A Fair Game?
Mursalin and Trevor decide to play a game where Trevor gets to pick any positive integer n < 1 0 0 0 .
After that the game begins.
First Mursalin names an integer x from 1 to n [both inclusive]. Then Trevor has to name an integer from 1 to n [both inclusive] that does not divide x . Then it's Mursalin's turn again and so on. On each turn the player has to select an integer from 1 through n [both inclusive] that doesn't divide all the numbers selected so far. The first person unable to name an integer under these constraints loses. Assuming that both players play optimally, for how many n 's does Mursalin have a winning strategy?
The answer is 999.
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.
2 solutions
Yes, That is called the strategy stealing argument.
@Mursalin Habib I do not get it. What would you do if n=1,2?
Log in to reply
If n = 1 , I name 1 . Since there is no integer left, Trevor loses.
If n = 2 , I name 2 . Trevor can't pick 1 since 1 divides 2 and he loses.
The thing is, you don't have to explicitly find the winning strategy for each individual n to prove that Mursalin always wins. The assumption that Trevor has a winning strategy leads to a contradiction. See @Ivan Koswara 's solution for more details.
Log in to reply
But doesn't 1 divide 1? How can you pick it when n=1?
Log in to reply
@Agnishom Chattopadhyay – You cannot pick numbers that have been picked before. For your first move, you can pick 1 , since there's no previous number for 1 to divide into. For any subsequent move, you cannot pick 1 , as it divides any number that has been picked before. The value of n is unrelated to this.
@Agnishom Chattopadhyay – The game starts after Trevor has picked n .
n just determines the maximum integer someone can pick.
Log in to reply
@Mursalin Habib – I wish I read the pronlem more carefully
n = 1 is trivial.
For n ≥ 2 , think of it this way. Suppose Trevor can win. Then if Mursalin plays 1 , Trevor has a winning response m . But now consider what happens if Mursalin plays m . Trevor cannot have a winning response, as the situation is identical to the previous one (if Mursalin plays 1 and Trevor replies with m ), but now with reversed sides, so Mursalin is the one holding the winning response.
For n = 4 (the smallest non-trivial example I can think of), suppose Trevor can win. Then if Mursalin plays 1 , Trevor has a winning response m (in this case m = 2 ; the remaining moves are 3 and 4 , and Trevor is guaranteed to choose the last integer and thus the last move). But what happens if Mursalin had played m = 2 initially? Now Trevor cannot win. So our assumption that Trevor can win is wrong, and indeed Mursalin should be able to win.
Another example, n = 3 . Suppose Trevor can win. If Mursalin plays 1 , turns out Trevor cannot win after all! (Only moves are 2 and 3 , so Mursalin gets the last move.) So clearly our assumption that Trevor can win is wrong, since Mursalin wins by playing 1 .
mursalin will choose 2! or 3! or 4! or 5! or 6! to win..so for any n <1000 mursalin can pick any of those six integers..so total number of n=999
I don't think you understood the problem.
If Mursalin picks 6 ! , Trevor can choose 7 and he's still in the game.
Mursalin wins all the time.
Note that the game must end, since the integers that have been picked can no longer be picked, and there are only finitely many integers available. In addition, one person has to win, since there is no draw.
Suppose Trevor has a winning strategy. Mursalin can begin by playing 1 . By our assumption, Trevor has a winning strategy by playing m . But then Mursalin could have also started with m and follows the same strategy; this necessarily wins for Mursalin, since Trevor can no longer reply with 1 , and thus this is the same situation as the first one (Mursalin plays 1 followed with Trevor playing m ), only with players reversed. Thus our assumption that Trevor has a winning strategy is a contradiction, so Mursalin has a winning strategy all the time.
There are 9 9 9 positive integers less than 1 0 0 0 , and thus that's our answer.