Reach 100
Dan and Sam play a game in which the first to start says the number 1, the next says 2, and the one who's next must say an integer strictly between the previous number and twice of it (not including the endpoints).
For example, Dan begins saying 1, then Sam says 2. Dan's options are now all integers between 2 and 4, exclusive. But there's only one such option, 3, so Dan is forced to say 3. Sam's options are now between 3 and 6, which are 4 and 5.
The game finishes when someone says 100 or greater; that player wins.
If Dan begins, who will win, assuming both players play optimally?
This is the first problem of the set Winning Strategies .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Easily we can deduce that the one who says 5 0 , wins, as the next can say at least 5 1 and at most 9 9 , and then, the one who said 5 0 says 1 0 0 and wins. Analyzing backwards the numbers that winner must have told, we have found a winner position: if someone says 5 0 , will win. So, now the problem is who will say 5 0 first, that is, who has that winner strategy? Again, we can easily deduce that the one who says 2 5 , wins; and, who's the first one to say 2 5 ? The one who says 1 2 , therefore, the one who says 6 , then, the one who says 3 , thus, the one who says 1 ... but Dan begins with the number 1 ! Hence, he will always win playing optimally, as follows:
Dan begins saying 1 , then Sam says 2 , then Dan says 3 , then Sam says 4 or 5 and, after this, Dan must say the double of the number he said in his previous turn; that is, 6 , then 1 2 . At this point, he should not say 2 4 , because he wants to reach 1 0 0 before Sam, and we had concluded that, in order to win, he must say the half of the goal number before his opponent, and so the half of the half, and so on. Thus, he says 2 5 , then Sam says any number between 2 5 and 5 0 , then Dan replies 5 0 (like bounding the possible numbers that Sam can say), then Sam says a number, but it does not matter, Dan says 1 0 0 !
I will post a note analyzing the general game and its possible situations and variations.