Paula and Victor play another guessing game

[karthickgururaj]

Taking off from bonanova's recent post (), a different version of the game is played by Paula and Victor.

 

Paula first selects S, an arbitrary positive integer (> 0). S can be as small or as large as Paula wants it to be. Paula doesn't reveal S to Victor.

 

Paula then selects n integers randomly, (a₁, a₂, ..., a_n) (n > 0), with a uniform probability distribution on the interval [1, S]. She tells these numbers to Victor.

 

Then she selects two more integers x and y, again randomly with uniform probability distribution in the same interval.

 

Victor has to decide whether he wants to know the value of x or y. After Victor has made his choice and told Paula, Paula first asks Victor - "A. Guess whether the number I'm going to tell you now is less than S/2 or more than S/2". After Victor answers, Paula doesn't reveal whether he is right or wrong. She instead tells the value of the number. Next she asks, "B. Guess whether the other number is smaller or larger when compared to the one I revealed". After Victor answers, Paula reveals the value of the second number and S (so Victor knows whether his guesses were right or not).

 

Puzzle: What would be Victor's strategy for both the guesses? What would be his chance of winning the first guess?

 

 

 

 

[karthickgururaj]

For (A), one approach would be to estimate S, based on a₁ to a_n.

[k-man]

A: For even S, there are S/2 numbers in [1,S] range that are greater than S/2, one number that is equal to S/2 and S/2-1 numbers that are less than S/2. If the OP is rephrased so that the first guess is for "not greater than" instead of "less than" then there is exactly 50% chance for the first guess for any even S. In the current phrasing, there a small bias toward x or y to be greater than S/2.

For odd S, the range [1,(S-1)/2] has one less number than range [(S+1)/2,S], so there is a higher chance that x or y is greater than S/2 for odd S.

Conclusion: Victor should always guess that the first number he picks is greater than S/2.

B: Estimate S based on the revealed number (let's call it a₀) and a₁...a_n. The accuracy of the estimate depends on n and there are multiple different ways to do it. One way is to compute the average (a_avg) of a₀...a_n and assume S=2*a_avg. Another way is to find the maximum (a_max) of a₀...a_n use the formula S=a_max+a_max/(n+1)-1. (For other methods to estimate S see http://en.wikipedia.org/wiki/German_tank_problem)

Given the estimate of S and the revealed number, Victor should answer "smaller" if the number revealed is greater that half the estimate of S and "larger" otherwise.

 

[DejMar]

A: For even S, there are S/2 numbers in [1,S] range that are greater than S/2, one number that is equal to S/2 and S/2-1 numbers that are less than S/2. If the OP is rephrased so that the first guess is for "not greater than" instead of "less than" then there is exactly 50% chance for the first guess for any even S. In the current phrasing, there a small bias toward x or y to be greater than S/2.

For odd S, the range [1,(S-1)/2] has one less number than range [(S+1)/2,S], so there is a higher chance that x or y is greater than S/2 for odd S.

Conclusion: Victor should always guess that the first number he picks is greater than S/2.

B: Estimate S based on the revealed number (let's call it a₀) and a₁...a_n. The accuracy of the estimate depends on n and there are multiple different ways to do it. One way is to compute the average (a_avg) of a₀...a_n and assume S=2*a_avg. Another way is to find the maximum (a_max) of a₀...a_n use the formula S=a_max+a_max/(n+1)-1. (For other methods to estimate S see http://en.wikipedia.org/wiki/German_tank_problem)

Given the estimate of S and the revealed number, Victor should answer "smaller" if the number revealed is greater that half the estimate of S and "larger" otherwise.

 

There is no specification that the numbers are distinct, yet an implication that they must be. If the numbers do not need be distinct, it is possible for no number to be less and all to be more than s/2. (This can occur if s = 1). For this specific instance, an answer of "more" will always be a 'win' for Victor. In this instance, the hypothesis that Victor should answer "less" if the number revealed is greater that half the estimate of S and "more" otherwise will be correct, as Victor will always answer "more". S=2*a

_avg=2, and the revealed number R=1, R=S/2. But for the given estimate S=a_max+a_max/(n+1)-1, S<=1, and the revealed number R=1, R>=S/2 (yet, considering probability, as n's upper value is unbounded in the positive integers, R>S/2), the hypothesis will be incorrect (though the hypothesis may hold true for most arbitrarily chosen s).

Given the phrasing "Paula then selects n integers....She tells these numbers....", and "...selects two more integers....", there is an implication that s must be greater than 2. By this implication, I believe your analysis, k-man, is generally correct. But is it correct if x and y do not need be distinct? And, other than the case where s = 1, is it correct if s = 2?

 

Edited November 10, 2014 by DejMar

[k-man]

Guilty. I didn't consider edge cases at all and assumed that all the numbers are distinct.

 

then some of the methods for estimation of S are not applicable, although I think that the rest of this approach should generally still work.

[karthickgururaj]

@k-man and @DejMar: you have poked a few holes into my question
 
Let me clarify:
a. The numbers a₁, a₂, ..a_n and x, y can have duplicates. Each number is picked using a function like, rand(1, S), which gives a random integer in the specified range.
b. S is always even (this is the easiest way to escape the mid-point issue pointed out in your post). The first question is now modified as: "A. Guess whether the number I'm going to tell you now is (less than or equal to S/2)  or (more than S/2)". I think S = 2 case must be allowed as well.

 

Would your responses change then?

 
@k-man, thanks for the wikipedia link - was interesting to read. It doesn't apply here (at least not directly) because we can have repeats - as you have pointed out yourself.

Edited November 11, 2014 by karthickgururaj