## Choose a donut

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Ralp
Posts: 25
Joined: Sat Dec 16, 2006 9:44 am UTC
Location: internet
Contact:

### Choose a donut

A plate of donuts is served in the meeting room. There are three donuts left for you to choose from: two glazed donuts, and one jelly-filled. You like both glazed and jelly donuts equally. You can only take one, but later if you come back to the meeting room you hope to find at least one of the other donuts still there, so you can take another. (But three donuts in one day is entirely too many for you; even if both donuts happen to remain when you come back, you'd be just as happy with one.)

In the meantime though, it is possible that co-workers might check the meeting room and take a donut if they find one they like. You don't remember what kind of donuts your co-workers like, but you know everyone in the office who has a preference, has the same preference. In other words, if anyone refuses to eat glazed, then no one refuses to eat jelly, and vice versa. Additionally, some co-workers, like you, will eat any sort of donut.

What type of donut should you take in order to maximize the chances of at least one donut remaining when you come back later?

(The meta-puzzle here: why is this even an interesting problem? The solution seemed obvious until I thought about it more. I made this puzzle up and I do not know a general solution.)

V
Posts: 49
Joined: Thu Nov 09, 2006 1:15 pm UTC
If i take the glazed one, come back later and only the second glazed remains, am i allowed to take this one too ?

V.

Posts: 81
Joined: Fri Nov 24, 2006 11:32 pm UTC
The answer depends on how many people have no preference, like you, and how many try to get a donut. If you eat a glazed donut, leaving one of each kind, then it takes any person, and a person without preference to eat both of them. Call this situation A. If you leave 2 of the same type, and assuming that the general preferences are equally likely, then there is a 50% chance that it takes any two people, and a 50% chance that it takes two people with no preference. Call this situation B. Suppose there are n co-workers in total, i of which have no preference, and j people attempt to get a donut. Call the probability that there is at least one donut left P. If j=0, 1, you will get a donut at the end of the day, so consider j>=2. If j>=n-i+2, you will never get a donut, because at least two people with no preference will have wanted a donut.

Case A: You need either one or zero people with no preference to visit. If two or more visit, they will eat both donuts. If one visits, and he does not visit first, then someone else would have visited already and taken their favourite, and he would take the other. Also, if he does visit first, he must take the same kind that a person with a preference would take. If the first person is one of the n-i with a preference, then the rest must also have a preference. If he is one of the i without preference, the rest must still be those with a preference.

I've assumed that once a person with a preference visits and finds nothing they like, they won't come back, that's where all the (n-i)(n-i-1)...(n-i-j+1) comes from.

Hence, P(A) = ((n-i)(n-i-1)...(n-i-j+1)/n^j) + (1/2)*(i/n)*((n-i)(n-i-1)...(n-i-j+2)/n^(j-1)) = (1/2)*((n-i)(n-i-1)...(n-i-j+2)/n^(j-1)) * ((2n-i-2j+2)/n)

Case B: There is a 50% chance that the people prefer glazed, so any two people will eat both donuts. Otherwise, it will take two of the no preference people. Thus, you want only 0 or 1 no preference people to show up, and pray that nobody else likes glazed. jC1 is "j choose 1", and chooses a position for the no preference person. jC1=j, as there are j different positions.

P(B)=(1/2)[(jC1)*(i/n)*((n-i)(n-i-1)...(n-i-j+2)/n^(j-1)) + ((n-i)(n-i-1)...(n-i-j+1)/n^j)]=(1/2)*((n-i)(n-i-1)...(n-i-j+2)/n^(j-1)) * ((n-i-j+i*j+1)/n)

P(A)>P(B) <==> 2n-i-2j+2 > n-i-j+ij+1 <==> n+1 > j + i*j

I figure you know n, but if you don't know i and can't make some assumption for j, there's no best strategy.