Tarik and Sultan are playing the following game. Tarik thinks of a number that is greater than . Then Sultan is telling a number greater than . If Tarik's number is divisible by Sultan's number, Sultan wins, otherwise Tarik subtracts Sultan's number from his number and Sultan tells his next number. Sultan is forbidden to repeat his numbers. If Tarik's number becomes negative, Sultan loses. Does Sultan have a winning strategy?
Solution
Yes, Sultan has winning strategies. Here are two examples:
First winning strategy. Sultan plays the following numbers in order: , , , , , , and he wins. Indeed, let be Tarik's number and assume that Sultan will not win before playing the last number .
- is not divisible by , so it is congruent to one of the twelve numbers , in modulo .
- is not divisible by , so it is congruent to one of the eight numbers , in modulo .
- is not divisible by , so it is congruent to one of the four numbers , in modulo .
- is not divisible by , so it is congruent to one of the two numbers , in modulo .
- is not divisible by and is congruent to in modulo .
- is not divisible by and is congruent to in modulo .
- Finally, Sultan ends up with , which is still a positive number divisible by , and Sultan wins.
Second winning strategy. Sultan plays the following numbers in order: , , , , , and he wins. Indeed, let be Tarik's number and assume that Sultan will not win before playing the last number .
- is not divisible by , so it is congruent to one of the six numbers , in modulo .
- is not divisible by , so it is congruent to one of the four numbers , in modulo .
- is not divisible by , so it is congruent to one of the two numbers , in modulo .
- is not divisible by , so it is congruent to in modulo .
- is not divisible by and is congruent to in modulo .
- Finally, Sultan ends up with , which is still a positive number divisible by , and Sultan wins.