Jump to content
BrainDen.com - Brain Teasers
  • 0

Paula and Victor play another guessing game


karthickgururaj
 Share

Question

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, (a1, a2, ..., an) (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 (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?

 

 

 

 

Link to comment
Share on other sites

5 answers to this question

Recommended Posts

  • 0

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 a0) and a1...an. The accuracy of the estimate depends on n and there are multiple different ways to do it. One way is to compute the average (aavg) of a0...an and assume S=2*aavg. Another way is to find the maximum (amax) of a0...an use the formula S=amax+amax/(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.

 

Link to comment
Share on other sites

  • 0

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 a0) and a1...an. The accuracy of the estimate depends on n and there are multiple different ways to do it. One way is to compute the average (aavg) of a0...an and assume S=2*aavg. Another way is to find the maximum (amax) of a0...an use the formula S=amax+amax/(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=amax+amax/(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 by DejMar
Link to comment
Share on other sites

  • 0

@k-man and @DejMar: you have poked a few holes into my question :)
 
Let me clarify:
a. The numbers a1, a2, ..an 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 by karthickgururaj
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...