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?

[k-man]

There is probably something I'm missing, but I tried the stochastic approach and it didn't help. Here is what I did...

 

Let's say that Bob's strategy is to accept the first room randomly with some probability x. Then, if he accepted the first room and the second room has a smaller number then he accepts it at random with some probability y. Second room with a larger number of apples is always accepted.

 

The probability of winning in each case is then determined as follows:

 

SML 1-x

SLM 1-x

MSL x(1-y)

MLS x

LSM x(1-y)

LMS xy

 

The total probability of Bob winning is the sum of the above divided by 6. After simplification we get (2+x-xy)/6, which has a maximum of 0.5 when x=1 and y=0, which means that Bob should always accept the first room and never the second (if smaller than the first) to maximize his odds.

[gavinksong]

There is probably something I'm missing, but I tried the stochastic approach and it didn't help. Here is what I did...

Let's say that Bob's strategy is to accept the first room randomly with some probability x. Then, if he accepted the first room and the second room has a smaller number then he accepts it at random with some probability y. Second room with a larger number of apples is always accepted.

The probability of winning in each case is then determined as follows:

SML 1-x

SLM 1-x

MSL x(1-y)

MLS x

LSM x(1-y)

LMS xy

The total probability of Bob winning is the sum of the above divided by 6. After simplification we get (2+x-xy)/6, which has a maximum of 0.5 when x=1 and y=0, which means that Bob should always accept the first room and never the second (if smaller than the first) to maximize his odds.

Your analysis isn't wrong; doing it like that won't work. Try another approach.

[gavinksong]

Why is it unfortunate? What part of the solution are you challenging?

Hmm. It seems I read over the part where you estimated the probability to be 1/3. I can tell you that is not the case, possibly because it is an estimate. The actual probability is 1/2, as it was shown by k-man and wolfgang. I'm sorry.

[k-man]

 

There is probably something I'm missing, but I tried the stochastic approach and it didn't help. Here is what I did...

Let's say that Bob's strategy is to accept the first room randomly with some probability x. Then, if he accepted the first room and the second room has a smaller number then he accepts it at random with some probability y. Second room with a larger number of apples is always accepted.

The probability of winning in each case is then determined as follows:

SML 1-x

SLM 1-x

MSL x(1-y)

MLS x

LSM x(1-y)

LMS xy

The total probability of Bob winning is the sum of the above divided by 6. After simplification we get (2+x-xy)/6, which has a maximum of 0.5 when x=1 and y=0, which means that Bob should always accept the first room and never the second (if smaller than the first) to maximize his odds.

Your analysis isn't wrong; doing it like that won't work. Try another approach.

 

Bob could establish a probability function

f(n) that determines the probability to accept the first room based on the number of apples n in that room. The function would favor larger numbers over smaller ones. The function would have to be 0 for n=1 and approach 1 for n->infinity. For example f(n) could be 1-1/n. I don't know how to calculate the probability of Bob winning in this case as his chances of winning now depend on what Alice puts in the rooms and what room he opens first. Also, it seems that even if such function exists that could give Bob an edge, this edge would be theoretical as Alice can choose 3 very large consecutive numbers as a counter tactic.

[gavinksong]

There is probably something I'm missing, but I tried the stochastic approach and it didn't help. Here is what I did...

Let's say that Bob's strategy is to accept the first room randomly with some probability x. Then, if he accepted the first room and the second room has a smaller number then he accepts it at random with some probability y. Second room with a larger number of apples is always accepted.

The probability of winning in each case is then determined as follows:

SML 1-x

SLM 1-x

MSL x(1-y)

MLS x

LSM x(1-y)

LMS xy

The total probability of Bob winning is the sum of the above divided by 6. After simplification we get (2+x-xy)/6, which has a maximum of 0.5 when x=1 and y=0, which means that Bob should always accept the first room and never the second (if smaller than the first) to maximize his odds.

Your analysis isn't wrong; doing it like that won't work. Try another approach.

Bob could establish a probability function

f(n) that determines the probability to accept the first room based on the number of apples n in that room. The function would favor larger numbers over smaller ones. The function would have to be 0 for n=1 and approach 1 for n->infinity. For example f(n) could be 1-1/n. I don't know how to calculate the probability of Bob winning in this case as his chances of winning now depend on what Alice puts in the rooms and what room he opens first. Also, it seems that even if such function exists that could give Bob an edge, this edge would be theoretical as Alice can choose 3 very large consecutive numbers as a counter tactic.

Go on.

[karthickgururaj]

 

 

 

There is probably something I'm missing, but I tried the stochastic approach and it didn't help. Here is what I did...

Let's say that Bob's strategy is to accept the first room randomly with some probability x. Then, if he accepted the first room and the second room has a smaller number then he accepts it at random with some probability y. Second room with a larger number of apples is always accepted.

The probability of winning in each case is then determined as follows:

SML 1-x

SLM 1-x

MSL x(1-y)

MLS x

LSM x(1-y)

LMS xy

The total probability of Bob winning is the sum of the above divided by 6. After simplification we get (2+x-xy)/6, which has a maximum of 0.5 when x=1 and y=0, which means that Bob should always accept the first room and never the second (if smaller than the first) to maximize his odds.

Your analysis isn't wrong; doing it like that won't work. Try another approach.

Bob could establish a probability function

f(n) that determines the probability to accept the first room based on the number of apples n in that room. The function would favor larger numbers over smaller ones. The function would have to be 0 for n=1 and approach 1 for n->infinity. For example f(n) could be 1-1/n. I don't know how to calculate the probability of Bob winning in this case as his chances of winning now depend on what Alice puts in the rooms and what room he opens first. Also, it seems that even if such function exists that could give Bob an edge, this edge would be theoretical as Alice can choose 3 very large consecutive numbers as a counter tactic.

Go on.

 

Very interesting. I'm also now wondering about the puzzle itself.. What should Bob do: have a strategy that ensures he rejects the room with least number of apples,

 

Ensure he gets maximum number of apples? In other words, if Bob can "force" Alice to put more apples in each room, does that mean he won?

[gavinksong]

There is probably something I'm missing, but I tried the stochastic approach and it didn't help. Here is what I did...

Let's say that Bob's strategy is to accept the first room randomly with some probability x. Then, if he accepted the first room and the second room has a smaller number then he accepts it at random with some probability y. Second room with a larger number of apples is always accepted.

The probability of winning in each case is then determined as follows:

SML 1-x

SLM 1-x

MSL x(1-y)

MLS x

LSM x(1-y)

LMS xy

The total probability of Bob winning is the sum of the above divided by 6. After simplification we get (2+x-xy)/6, which has a maximum of 0.5 when x=1 and y=0, which means that Bob should always accept the first room and never the second (if smaller than the first) to maximize his odds.

Your analysis isn't wrong; doing it like that won't work. Try another approach.

Bob could establish a probability function

f(n) that determines the probability to accept the first room based on the number of apples n in that room. The function would favor larger numbers over smaller ones. The function would have to be 0 for n=1 and approach 1 for n->infinity. For example f(n) could be 1-1/n. I don't know how to calculate the probability of Bob winning in this case as his chances of winning now depend on what Alice puts in the rooms and what room he opens first. Also, it seems that even if such function exists that could give Bob an edge, this edge would be theoretical as Alice can choose 3 very large consecutive numbers as a counter tactic.

Go on.

Very interesting. I'm also now wondering about the puzzle itself.. What should Bob do: have a strategy that ensures he rejects the room with least number of apples,

Ensure he gets maximum number of apples? In other words, if Bob can "force" Alice to put more apples in each room, does that mean he won?

Oh... Haha. No, it's nothing like that. Bob only wins if he rejects the smallest room, regardless of how many apples he gets total.

[DejMar]

gavinksong, on 23 Oct 2014 - 12:58 AM, said:

"the function would have to be 0 for n=1"

 

Why? The least number of apples Alice can place in a room is 0, not 1.  0 is a non-negative integer, and thus a valid option for Alice.

 

 

"each room can have any non-negative integer number of apples"

[gavinksong]

gavinksong, on 23 Oct 2014 - 12:58 AM, said:

"the function would have to be 0 for n=1"

Why? The least number of apples Alice can place in a room is 0, not 1. 0 is a non-negative integer, and thus a valid option for Alice.

"each room can have any non-negative integer number of apples"

Uhh... I didn't say that. It was k-man. :|

That said, that's a pretty trivial correction.

It seems that when you quoted me quoting k-man, you accidentally removed the spoiler brackets (apparently along with the innermost quotation brackets). Could you be more careful about that in the future?

[DejMar]

Sorry about that gavinksong. I didn't mean to attribute the quote incorrectly. The quoting structure is more complex than it should be, yet I will be more careful, as you request. I didn't remove any brackets. I used the quote tool on the toolbar, but, apparantly, it has changed with the upgrade(s) to the site. Unlike the Spoiler tag, it didn't provide anywhere for a reference to the quote -- except within the quote. i just picked the wrong name.

And though the difference between 0 and 1 may seem to be trivial, it is not so trivial. 

Edited October 24, 2014 by DejMar

[gavinksong]

The tactic that k-man suggested in his last post is correct. He seemed to have very little faith in it, but carrying it out should reveal the solution.

[TimeSpaceLightForce]

If bob knows that alice know that he know that she know...so on, that is deterministic.

So better let decisions 1 & 2 be based on fair outcome roulette depending on the A1 apples in room1.The Ratio (reject/accept)=function (A1) ,

e.g. if R1=1/2 use 3way roulette for decision.When decision 1 is accept , if room2 has A2 apples >A1 , the Ratio (reject/accept)=function(A2,A1),

e.g. if R2=2/3 use 5way roulette for decision.

[gavinksong]

If bob knows that alice know that he know that she know...so on, that is deterministic.

So better let decisions 1 & 2 be based on fair outcome roulette depending on the A1 apples in room1.The Ratio (reject/accept)=function (A1) ,

e.g. if R1=1/2 use 3way roulette for decision.When decision 1 is accept , if room2 has A2 apples >A1 , the Ratio (reject/accept)=function(A2,A1),

e.g. if R2=2/3 use 5way roulette for decision.

I'm actually not quite sure what you mean, but I don't think that's the answer I had in mind.

[wolfgang]

can I ask a silly question?

Do we get the same answer, if we change the three rooms and apples with three positive numbers  written on three papers?

[gavinksong]

can I ask a silly question?

Do we get the same answer, if we change the three rooms and apples with three positive numbers written on three papers?

Yes, but they must all be different numbers.

[harey]

Bob can refine this strategy. Suppose:

a) the number of apples is limited to N (a very large one) and

b) Alice places places a random number of apples in each room

- if the number of apples in the first room is "small", Bob should refuse it

- if the number of apples in the first room "->N" and the number of apples in the second room is "just a little bit smaller than the number of apples in the first room", Bob should accept it

 

If we lift a), it will still apply.

 

Alice can counter this strategy by placing respectively K, K+1, K+2 apples. This brings us back to the strategy of k-man.

 

The mathematical formulation is left to the reader as exercise

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%.

Edited November 4, 2014 by harey

[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.