Fun Game Theory, Guessing a Number With a Twist

In summary, the minimum number of turns needed to guarantee guessing the number in this game is 1007. This is achieved by forcing the opponent to one end of the guessing range and then capturing them in the next turn. Any algorithm that does not force the opponent to an end will require at least 1008 turns, as proven by the lemma provided.
  • #1
Canada_Whiz
14
0
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!
 
Physics news on Phys.org
  • #2


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.
 
  • #3


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.
 
  • #4


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 =)
 
  • #5


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?
 

1. What is Fun Game Theory?

Fun Game Theory is a branch of mathematics that deals with the study of strategic decision-making in games. It involves analyzing and predicting the behavior of players in various games and determining the optimal strategies for winning.

2. What is the "Guessing a Number With a Twist" game?

The "Guessing a Number With a Twist" game is a mathematical game where one player chooses a secret number and the other player has to guess it within a certain number of tries. However, in this game, the secret number changes after each guess, making it more challenging and strategic.

3. How does this game differ from traditional guessing games?

This game differs from traditional guessing games because the secret number changes after each guess, making it more unpredictable and requiring players to think strategically in order to win. It also adds an element of excitement and surprise to the game.

4. What are some key strategies for winning this game?

Some key strategies for winning this game include keeping track of previous guesses, using probability to narrow down the possible range of numbers, and taking calculated risks by choosing numbers that have not been guessed yet.

5. What real-world applications does Fun Game Theory have?

Fun Game Theory has various real-world applications, including in economics, politics, and sports. It can be used to analyze and predict the behavior of individuals and groups in competitive situations and make strategic decisions based on that analysis.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
2
Views
870
  • Precalculus Mathematics Homework Help
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
11
Views
2K
  • Precalculus Mathematics Homework Help
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
6
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
297
Replies
9
Views
887
  • Engineering and Comp Sci Homework Help
Replies
4
Views
968
  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
1K
Back
Top