Maths Olympiad Prep

Library / /43 of 43

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it JBMO

Problem:

An economist and a statistician play a game on a calculator which does only one operation. The calculator displays only positive integers and it is used in the following way: Denote by nn an integer that is shown on the calculator. A person types an integer, mm, chosen from the set {1,2,,99}\{1,2, \ldots, 99\} of the first 99 positive integers, and if m%m \% of the number nn is again a positive integer, then the calculator displays m%m \% of nn. Otherwise, the calculator shows an error message and this operation is not allowed. The game consists of doing alternatively these operations and the player that cannot do the operation loses. How many numbers from {1,2,,2019}\{1,2, \ldots, 2019\} guarantee the winning strategy for the statistician, who plays second?

For example, if the calculator displays 1200, the economist can type 50, giving the number 600 on the calculator, then the statistician can type 25 giving the number 150. Now, for instance, the economist cannot type 75 as 75%75 \% of 150 is not a positive integer, but can choose 40 and the game continues until one of them cannot type an allowed number.

Solutions — 2

Solution 1

Solution:

First of all, the game finishes because the number on the calculator always decreases. By picking m%m \% of a positive integer nn, players get the number
mn100=mn2252 \frac{m \cdot n}{100} = \frac{m \cdot n}{2^{2} 5^{2}}
We see that at least one of the powers of 2 and 5 that divide nn decreases after one move, as mm is not allowed to be 100, or a multiple of it. These prime divisors of nn are the only ones that can decrease, so we conclude that all the other prime factors of nn are not important for this game. Therefore, it is enough to consider numbers of the form n=2k5n = 2^{k} 5^{\ell} where k,N0k, \ell \in \mathbb{N}_{0}, and to draw conclusions from these numbers.

We will describe all possible changes of kk and \ell in one move. Since 53>1005^{3} > 100, then \ell cannot increase, so all possible changes are from \ell to +b\ell + b, where b{0,1,2}b \in \{0, -1, -2\}. For kk, we note that 26=642^{6} = 64 is the biggest power of 2 less than 100, so kk can be changed to k+ak + a, where a{2,1,0,1,2,3,4}a \in \{-2, -1, 0, 1, 2, 3, 4\}. But the changes of kk and \ell are not independent. For example, if \ell stays the same, then mm has to be divisible by 25, giving only two possibilities for a change (k,)(k2,)(k, \ell) \rightarrow (k-2, \ell), when m=25m=25 or m=75m=75, or (k,)(k1,)(k, \ell) \rightarrow (k-1, \ell), when m=50m=50. Similarly, if \ell decreases by 1, then mm is divisible exactly by 5 and then the different changes are given by (k,)(k+a,1)(k, \ell) \rightarrow (k+a, \ell-1), where a{2,1,0,1,2}a \in \{-2, -1, 0, 1, 2\}, depending on the power of 2 that divides mm and it can be from 202^{0} to 242^{4}. If \ell decreases by 2, then mm is not divisible by 5, so it is enough to consider when mm is a power of two, giving changes (k,)(k+a,2)(k, \ell) \rightarrow (k+a, \ell-2), where a{2,1,0,1,2,3,4}a \in \{-2, -1, 0, 1, 2, 3, 4\}.

We have translated the starting game into another game with changing (the starting pair of non-negative integers) (k,)(k, \ell) by moves described above and the player who cannot make the move loses, i.e. the player who manages to play the move (k,)(0,0)(k, \ell) \rightarrow (0,0) wins. We claim that the second player wins if and only if 3k3 \mid k and 33 \mid \ell.

We notice that all moves have their inverse modulo 3, namely after the move (k,)(k+a,+b)(k, \ell) \rightarrow (k+a, \ell+b), the other player plays (k+a,+b)(k+a+c,+b+d)(k+a, \ell+b) \rightarrow (k+a+c, \ell+b+d), where
(c,d){(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)} (c, d) \in \{(0,-1), (0,-2), (-1,0), (-1,-1), (-1,-2), (-2,0), (-2,-1), (-2,-2)\}
is chosen such that 3a+c3 \mid a+c and 3b+d3 \mid b+d. Such (c,d)(c, d) can be chosen as all possible residues different from (0,0)(0,0) modulo 3 are contained in the set above and there is no move that keeps kk and \ell the same modulo 3. If the starting numbers (k,)(k, \ell) are divisible by 3, then after the move of the first player at least one of kk and \ell will not be divisible by 3, and then the second player will play the move so that kk and \ell become divisible by 3 again. In this way, the first player can never finish the game, so the second player wins. In all other cases, the first player will make such a move to make kk and \ell divisible by 3 and then he becomes the second player in the game, and by previous reasoning, wins.

The remaining part of the problem is to compute the number of positive integers n2019n \leqslant 2019 which are winning for the second player. Those are the nn which are divisible by exactly 23k53, k,N02^{3k} 5^{3\ell},\ k, \ell \in \mathbb{N}_{0}. Here, exact divisibility by 23k532^{3k} 5^{3\ell} in this context means that 23kn2^{3k} \| n and 53n5^{3\ell} \| n, even for =0\ell=0, or k=0k=0. For example, if we say that nn is exactly divisible by 8, it means that 8n,16n8 \mid n, 16 \nmid n and 5n5 \nmid n. We start by noting that for each ten consecutive numbers, exactly four of them are coprime to 10. Then we find the desired amount by dividing 2019 by numbers 23k532^{3k} 5^{3\ell} which are less than 2019, and then computing the number of numbers no bigger than 201923k53\left\lfloor \frac{2019}{2^{3k} 5^{3\ell}} \right\rfloor which are coprime to 10.

First, there are 4201+4=8084 \cdot 201 + 4 = 808 numbers (out of positive integers n2019n \leqslant 2019) coprime to 10. Then, there are 20198=252\left\lfloor \frac{2019}{8} \right\rfloor = 252 numbers divisible by 8, and 254+1=10125 \cdot 4 + 1 = 101 among them are exactly divisible by 8. There are 201964=31\left\lfloor \frac{2019}{64} \right\rfloor = 31 numbers divisible by 64, giving 34+1=133 \cdot 4 + 1 = 13 divisible exactly by 64. And there are two numbers, 512 and 35123 \cdot 512, which are divisible by exactly 512. Similarly, there are 2019125=16\left\lfloor \frac{2019}{125} \right\rfloor = 16 numbers divisible by 125, implying that 4+2=64 + 2 = 6 of them are exactly divisible by 125. Finally, there is only one number divisible by exactly 1000, and this is 1000 itself. All other numbers that are divisible by exactly 23k532^{3k} 5^{3\ell} are greater than 2019. So, we obtain that 808+101+13+2+6+1=931808 + 101 + 13 + 2 + 6 + 1 = 931 numbers not bigger than 2019 are winning for the statistician.

Solution 2

Alternative Solution by PSC:

Let us call a positive integer nn losing if n=2r5skn = 2^{r} 5^{s} k where rs0mod3r \equiv s \equiv 0 \bmod 3 and (k,10)=1(k, 10) = 1. We call all other positive integers winning.

Lemma 1. If nn is losing, then mn100\frac{m n}{100} is winning for all m{1,2,,99}m \in \{1,2, \ldots, 99\} such that 100mn100 \mid m n.

Proof of Lemma 1. Let m=2t5ukm = 2^{t} 5^{u} k'. For mn100\frac{m n}{100} to be losing, we would need tu2mod3t \equiv u \equiv 2 \bmod 3. But then m100m \geqslant 100, a contradiction.

Lemma 2. If nn is winning, then there is an m{1,2,,99}m \in \{1,2, \ldots, 99\} such that 100mn100 \mid m n and mn100\frac{m n}{100} is losing.

Proof of Lemma 2. Let n=2r5skn = 2^{r} 5^{s} k where (k,10)=1(k, 10) = 1. Pick t,u{0,1,2}t, u \in \{0,1,2\} such that t(2r)mod3t \equiv (2-r) \bmod 3 and u(2s)mod3u \equiv (2-s) \bmod 3 and let m=2t5um = 2^{t} 5^{u}. Then 100mn100 \mid m n and mn100\frac{m n}{100} is losing. Furthermore m<100m < 100 as otherwise m=100,t=u=2m = 100, t = u = 2 giving rs0mod3r \equiv s \equiv 0 \bmod 3 contradicting the fact that nn was winning.

Combining Lemmas 1 and 2 we obtain that the second player wins if and only if the game starts from a losing number.

The remaining part of the problem is to compute the number of positive integers n2019n \leqslant 2019 which are winning for the second player. Those are the nn which are divisible by exactly 23k53, k,N02^{3k} 5^{3\ell},\ k, \ell \in \mathbb{N}_{0}. Here, exact divisibility by 23k532^{3k} 5^{3\ell} in this context means that 23kn2^{3k} \| n and 53n5^{3\ell} \| n, even for =0\ell=0, or k=0k=0. For example, if we say that nn is exactly divisible by 8, it means that 8n,16n8 \mid n, 16 \nmid n and 5n5 \nmid n. We start by noting that for each ten consecutive numbers, exactly four of them are coprime to 10. Then we find the desired amount by dividing 2019 by numbers 23k532^{3k} 5^{3\ell} which are less than 2019, and then computing the number of numbers no bigger than 201923k53\left\lfloor \frac{2019}{2^{3k} 5^{3\ell}} \right\rfloor which are coprime to 10.

First, there are 4201+4=8084 \cdot 201 + 4 = 808 numbers (out of positive integers n2019n \leqslant 2019) coprime to 10. Then, there are 20198=252\left\lfloor \frac{2019}{8} \right\rfloor = 252 numbers divisible by 8, and 254+1=10125 \cdot 4 + 1 = 101 among them are exactly divisible by 8. There are 201964=31\left\lfloor \frac{2019}{64} \right\rfloor = 31 numbers divisible by 64, giving 34+1=133 \cdot 4 + 1 = 13 divisible exactly by 64. And there are two numbers, 512 and 35123 \cdot 512, which are divisible by exactly 512. Similarly, there are 2019125=16\left\lfloor \frac{2019}{125} \right\rfloor = 16 numbers divisible by 125, implying that 4+2=64 + 2 = 6 of them are exactly divisible by 125. Finally, there is only one number divisible by exactly 1000, and this is 1000 itself. All other numbers that are divisible by exactly 23k532^{3k} 5^{3\ell} are greater than 2019. So, we obtain that 808+101+13+2+6+1=931808 + 101 + 13 + 2 + 6 + 1 = 931 numbers not bigger than 2019 are winning for the statistician.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.