Fun Game Theory, Guessing a Number With a Twist

[Canada_Whiz]

Fun Game Theory, Guessing a Number With a "Twist"

You and I are playing a game. I begin by picking an integer from 1 to 2011 (inclusive). On each turn you try to guess my number. I then tells you whether your guess is too high, too low, or correct. If your guess is not correct, I add or subtracts 1 from my number (always constructing a new number from 1 to 2011). Assuming you play optimally, what is the minimum number of turns you need to guarantee that you will guess my number?

I know that if I DIDNT change my number each time, it would take 11 turns for you to guess my number. I also know that the optimal strategy is picking a number directly in the middle each time. But the problem is, suppose you chose 1006 first. Then my number could be 1005, and I would tell you "too high" But my new number could in fact be 1006!

Help is MUCH appreciated!

 

[grief]

If you think about it, a change of +-1 doesn't much matter. Suppose I guess 1006, and am told "too high." In the traditional game, I would conclude the number I have to guess next lies between 1 and 1005. Now I would conclude the number I have to guess next lies between 1 and 1006. So I would guess the middle of that interval, and continue like that, each time taking into account the possibility that the number has changed by +-1.

The problem is what happens when your guessing interval is small enough. For example, suppose I know the number is between 3 and 6. I guess 5. I am told 5 is too high. My new guessing range is 2 to 5, the same range, only shifted.

Similarly, suppose I narrowed it down to two numbers, 3 and 4. I guess 4. I am told that's wrong. Then I know the number was 3. So next, it will be either 2 or 4-- again I have to guess between two numbers.

In these cases, it seems the only strategy is to "chase the numbers down," force the numbers to one of the ends, because if, for example, you narrowed it down to either the numbers 1 or 2, you guess 2. If you're wrong, you know the number was 1, but since you can't subtract 1 from 1 in this game, you know the next number will be 2.

 

[hgfalling]

I think the answer is 1007 turns. You have to force the opponent to an end to catch him.

WLOG suppose you know he is at a location x < 1006. Then you can force him to the nearest side by simply playing x+1. He must go to x-1 to avoid capture, so you next play x, and so on. Eventually he is at 2, and you play 3, and then you capture him next turn. So if he starts at x, he is captured in x turns.

When you start, however, you don't know where he is. Nevertheless, suppose you pick 1006 and he is lower. Then you play 1005, and so on. At some point, he can cross you (such that he is now higher). But then you know exactly where he is (in the spot you just vacated). So you return to your current location + 2 and lose two turns. So since he must start at a location no more than 1005, he can be captured in no more than 1007 turns.

 

[Canada_Whiz]

Thanks guys! But can anyone provide a rigorous proof? For example, hgfall, you proved that i can always guess the number in 1007 moves, but you haven't proved that is the ABSOLUTE MINIMUM number of moves for which I am guaranteed to guess the number.

So a rigorous proof would be appreciated =)

 

[Tedjn]

We would like to show that every algorithm requires at least 1008 guesses. (I believe if you walk through hgfalling's argument, it requires at least 1008 since you lose 3 moves.) Unless I am missing some easy argument, a rigorous proof for this seems kind of annoying, and I'm not sure how to go about it exactly. You can use this easy lemma:

Lemma. If at some point the current actual number is 1006, then you need at least 1006 guesses after that to finish.

Proof. After each guess, the current number x either increases or decreases by 1. We can only guarantee that the next guess is correct if x is 1 or 2011. Otherwise, there will always be two choices for the subsequent x, and we can never be sure we will guess right. Suppose that at some point x is equal to 1006. Then, we need at least 1005 guesses before x reaches 1 or 2011, then another one to finish correctly. That is, after x is 1006, we need at least 1006 guesses to guarantee finishing the game.

To see that we need two more guesses afterward, we might need to break our guessing algorithms down into cases and try to construct sequences of x values based on the guesses made by the algorithm; this may be complicated, I don't know.

In any case, this is an interesting question. Where did you find it?