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

# Who gets a free dinner?

### #11

Posted 23 March 2013 - 08:28 AM

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

Past prime, actually.

### #12

Posted 23 March 2013 - 04:46 PM

Awesome. Same problem though no ceiling. And it seems fair, but not in an obvious way. A proof of fairness would be nice.

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

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

### #13

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 =)

### #14

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.

Past prime, actually.

### #15

Posted 23 March 2013 - 08:35 PM

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

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 forNot acceptable. The winner must be decided by coin toss.

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

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.

### #16

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.

*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