Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -

An Unfair Coin 2: Fairness Strikes Back


  • Please log in to reply
6 replies to this topic

#1 EventHorizon

EventHorizon

    Senior Member

  • VIP
  • PipPipPipPip
  • 512 posts
  • Gender:Male

Posted 27 July 2012 - 01:02 PM

I took the coin from ujjagrawal's post out of the biased random number generators jar that had been collecting dust in the corner of the Den, but I needed to choose between two options with 50% probability each. I thought this would be easy since I already calculated the probability that heads would come up for this coin.

Spoiler for Hint to 1, and info from ujjagrawal's puzzle


1) How can I choose between the two options with 50% probability?

2) I accidently drop ujjagrawal's coin in the jar, and now don't know which one it is. I grab another coin from the jar. How can I choose between the two options with equal probability using this new coin (assuming both heads and tails can be outcomes on any given flip and occur with constant probabilities)?

3) How can I use the coin from (2) to choose between N options, where N is a positive integer, with the fewest number of coin flips needed on average?
  • 0

#2 phil1882

phil1882

    Senior Member

  • Members
  • PipPipPipPip
  • 550 posts

Posted 27 July 2012 - 01:43 PM

not sure i understand the puzzle.
Spoiler for

  • 0

#3 jim

jim

    Junior Member

  • Members
  • PipPip
  • 33 posts

Posted 27 July 2012 - 02:47 PM

Spoiler for 1 and 2


Spoiler for 3

  • 0

#4 EventHorizon

EventHorizon

    Senior Member

  • VIP
  • PipPipPipPip
  • 512 posts
  • Gender:Male

Posted 27 July 2012 - 11:32 PM

Hey jim. It is common courtesy to use spoilers so others will see your answer only if they want to. Please use them in the future. (Will a mod spoilerify his post please?)

That being said... good job on 1&2. I wanted a different answer for 1, but 2's answer will obviously work too.

As for 3, it was a valiant attempt. You've identified a number of the needed elements in the solution, but you've missed something. Also, I think you may have misunderstood the problem as choosing between two options with an unequal probability based on N. The problem is asking you to choose from from a set of N different options with equal probability. This is a simple difference, but not the only thing I believe is missing from the solution.

Though I should point out that I don't have a full solution worked up yet.
  • 0

#5 CaptainEd

CaptainEd

    Senior Member

  • Members
  • PipPipPipPip
  • 1094 posts

Posted 09 August 2012 - 10:40 PM

Spoiler for To choose one of N buckets, equiprobably, with an unknown unfair coin


Oh, you want the minimum flip solution...sorry

Edited by CaptainEd, 09 August 2012 - 10:43 PM.

  • 0

#6 CaptainEd

CaptainEd

    Senior Member

  • Members
  • PipPipPipPip
  • 1094 posts

Posted 09 August 2012 - 10:52 PM

Spoiler for Sigh, silly captain!

  • 0

#7 CaptainEd

CaptainEd

    Senior Member

  • Members
  • PipPipPipPip
  • 1094 posts

Posted 10 August 2012 - 03:41 PM

Spoiler for Is this Jim's proposal?

  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users