2
$\begingroup$

I have no clue how to answer this question. This is 2002 Putnam examination question B-4.

B4 An integer $n$, unknown to you, has been randomly chosen in the interval $[1,2002]$ with uniform probability. Your objective is to select $n$ in an odd number of guesses. After each incorrect guess, you are informed whether $n$ is higher or lower, and you must guess an integer on your next turn among the numbers that are still feasibly correct. Show that you have a strategy so that the chance of winning is greater than $\frac23$.

Frankly speaking, I didn't understand the phrase 'an odd number of guesses'.

For example, if n is 1000, and I guess 10 in my 1st attempt, then I will be informed that n is higher than that number.

In the 2nd attempt, if I guess 1000, then it would be a correct guess. That means I correctly guessed $n=1000$ in an even number of guesses.

Is this understanding correct?

I have a solution to this problem but I didn't understand it. There are 4 points given in the solution. But as the problem is unclear to me, solution is obviously unclear to me. The solution is as follows:-

PUTNAM EXAM 2002,B-4

If any member understands the given solution correctly, may reply with the correct explanations of all the 4 points.

$\endgroup$
  • $\begingroup$ You appear to understand what the question is asking correctly. However, if you have a solution in hand, why say nothing about it? $\endgroup$ – Glen_b -Reinstate Monica Nov 30 '19 at 23:33
  • 1
    $\begingroup$ The solution given here: kskedlaya.org/putnam-archive seems fairly straightforward. Can you identify what is unclear? It might pay to examine a smaller version of the problem (say on the range $[1,22]$) by hand using the proposed approach. (Note, however, that the solution relies on some assumptions that are not given in the question.) $\endgroup$ – Glen_b -Reinstate Monica Nov 30 '19 at 23:36
3
$\begingroup$

This is the approach used in the previous solution that I linked to in your question, but discussed on a smaller set of numbers. Your present solution uses the same approach but adds a lot of unnecessary discussion in parts 1-3. This discusses what is in your section 4 (grouping values on their remainder when dividing by 3, skipping one of the groups, but where the group left out is carefully chosen).

Consider a small range like $[1,22]$. You guess in order: $1,\color{red}{3},4,\color{red}{6},7,\color{red}{9},10,\color{red}{12},13,\color{red}{15},16,\color{red}{18},19,\color{red}{21},22$ (that is, you make increasing guesses alternating between numbers of the form $3k-2$ and $\color{red}{3k}$ for $k=1,2,...$) until you either guess correctly or you overshoot $n$ (make a guess that's too high). You omit the numbers one less than a multiple of 3, being $\color{blue}{2,5,8,11,14,17,20}$. If $n$ is $\color{red}{\text{red}}$ (i.e. a multiple of 3) then you will get it in an even number of guesses. If $n$ is $\text{black}$, you'll get it in an odd number of guesses. If $n$ is $\color{blue}{\text{blue}}$, you will have made an even number of guesses at the point that you guess the first number larger than it, at which point you will guess the correct blue number on an odd guess.

Since 7/22 of the numbers are red and 15/22 of the numbers are black or blue, you have slightly better than 2/3 chance of getting $n$ on an odd guess.

The original problem is the same, just with a lot more numbers.

What the solution assumes but does not anywhere state is that all of the numbers in the range are equally likely to be $n$ (since that's what justifies dividing the number of values in the color classes by the total number of values).

$\endgroup$
  • $\begingroup$ ,I have provided the solution with all the 4 points. You may explain all the 4 points. My next question is what is the meaning of $ n \equiv 1$ mod 3? $\endgroup$ – Dhamnekar Winod Dec 1 '19 at 13:23
  • $\begingroup$ See en.wikipedia.org/wiki/Modular_arithmetic $\endgroup$ – Glen_b -Reinstate Monica Dec 1 '19 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.