# A game of guessing a chosen number

Your (honest) opponent choose a random number from 1 to 13 inclusive. You have to guess the number, and you win if the guess is correct. If not, your opponent either reduces the number chosen by one or increases it by 1, and you guess again.

The question is, what is the minimum # of attempts necessary to guarantee a win for you.

I am not able to get a handle on the problem.

Also, (a new variant just thought of), how many guesses should be allowed for a fair or "nearest to fair" game ?

-
Is opponent's decision to alter the number random ? –  Sasha Feb 18 '12 at 4:36
yes, (s)he can reduce by 1 or increase by 1 randomly. –  true blue anil Feb 18 '12 at 5:20
"Can reduce or increase" seems inconsistent with "randomly". Either your opponent changes it randomly, or is allowed to be strategic-perhaps even knowing your strategy. –  Ross Millikan Feb 18 '12 at 5:38
Well, to be fair, in the context of a guaranteed win (as opposed to a strong probability of winning), it doesn't really matter whether going up or down are "arbitrarily" and "randomly" chosen, since for every strategy, there's a chance of happening upon it randomly. I do agree with @Ross that they're normally very different things though. –  Yun William Yu Feb 18 '12 at 5:53
When your opponent change the number, is he allowed to move below 1 or above 13? –  GLG Feb 18 '12 at 6:06

The optimal strategy for $n=13$ odd is to try $2,\ldots,n-1=12$ first, which will catch the opponent if an only if she started on an even number; if the opponent is still not caught, one is sure she started on odd an is now (after $n-2=11$ moves) on an even number (in particular not on $n=13$), and trying $12,11,\ldots2$ is sure to catch her, for a total of $2*11=2n-4=22$ tries.

The same scheme works for $n=12$ even: try $2,\ldots,n-1=11$ first, which will catch the opponent if an only if she started on an even number; if she still not caught, one is sure she is now (after $n-2$ moves) again an odd number (in particular not on $n=12$), and trying $n-1=11,\ldots2$ is sure to catch the opponent, for a total of $2*10=2n-4=20$ tries.

Added: Here is the full anaylsis of the game. It clearly splits into two parallel games, one where the opponent starts odd and another where she starts even. The opponent chooses a game at the start and has to stick to it, but we don't know which it is, so we need to reduce to number of remaining potential positions in both games to $0$. On each move we remove one of the potential positions, but then the remaining possible positions are replaced by the set of all their neighbours; this also happens in the game we didn't play in. If one switches back-and-forth between games (playing game $A$, then at leat once game $B$ then again game $A$), then the before the second move in game $A$ the number of potential positions in game $A$ (if the first move didn't reduce it to $0$) has again grown to at least the same number it was before the previous move in $A$, so this gains nothing; an optimal strategy therefore should avoid such swithching. We must therefore choose a game to play in first, terminate that game entirely, and then start plaing in the other game.

Now focussing on one game (so the parity of the possibilities at each point in time is known), one may verify that the only type of move that actually reduces the number of remaining possibilities is where those possibilities form an "interval" (in the sense of the numbers of a given parity in a given interval) containing one of the extremities of the total set: by playing the other end of the interval, the possibilities are reduced to those of the opposite parity between the ends of the original interval. (The claim "only" is not entirely true: (1) whenever the possibilities have been reuced to a singleton, one can play that to reduce it to $0$, and (2) if $n$ is odd and all odd numbers remain possible, their number is bound to decrease regardless of our move. However these possibilities are marginal and do not affect our analysis.) After such a move one cannot reuce the number again on the next move, but by playing again on the same end of the (new) interval one can at least prepare do decrease it on the move after that.

There are four types of games, according to the parity of $n$ and of the initial possibilities. The two variants with $n$ even are left-right mirror images, and the "initial even" one can be won in $n-2$ moves by playing $2,3,\ldots,n-1$. So can the "initial even" game with $n$ odd. The game with $n$ odd and initial possibilities odd however needs $n-1$ moves: the very first move makes no difference whatsoever, and then the "initial even" game remains. Since we have the choice which game to play in first, and since for $n$ odd the "initial even" game requires an odd number of moves, we can play that first and have transformed the other game into another "initial even" game, so in the end we can still win in $2(n-2)$ moves, regardless of the parity of $n$.

-

EDIT: Not optimal because I didn't properly examine the boundaries. See Marc van Leeuwen's answer for a better analysis in 22 steps.

My strategy would be to sweep $G = \{g_i\} = \{1, 2, ..., 13, 1, 2, ..., 12\}$, requiring a total of 25 steps.

Why should this work?

Let $x_1$ be the initial number chosen by the opponent. Note that each move changes the number by exactly $\pm 1$. Thus, $x_{2i} - x_1$ is odd and $x_{2i+1} - x_1$ is even for $i \in \mathbb{N}$.

Case 1: $x_1$ is odd. Then the first sweep from $g_1$ to $g_{13}$ will succeed.

Note that since $x_1$ is odd, $x_{2i}$ must be even and $x_{2i+1}$ must be odd. Also note that in the first sweep, $g_{2i}$ is even and $g_{2i+1}$ is odd. Thus, $2|(x_i - g_i)$ for all $1\le i \le 13$.

Suppose $x_i < g_i$. Then at some point, $x_i = g_i - 1$ (since we are starting the sweep at $g_1 = 1$). However, that's a contradiction because we showed that the difference between $x_i$ and $g_i$ is always even. Thus, $x_i \ge g_i$ for $1 \le i \le 13$, which implies that we must succeed in the first sweep if $x_1$ is odd.

Case 2: $x_1$ is even. Then the first sweep will not succeed. However, the second sweep $g_{14}$ to $g_{25}$ will, because if $x_1$ is even, then $x_{14}$ must be odd. Thus, an identical argument as given above for case 1 holds. We don't need to check $13$ this time around because $x_i$ would have to be $12$ the previous step, which we're already checking. (strictly speaking, checking $13$ isn't necessary in the first round either for the same reason, but we need to waste a move before starting the second sweep)

Thus, at most 25 moves are necessary.

Since two sweeps are necessary to guarantee, 12 moves is a "nearest to fair" game, since that's what's required for a single sweep, making the result depend on whether the initial choice was even or odd.

-
This strategy works if 13 is replaced by any odd (positive) integer. Is there a winning strategy if 13 is replaced by an even number? –  Gerry Myerson Feb 18 '12 at 8:03
@GerryMyerson: The alternative strategy of trying $1,2,\ldots n,n,n-1,\ldots,2$ wins whether $n$ is even or odd. Actually the first $n$ is not necessary if $n$ is even; for $n$ odd it just serves the "regain opposition". –  Marc van Leeuwen Feb 18 '12 at 11:06
@GerryMyerson: Actually there is better, see my forthcoming answer. –  Marc van Leeuwen Feb 18 '12 at 11:49

One way to guarantee a win is to guess 13 twice, then 12 twice, then 11 twice, etc.

EDIT: Not quite. Back to the drawing board.

-
What if the opponent moves 8, 9, 10, 11, 12, 13, 12, 13, ... ? –  Yun William Yu Feb 18 '12 at 5:12
Oops. Never mind. –  Gerry Myerson Feb 18 '12 at 5:19

Here's my attempt but I'm not sure if this is optimal solution with least guesses, though. For $n=13$ odd.

First, let's assume that you have an "extra information" that the number is even. Then, you're first guessing $n-1$. If that's not the number, then you know the3 number's even and nor greater than $n-3$. This means that next number will be odd, and not greater than $n-2$. So you guess $n-2$. If that's not the number, it means that the number is odd and not greater than $n-4$. So, you're guessing for $n-4$ next, and so on. Keeping like this, if you don't guess the number meanwhile, you'll know that the number is even and not greater than $2$. So, you're guessing $2$ and your guess is correct. What we need to do now is how to get the "extra information".

Let's assume that in each of next guesses you din't guess correctly. Let's say each day you guess one number for easier understanding. First day, you guess $2$. Third day, the number will be $2$ iff first day it was $4$. But this means the number was $3$ the second day. o, second day you guess $2$, and thrid you guess $4$. This guarantees that the third day number wasn't $2$ or $4$. Let's take a look at the fifth day. That day, number can't be $2$, and it can be $4$ iff the third day it was $6$. But that means the forth day number was $5$. So, fourth and fifth day you guess $5$ and $6$. So, fifth day, the number is surely not $2$, $4$ or $6$. Keeping up like this, after $n-2$ days you will know that $n-2$nd day the number wasn't $2$, $4$, ..., $n-3$ or $n-1$. So this is strategy to get the "extra information", and after this you keep as in first paragraph.

So my guess is that for odd $n$, you must guess (if I counted guesses correctly) $(n-2)+(n-2)=2n-4=2*13-4=22$.

-