Maths Olympiad Prep

Library / /127 of 133

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it Saudi Arabia

Tarik and Sultan are playing the following game. Tarik thinks of a number that is greater than 100100. Then Sultan is telling a number greater than 11. 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: 22, 33, 44, 66, 88, 2020, 2424 and he wins. Indeed, let n100n \geq 100 be Tarik's number and assume that Sultan will not win before playing the last number 2424.
- nn is not divisible by 22, so it is congruent to one of the twelve numbers 1,3,5,7,9,11,13,15,17,19,21,231,3,5,7,9,11,13,15,17,19,21,23, in modulo 2424.
- n2n-2 is not divisible by 33, so it is congruent to one of the eight numbers 1,5,7,11,13,17,19,231,5,7,11,13,17,19,23, in modulo 2424.
- n5=(n2)3n-5=(n-2)-3 is not divisible by 44, so it is congruent to one of the four numbers 2,10,14,222,10,14,22, in modulo 2424.
- n9=(n5)4n-9=(n-5)-4 is not divisible by 66, so it is congruent to one of the two numbers 10,2210,22, in modulo 2424.
- n15=(n9)6n-15=(n-9)-6 is not divisible by 88 and is congruent to 44 in modulo 2424.
- n23=(n15)8n-23=(n-15)-8 is not divisible by 2020 and is congruent to 2020 in modulo 2424.
- Finally, Sultan ends up with n430mod24n-43 \equiv 0 \bmod 24, which is still a positive number divisible by 2424, and Sultan wins.

Second winning strategy. Sultan plays the following numbers in order: 22, 33, 44, 66, 1616, 1212 and he wins. Indeed, let n100n \geq 100 be Tarik's number and assume that Sultan will not win before playing the last number 1212.
- nn is not divisible by 22, so it is congruent to one of the six numbers 1,3,5,7,9,111,3,5,7,9,11, in modulo 1212.
- n2n-2 is not divisible by 33, so it is congruent to one of the four numbers 1,5,7,111,5,7,11, in modulo 1212.
- n5=(n2)3n-5=(n-2)-3 is not divisible by 44, so it is congruent to one of the two numbers 2,102,10, in modulo 1212.
- n9=(n5)4n-9=(n-5)-4 is not divisible by 66, so it is congruent to 1010 in modulo 1212.
- n15=(n9)6n-15=(n-9)-6 is not divisible by 1616 and is congruent to 44 in modulo 1212.
- Finally, Sultan ends up with n310mod12n-31 \equiv 0 \bmod 12, which is still a positive number divisible by 1212, and Sultan wins.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.