Find The Apples

[gavinksong]

(This puzzle is taken from a blog called By Way Of Contradiction)

Imagine the following two player game. Alice secretly fills 3 rooms with apples. She has an infinite supply of apples and infinitely large rooms, so each room can have any non-negative integer number of apples. She must put a different number of apples in each room. Bob will then open the doors to the rooms in any order he chooses. After opening each door and counting the apples, but before he opens the next door, Bob must accept or reject that room. Bob must accept exactly two rooms and reject exactly one room. Bob loves apples, but hates regret. Bob wins the game if the total number of apples in the two rooms he accepts is a large as possible. Equivalently, Bob wins if the single room he rejects has the fewest apples. Alice wins if Bob loses.

Which of the two players has the advantage in this game?

[gavinksong]

Since nobody has gotten this...

Here's the answer:

Consider the following strategy: Bob rejects the first room with probability P(n), where n is the number of apples in the room. If he accepts, then he rejects the second room if it has fewer apples.

We can calculate Bob's chances of winning if Alice fills the rooms with a, b, and c apples, with a > b > c.

If the first room has a apples, Bob only wins if he accepts the first room, and the second room has c apples. Thus, (1 - P(a)) * (1/2).

If the first room has b apples, Bob only wins if he accepts the first room. Thus, (1 - P(.

If the first room has c apples, Bob only wins if he rejects the first room. Thus, P©.

Adding all of these together and dividing by three gives us Bob's total chances of winning. This simplifies to (1/2) + (P© - P(b) - P(a)/2) / 3.

Notice that Bob's chances of winning are above 50% if P© > P(b) + P(a)/2.

Since a, b, and c are natural numbers, any constantly decreasing function P(n) that satisfies P(n) > P(n+1) + P(n+2)/2 will give Bob an edge over Alice. One example of such a function is P(n) = 2^{-n}.

Note that if Alice knows Bob's strategy, she can reduce Bob's chances of winning to any percentage strictly greater than 50%, but can never truly even the odds.

[k-man]

By applying a correct strategy Bob can even his chances of winning against Alice. If Bob was to accept/reject at random or follow a fixed strategy (i.e. always reject the first room and accept the other two) his chance of winning would be 1 out of 3. However, if Bob always accepts the first room and decides to accept or reject a second room based on whether the number of apples in the second room is larger or smaller compared to the first room then his chances of winning become 50%.

 

One can easily see that by enumerating the possibilities. Let's call the room with the smallest number of apples - 1, the room with the largest number - 3, and the other one 2. So, Bob can open these rooms in one of the following orders. Each of these orders has exactly the same probability since he knows nothing about the rooms and opens them randomly. Following the above strategy, Bob wins in 3 cases and loses in 3 cases.

 

123 L

132 L

213 W

231 W

312 W

321 L

 

 

[gavinksong]

By applying a correct strategy Bob can even his chances of winning against Alice. If Bob was to accept/reject at random or follow a fixed strategy (i.e. always reject the first room and accept the other two) his chance of winning would be 1 out of 3. However, if Bob always accepts the first room and decides to accept or reject a second room based on whether the number of apples in the second room is larger or smaller compared to the first room then his chances of winning become 50%.

One can easily see that by enumerating the possibilities. Let's call the room with the smallest number of apples - 1, the room with the largest number - 3, and the other one 2. So, Bob can open these rooms in one of the following orders. Each of these orders has exactly the same probability since he knows nothing about the rooms and opens them randomly. Following the above strategy, Bob wins in 3 cases and loses in 3 cases.

123 L

132 L

213 W

231 W

312 W

321 L

Nice try, but not quite.

Bob can do better than just even the odds. Care to guess how?

This problem is a bit more interesting than it looks at first glance.

[karthickgururaj]

"infinite supply of apples and infinitely large rooms, so each room can have any non-negative integer number of apples": Ting..ting..ting.. This is setting off a few warning bells for me

 

For instance, how about the following rationale why Bob must always reject the first room:,

 

 

If the first room has 'x' apples, the probability that the second that third rooms have more than 'x' apples is '1', since the number of apples in those rooms can be any number from 0 to "infinity".

 

Of course, this line of reasoning has a flaw.

 

[gavinksong]

"infinite supply of apples and infinitely large rooms, so each room can have any non-negative integer number of apples": Ting..ting..ting.. This is setting off a few warning bells for me

For instance, how about the following rationale why Bob must always reject the first room:,

If the first room has 'x' apples, the probability that the second that third rooms have more than 'x' apples is '1', since the number of apples in those rooms can be any number from 0 to "infinity".

Of course, this line of reasoning has a flaw.

Haha, it's this thing again. Probability and infinity.

This isn't the answer I had in mind, but it did make me stop and think for a moment.

The real strategy actually tends to work in real life. In fact, it is one that a normal human being would use almost instinctively.

[wolfgang]

1- He should accept the 1st room, because ,in this case he has 2 possibilities.(accept,accept,reject)or(accept,reject,accept).

2-If the apples in the 2nd room >than in the 1st room, he should accept it.
3- If they were less, he should reject it and accept the 3rd room.
Leading to 50% chance of wining.

[gavinksong]

1- He should accept the 1st room, because ,in this case he has 2 possibilities.(accept,accept,reject)or(accept,reject,accept).

2-If the apples in the 2nd room >than in the 1st room, he should accept it.

3- If they were less, he should reject it and accept the 3rd room.

Leading to 50% chance of wining.

Nice try. This is what k-man got as well.

It's the obvious answer, but not the best one.

Edited October 18, 2014 by gavinksong

[bonanova]

"infinite supply of apples and infinitely large rooms, so each room can have any non-negative integer number of apples": Ting..ting..ting.. This is setting off a few warning bells for me

 

For instance, how about the following rationale why Bob must always reject the first room:,

 

 

If the first room has 'x' apples, the probability that the second that third rooms have more than 'x' apples is '1', since the number of apples in those rooms can be any number from 0 to "infinity".

 

Of course, this line of reasoning has a flaw.

 

 

The number of apples in rooms 1 and 2 are described by the same words.

What if Bob had gone to Room 2 first?

 

Or is that the flaw?

[karthickgururaj]

 

"infinite supply of apples and infinitely large rooms, so each room can have any non-negative integer number of apples": Ting..ting..ting.. This is setting off a few warning bells for me

 

For instance, how about the following rationale why Bob must always reject the first room:,

 

 

If the first room has 'x' apples, the probability that the second that third rooms have more than 'x' apples is '1', since the number of apples in those rooms can be any number from 0 to "infinity".

 

Of course, this line of reasoning has a flaw.

 

 

The number of apples in rooms 1 and 2 are described by the same words.

What if Bob had gone to Room 2 first?

 

Or is that the flaw?

 

No.. the flaw is that we can't directly deal with infinities, as you yourself showed in a different context

 

A better way to approach would be to assume an upper limit on the number of apples that may be kept in a room, and then take limits to infinity... wouldn't that answer the OP?

 

that Bob knows the upper limit, then Bob can come up with a better strategy. For instance, if the upper limit is 1000, and if the first room has 999 apples, it is better for Bob to accept it; but if it has 1 apple, it is better for him to reject it.

But looks like the strategy depends on the upper limit, in which case, I don't see how we can proceed with the limit to infinity.

 

So, in short: I don't know the answer to the puzzle

[gavinksong]

 

 

"infinite supply of apples and infinitely large rooms, so each room can have any non-negative integer number of apples": Ting..ting..ting.. This is setting off a few warning bells for me

For instance, how about the following rationale why Bob must always reject the first room:,

If the first room has 'x' apples, the probability that the second that third rooms have more than 'x' apples is '1', since the number of apples in those rooms can be any number from 0 to "infinity".

Of course, this line of reasoning has a flaw.

The number of apples in rooms 1 and 2 are described by the same words.

What if Bob had gone to Room 2 first?

Or is that the flaw?

No.. the flaw is that we can't directly deal with infinities, as you yourself showed in a different context

A better way to approach would be to assume an upper limit on the number of apples that may be kept in a room, and then take limits to infinity... wouldn't that answer the OP?

that Bob knows the upper limit, then Bob can come up with a better strategy. For instance, if the upper limit is 1000, and if the first room has 999 apples, it is better for Bob to accept it; but if it has 1 apple, it is better for him to reject it.

But looks like the strategy depends on the upper limit, in which case, I don't see how we can proceed with the limit to infinity.

So, in short: I don't know the answer to the puzzle

I believe that the solution can be found using this method, but it is a bit roundabout. Something you said does suggest you are moving in right direction.

Edited October 19, 2014 by rookie1ja

[plainglazed]

if the first room has one apple in it, don't select it; otherwise, the same as k-man.  for a finite number of apples, which is ultimately the case as they are counted, this improves on the 50/50 odds giving Bob a slight advantage over Alice.

[gavinksong]

if the first room has one apple in it, don't select it; otherwise, the same as k-man. for a finite number of apples, which is ultimately the case as they are counted, this improves on the 50/50 odds giving Bob a slight advantage over Alice.

Sneaky, but wrong. All Alice would have to do is put more than one or two apples in every room, and your strategy would fall flat.

[karthickgururaj]

 

To arrive at a working strategy, the information gathered (for example, the number of apples in the first room) must influence the probability of "finding more apples in the other room". For example, the a priori chance that "room 1 has more apples than room 2" is 0.5. After seeing the number of apples in room 1, this number (0.5) has to change in a predictable way to a posteriori chance that "room 1 has more apples than room 2". Indeed, that would happen if Bob knew the maximum number of apples ('MAX') that Alice is going to keep in the rooms. A strategy can then be formulated..

 

A change in probability is what happens in case of Monty Hall problem - the information that a third door has a goat changes the probability of finding a car behind doors 1 and 2.. 

 

However, in case of OP, Bob doesn't know 'MAX'. So I think what Bob needs to do is:

a. Open room 1 and accept it always. Use the number of apples in room 1 to make an estimate of 'MAX'. I think 2*x is the best estimate for 'MAX', where x = number of apples in room 1.

b. Open room 2. Accept it if the number of apples in room 2 is greater than half of the MAX estimate; else reject it.

 

..but this turns out to be the same approach as k-man.

 

[gavinksong]

To arrive at a working strategy, the information gathered (for example, the number of apples in the first room) must influence the probability of "finding more apples in the other room". For example, the a priori chance that "room 1 has more apples than room 2" is 0.5. After seeing the number of apples in room 1, this number (0.5) has to change in a predictable way to a posteriori chance that "room 1 has more apples than room 2". Indeed, that would happen if Bob knew the maximum number of apples ('MAX') that Alice is going to keep in the rooms. A strategy can then be formulated..

A change in probability is what happens in case of Monty Hall problem - the information that a third door has a goat changes the probability of finding a car behind doors 1 and 2..

However, in case of OP, Bob doesn't know 'MAX'. So I think what Bob needs to do is:

a. Open room 1 and accept it always. Use the number of apples in room 1 to make an estimate of 'MAX'. I think 2*x is the best estimate for 'MAX', where x = number of apples in room 1.

b. Open room 2. Accept it if the number of apples in room 2 is greater than half of the MAX estimate; else reject it.

..but this turns out to be the same approach as k-man.

I think you guys need a little something.

The strategy isn't as complicated as you might think, and it makes sense intuitively (unlike Monty Hall which is pretty counterintuitive), although it does take some math to prove.

Only one step in k-man's solution must be changed/augmented to arrive at the superior strategy.

There is no "optimal" strategy. The answer isn't a fixed solution but rather a set of solutions that work better than 50% whose actual effectiveness varies based on the distribution of apples. Thus, the final winning percentage is not fixed either.

I will save this one for later for if you guys really need it.

[k-man]

I don't know if I'm taking your hints correctly, but based on your hints, I'm inclined to interpret "infinity" as "no specific limit, but within some practical boundaries". Using this interpretation I can suggest a...

Provided that Bob and Alice really enjoy playing this game and will do it over and over again, Bob can estimate the MAX based on prior experience and decide whether a particular number is SMALL compared to the MAX. Then Bob can reject the first room if the number of apples in the first room is SMALL. Bob can start with SMALL=1 (as plainglazed suggested) or he can start with a higher number depending on his prior knowledge of Alice's generosity. Bob can adjust his estimate of SMALL as the rounds progress.

 

Now, I know that in math there isn't such thing as a "small number" as any and every number is small on the infinite scale, but that was the only thing that came to mind from the "intuitive" part of my brain  

[gavinksong]

I don't know if I'm taking your hints correctly, but based on your hints, I'm inclined to interpret "infinity" as "no specific limit, but within some practical boundaries". Using this interpretation I can suggest a...

Provided that Bob and Alice really enjoy playing this game and will do it over and over again, Bob can estimate the MAX based on prior experience and decide whether a particular number is SMALL compared to the MAX. Then Bob can reject the first room if the number of apples in the first room is SMALL. Bob can start with SMALL=1 (as plainglazed suggested) or he can start with a higher number depending on his prior knowledge of Alice's generosity. Bob can adjust his estimate of SMALL as the rounds progress.

Now, I know that in math there isn't such thing as a "small number" as any and every number is small on the infinite scale, but that was the only thing that came to mind from the "intuitive" part of my brain

You're going somewhat in the right direction (and so is everybody else) but have yet to break one assumption about the correct strategy.

Mulling over my big hint may help, but also maybe not. I don't want to give too much away.

We cannot assume that there are any practical limits to the number of apples.

[koren]

"Which of the two players has the advantage in this game?"

My answer is Alice:

 

     A B C
1   S L M
2   S M L
3   M S L
4   M L S
5   L S M
6   L M S
S - room with a small amount of apples, M – medium, L – large.

Bob possibilities are reduced to the following options:

1) rejection of the first room - A
In this case, his chance to get ML combination reduced to 2 out of 6, meaning P1= 1/3

2) To accept room A, then there are two possibilities:
 

First - B contains more apples than A – versions 1, 2, 4.
S L M
S M L
M L S
Bob must then select the second room B which means that the probability of winning P2 = 1/3

 

The second - B contains less apples than A – versions 3, 5, 6.
M S L
L S M
L M S
Bob must select the room C - the probability to win = 2/3

But do not forget that the probability of obtaining the second variant is 1/2 from the very beginning, which eventually means (1/2x2/3)    P3 = 1/3  as well as the fact that poor Bob has no chance of winning.  

[gavinksong]

"Which of the two players has the advantage in this game?"

My answer is Alice:

A B C

1 S L M

2 S M L

3 M S L

4 M L S

5 L S M

6 L M S

S - room with a small amount of apples, M – medium, L – large.

Bob possibilities are reduced to the following options:

1) rejection of the first room - A

In this case, his chance to get ML combination reduced to 2 out of 6, meaning P1= 1/3

2) To accept room A, then there are two possibilities:

First - B contains more apples than A – versions 1, 2, 4.

S L M

S M L

M L S

Bob must then select the second room B which means that the probability of winning P2 = 1/3

The second - B contains less apples than A – versions 3, 5, 6.

M S L

L S M

L M S

Bob must select the room C - the probability to win = 2/3

But do not forget that the probability of obtaining the second variant is 1/2 from the very beginning, which eventually means (1/2x2/3) P3 = 1/3 as well as the fact that poor Bob has no chance of winning.

Your answer is incorrect...

Umm... None of your steps appear to be wrong but somehow you jumped to the wrong conclusion. If you look at all of the possible scenarios, Bob wins in three out of six of them (one out of the three cases where the second room contains more apples, and two out of the three cases where the second room contains fewer apples). That's 50%.

[k-man]

I think Bob can achieve the win/loss ratio of 14/27, which is about 51.8%. I'm not sure it's the maximum and I still need to check my calculations for errors, but if the answer is correct then I'll post the solution later.

[k-man]

Ignore my previous post as I found an error in my calculations and this time I think I found the maximum.

 

Bob has an advantage and can win 25 out of 48 times by following a specific strategy.

1. Bob always accepts the first room unless there is only one apple in it. We can ignore this edge case from probability calculations and assume that Bob will ALWAYS accept the first room he opens.

2. Bob will accept the second room if the number of apples in the second room is greater than 75% of the apples in the first room.

 

Denoting the rooms as S - smallest number of apples, M - medium number of apples, L - largest number of apples, there are 6 possible ways in which Bob will open the doors and the probability of Bob winning with this strategy is as follows:

 

SML 0        

SLM 0        

MSL 3/4  

MLS 1        

LSM 15/16 

LMS 7/16

 

Each of these sequences has equal probability of 1/6, so the total probability of winning is (1+3/4+15/16+7/16)/6 = 25/48

[gavinksong]

Ignore my previous post as I found an error in my calculations and this time I think I found the maximum.

Bob has an advantage and can win 25 out of 48 times by following a specific strategy.

1. Bob always accepts the first room unless there is only one apple in it. We can ignore this edge case from probability calculations and assume that Bob will ALWAYS accept the first room he opens.

2. Bob will accept the second room if the number of apples in the second room is greater than 75% of the apples in the first room.

Denoting the rooms as S - smallest number of apples, M - medium number of apples, L - largest number of apples, there are 6 possible ways in which Bob will open the doors and the probability of Bob winning with this strategy is as follows:

SML 0

SLM 0

MSL 3/4

MLS 1

LSM 15/16

LMS 7/16

Each of these sequences has equal probability of 1/6, so the total probability of winning is (1+3/4+15/16+7/16)/6 = 25/48

Huh. I suppose this could be an alternative solution to the problem? But if course, this wasn't the solution I had in mind.

One thing that is a bit iffy about your solution is that you shouldn't have been able to calculate the probability that the number of apples in a certain room is more than 75% of the apples in another room since a probability distribution was not defined.

For the sake of clarity, from now on assume that Alice knows Bob's strategy. Thus, the distribution of apples is not completely random, but chosen in such a way to try and minimize Bob's chances of winning (if possible).

Edited October 21, 2014 by gavinksong

[gavinksong]

Perhaps the solution isn't very intuitive, but a regular person would still do something similar.

[k-man]

Huh. I suppose this could be an alternative solution to the problem? But if course, this wasn't the solution I had in mind.

For the sake of clarity, from now on assume that Alice knows Bob's strategy. Thus, the distribution of apples is not completely random, but chosen in such a way to try and minimize Bob's chances of winning (if possible).

One thing that is a bit iffy about your solution is that you shouldn't have been able to calculate the probability that the number of apples in a certain room is more than 75% of the apples in another room since a probability distribution was not defined.

 

a uniform probability distribution over a finite set after the first number is revealed. I don't understand how you can calculate the probability of Bob winning without assuming some kind of probability distribution for the numbers. If Alice knows Bob's strategy then she can force his odds down to 50%. I can't see how Bob can overcome that.

 

I'm ready to hear your solution. 

[bonanova]

There is a classic problem of the princess selecting a suitor to be her husband. There are N suitors. They are brought before the princess one by one, and the princess must decide then and there whether to accept him or not. The process ends when she makes a positive choice. The puzzle has any number of variations. One variation has N slips of paper in a hat and you attempt to pick the one with the largest number written on it. You know nothing about the numbers (i.e. you know nothing about the probability distribution) except that each slip has a positive integer on it.

This is the same puzzle, but in reverse. Three rooms. Each has a positive integer (number of apples) with no known probability distribution. But now you must choose (by rejecting it) the lowest number.

The winning strategy in the first puzzle, where the largest integer (richest, most handsome suitor) is sought, is to reject a certain number n of candidates and then accept the next candidate that exceeds the maximum of the first n. If no such candidate is found (this happens when the largest was contained in the first n) then the last candidate must be chosen. I should say that is the process. The puzzle is to determine the optimal value for n.

 

You want n to be large enough to give you a good selection threshold, but small enough to provide a good chance that the best candidate lies in the remaining candidate pool. The answer can be calculated. The optimal value for n is N/e. And the probability of finding the optimal candidate is 1/e.

 

Why is it not 1-1/e? Because (a) the threshold almost always will be too low and (b) the first-encountered better candidate may not be best. The only assumption you must make is that the optimal candidate lies uniformly within the N candidates. This is certainly the case where slips of paper are drawn from a hat, and it is assumed to be true in the other cases. I.e. the richest suitor is no more or less likely to be the first suitor, or the last.

 

Of course, e does not divide any integer N. So in practice one chooses n to be the integer closest to N/e. And the probability of success is best approximated by 1/e for large values of N.

 

How does that apply here? Quite simply. N=3. N/e is closest to 1, so n = 1.

 

Bob accepts the first room.

He then rejects the second room if it has fewer apples,

else he rejects the third room.

 

Bob's probability of success is approximated by 1/e.

But the puzzle only asks whether Bob's chances are greater than 1/2.

They are not. Alice has the edge.

 

Edit:

1/e is not very different from 1/3, where Bob randomly chooses a room to reject.

It is difficult therefore to find a persuasive argument in favor of a particular selection algorithm.

Edited October 22, 2014 by bonanova
Footnote

[gavinksong]

There is a classic problem of the princess selecting a suitor to be her husband. There are

N suitors. They are brought before the princess one by one, and the princess must decide then and there whether to accept him or not. The process ends when she makes a positive choice. The puzzle has any number of variations. One variation has N slips of paper in a hat and you attempt to pick the one with the largest number written on it. You know nothing about the numbers (i.e. you know nothing about the probability distribution) except that each has a positive integer on it.

This is the same puzzle, but in reverse. Three rooms. Each has a positive integer (number of apples) with no known probability distribution. But now you must choose (by rejecting it) the lowest number.

The winning strategy in the first puzzle, where the largest integer (richest, most handsome suitor) is sought, is to reject a certain number n of candidates and then accept the next candidate that exceeds the maximum of the first n. If no such candidate is found (if the largest was contained in the first n) then the last candidate must be chose. I should say that is the process. The puzzle is to determine the optimal value for n.

You want n to be large enough to give you a good selection threshold, but small enough to provide a good chance that the sought-after candidate lies in the remaining candidate pool. The answer can be calculated. The optimal value for n is N/e. The only assumption you make is the the optimal candidate is uniformly among the N candidates. This is certainly the case where slips of paper are drawn from a hat, and it is assumed in the other cases. I.e. the richest suitor is no more likely to be the first suitor or the last.

Of course, e does not divide any integer N. So the solution is never exact. In practice, one chooses n to be the integer integer to N/e.

How does that apply here? Quite simply. N=3. N/e is closest to 1. n = 1.

Bob accepts the first room.

He then rejects the second room if it has fewer apples,

else he rejects the third room.

That was clever trying to reduce the problem into one with a known solution, bonanova. Unfortunately, the strategy you came up with is exactly the same as k-man's first strategy.

Bob can only do better specifically

because he has to reject the smallest option, as opposed to accepting the largest as in your princess problem. Why aren't they the same thing? A hint lies herein.

k-man,

Don't give up yet. Think about it a little bit more after mulling over my final hint.

Unlike any of the strategies that have been suggested so far, which were all deterministic, the 'correct' strategy is

stochastic. Crazy, right? It works better than 50%, even when Alice knows Bob's strategy, thus giving Bob a definite upper hand.