## 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

# Who gets a free dinner?

Best Answer James33, 23 March 2013 - 12:17 AM

Spoiler for A Third Way

Go to the full post

15 replies to this topic

### #11 Prime

Prime

Senior Member

• Members
• 872 posts
• Gender:Male
• Location:Illinois, US

Posted 23 March 2013 - 08:28 AM

I'd like to enter the following solution and claim the minimum number of throws.

Spoiler for just 1

• 0

Past prime, actually.

### #12 bushindo

bushindo

Senior Member

• VIP
• 721 posts
• Gender:Male
• Location:Los Angeles, CA

Posted 23 March 2013 - 04:46 PM

You're out with friends at Chuck's Steak House and decide to flip a coin to select one person get a free dinner. The bill will be split n-1 ways instead of n ways. Since I was not invited, I don't know how many are in the group. (Maybe next time you'll include me; I love Chuck's place.) So anyway, your selection method has to work for an arbitrary numbers of participants.

You have only a fair coin, and the method has to treat everyone equally.
It must be absolutely fair and unbiased.

There might be many ways; bonus points await methods with originality, flair, and minimization of flips.

Pick one person out of n, fairly, with a sequence of fair coin tosses.

I'm trying to go for the minimum expected number of flips here. This is my best attempt so far
Spoiler for
Awesome. Same problem though no ceiling. And it seems fair, but not in an obvious way. A proof of fairness would be nice.

I don't think this problem can be decided with a fixed ceiling method. That is, I don't think there exist a method that guarantees a maximum number of fixed maximum flips  m(N) for every N. See below for reason + proof of fairness
Spoiler for

• 0

### #13 bushindo

bushindo

Senior Member

• VIP
• 721 posts
• Gender:Male
• Location:Los Angeles, CA

Posted 23 March 2013 - 04:57 PM

I'd like to enter the following solution and claim the minimum number of throws.

Spoiler for just 1

I see your 1 and I will raise you a 0 =)

Spoiler for

• 0

### #14 Prime

Prime

Senior Member

• Members
• 872 posts
• Gender:Male
• Location:Illinois, US

Posted 23 March 2013 - 07:44 PM

I don't think this problem can be decided with a fixed ceiling method. That is, I don't think there exist a method that guarantees a maximum number of fixed maximum flips  m(N) for every N. See below for reason + proof of fairness

Spoiler for

Agree. A fair method cannot guaranty any maximum number of tosses.

I'd like to enter the following solution and claim the minimum number of throws.

Spoiler for just 1

I see your 1 and I will raise you a 0 =)

Spoiler for

Not acceptable. The winner must be decided by coin toss.

• 0

Past prime, actually.

### #15 bushindo

bushindo

Senior Member

• VIP
• 721 posts
• Gender:Male
• Location:Los Angeles, CA

Posted 23 March 2013 - 08:35 PM

I don't think this problem can be decided with a fixed ceiling method. That is, I don't think there exist a method that guarantees a maximum number of fixed maximum flips  m(N) for every N. See below for reason + proof of fairness

Spoiler for

Agree. A fair method cannot guaranty any maximum number of tosses.

I'd like to enter the following solution and claim the minimum number of throws.

Spoiler for just 1

I see your 1 and I will raise you a 0 =)

Spoiler for
Not acceptable. The winner must be decided by coin toss.

My interpretation of the OP is that the coin flip is optional rather than mandatory. The OP says "Pick a person out of n with a sequence of coin toss". I submit that it is possible to construct a sequence of length 0.
• 0

### #16 bonanova

bonanova

bonanova

• Moderator
• 5776 posts
• Gender:Male
• Location:New York

Posted 24 March 2013 - 04:09 AM

I'm trying to go for the minimum expected number of flips here. This is my best attempt so far

Spoiler for

This is the method I had in mind. It follows from a previous discussion of simulating an arbitrarily biased outcome using a fair coin.

But let the discussion continue.
• 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users