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?

This puzzle is my own design, and it is a lot more interesting than it looks at first. I will post the solution in the comments.

FIrst of all, the solution is NOT that the game is fair. If you thought that was the solution, then you should think about the problem some more with the following hint:

If Bob were to accept only one room and reject two rooms, the game would be fair.

Now I will give the actual solution. Bob has the advantage in this game. No matter how Alice puts the apples in the rooms, Bob can win with probability greater than 50%. However by her choice of how to distribute apples, Alice can reduce Bob’s chance of winning to any number strictly greater than 50%.

Here is Bob’s algorithm:

Look in a uniformly randomly chosen room. Let be the number of apples in that room. Reject that room with probability , and otherwise accept it.

If the first room was accepted, look in another room uniformly at random, and accept it if and only if it has at least as many apples as the first room.

Let’s look at the probability that Bob wins if Alice fills the rooms with , , and apples, with .

If the first room he sees has , he wins with probability , since he has a chance to accept the first room, and a chance to then open the room with and reject it.

If the first room he sees has , he wins with probability , since he has a chance to accept the first room, and if he does, he will accept the room with and reject the room with .

If the first room he sees has apples, he wins with probability , since he has a chance to reject this room, and if he does, he wins.

Therefore, the probability that Bob wins is

This simplifies to , which is always greater than 50%, since .

So… Is (1/2)^n generally the best choice? I noticed that sometimes (2/3)^n gives better chances of winning. (2/3) seems to be better for larger values of a, b and c. Can you explain this? And could Bob somehow use this to his advantage?

Great question. Different strategies do better or worse, depending on what numbers Alice picks. There isn’t really a well defined way to say one strategy does better than another, because if Alice knows your strategy, she can always choose the numbers so that your chance of winning is exactly whatever number greater than 50% she wants it to be. I choose 1/2 because it was simple.

It just has to be a strictly decreasing function. I would have used 1/n.

For Alice wanting a probability of winning very close to 50%, it’s better to use a function that decreases slower, since it would take longer to stop decreasing. (2/3)^n is better than (1/2)^n, but 1/n is better than (2/3)^n, and 1/log(n) is better than 1/n, etc.

That is actually not true. It must decreases sufficiently quickly so that . This can be achieved with , where .

Also, by decreasing slower, you are doing better for large numbers, but at the cost of doing worse for small numbers that Alice might pick.

Bob must always accept the first room he looks into unless it has 1 apple. So as long as Alice doesn’t make any rooms contain only 1 apple, she has the better odds. Continued below…

Because Bob has to accept the first room, there is a 66% chance that he will have accepted a room that is NOT the room with the least apples. If he HAS accepted the room with the least apples, then he has lost.

Moving onto the second room, because we know the first room isn’t the room with the least apples, that means the second room with have either more or fewer apples than the first. Regardless, there is a 50% chance that this room is the room with the least apples. That means the 3rd room ALSO has a 50% chance of being the room with the least apples. Therefor, Bob’s second choice is irrelevant.

That means bob will always either

A) Accept 1 and Accept 2

or

B) Accept 1 and Reject 2 (Subsequently Accepting 3)

So Bob will EVERY TIME make a 33% bad choice combined with a 50% bad choice which is a 16.5% chance to make the wrong choice and a 84.5% chance to make the right choice.

Bob has the advantage.

Correction for my post.

So Bob will EVERY TIME make a 33% bad choice combined with a 50% bad choice which is a 41.5% chance to make the wrong choice and a 59.5% chance to make the right choice.

Bob has the advantage.

Thank you for you comment, Jason. However, this is not correct. With your strategy, if I understand it correctly, Bob wins with probability 50%. Try for yourself the 6 permutations of the three rooms, and you will see that Bob only wins for 3 of them.

You didn’t follow your algorithm correctly.

bob has 66% of right choice in the first, if he makes the wrong choice, he has already lost, regardless of the second choice.

He then has 50% of making the right choice in the second, so in the case that he made the right choice in the first room, only 50% of the time will he end up winning the game, giving him a 33% chance of winning.

Assuming Bob remembers how many apples were in the previous room… If the second room has more apples than the first , Bob will not reject it. Thus Bob accepts the first room (2/3 winning choice) followed by the informed guess on the second room (4/7 winning choice) giving him a 38% chance of winning.

Assuming Bob remembers how many apples were in the previous room… If (first)(third), Bob will not reject the second room. Thus Bob accepts the first room (2/3 winning choice) followed by the informed guess on the second room (4/7 winning choice) giving him a 38% chance of winning.

The correct reply is brilliant (in a slightly-beyond-my-ken way). I thought that I’d done well to achieve 50% chance for Bob, with the strategy ‘accept first room. Accept second room if higher than first room, reject if lower than second room’. Assuming the rooms are A>B>C, this would mean Bob won on

ACB

BAC

BCA

but not

ABC

CAB

CBA

From the correct solution, I take it this is the best result you can get with a fixed rather than probabilistic algorithm. Assuming Alice doesn’t have a room with only 1 apple in, which would be fairly dumb.

You need a probabilistic approach just to view the three rooms in a random order. Also, if Bob knew for sure what Alice’s probabilistic strategy was, Bob could always reject the first room if it happens to be the lowest possible number Alice would pick. This way, if Alice has to choose her strategy first, Bob, can respond with a deterministic strategy which wins more than half the time.

OK, I’m probably using the terminology wrong! But to me, there’s a difference between randomly selecting one of 3 things and having to make a calculation and then use a random number generator to decide whether to keep the contents of a room. My solution doesn’t rely on Bob knowing what Alice’s strategy is: the point about Alice putting 1 apple in a room is an exception. So the rule would state

– If first room contains only one apple, REJECT. Otherwise, ACCEPT

– If second room contains more apples than first room ACCEPT. Otherwise REJECT

That should provide even odds at worst: better if Alice puts 1 in one of the rooms.

I agree that randomly ordering the rooms feels different from randomly decided whether you accept or reject, but I do not there is a good way to formalize this difference.

I was not disagreeing with you about doing even or better with that strategy. You are correct. I was making a side comment that if Alice choose a probabilistic strategy, and Bob knew what this probabilistic strategy was, then Bob could win more than half the time with a strategy that is deterministic in the strictest sense. .

BWOC,

I shared this puzzle on a forum (after giving you credit of course). People are still grappling with it as we speak. Here’s the link: http://brainden.com/forum/index.php/topic/17188-find-the-apples/page-3#entry340706

Thank you for the amazing puzzle! 🙂

Seriously, your puzzles are the best.