Maths Olympiad Prep

Library / 14-2j-m1 /1 of 2

14-2j-m1

Combinatorics Difficulty 6.2 National Olympiad Prove it Taiwan

Fix an integer k≥2k \ge 2. Two players, Ana and Banana, play the following game of numbers: Initially, some integer n≥kn \ge k gets written on the blackboard. Then they take moves in turn, with Ana beginning. A player making a move erases the number mm just written on the blackboard and replaces it by some number m′m' with k≤m′<mk \le m' < m that is coprime to mm. The first player who cannot move anymore loses.
An integer n≥kn \ge k is called good if Banana has a winning strategy when the initial number is nn, and bad otherwise.
Consider two integers n,n′≥kn, n' \ge k with the property that each prime number p≤kp \le k divides nn if and only if it divides n′n'. Prove that either both nn and n′n' are good or both are bad.

Solution

For convenience, let n→xn \to x denote the move of erasing nn and writing xx; by the rules, we must have n>x≥kn > x \ge k and (n,x)=1(n, x) = 1.

Claim A. If mm is a good number, and n>mn > m is coprime to mm, then nn is a bad number.
Proof. Because Ana only needs to choose n→mn \to m, and then copy Banana's winning strategy starting from mm.

Claim B. Any two good numbers cannot be coprime.
Proof. This follows immediately from Claim A and B.

Claim 1. If nn is a good number and n∣n′n|n', then n′n' is a good number.
Proof. If n′n' is a bad number, this means Ana can make the move n′→xn' \to x with xx being a good number. However, (n′,x)=1⇒(n,x)=1(n', x) = 1 \Rightarrow (n, x) = 1, but nn and xx are both good numbers, which contradicts Claim C.

Claim 2. If rsrs is a bad number, then r2sr^2s is also a bad number.
Proof. rsrs being a bad number means Ana can make the move rs→xrs \to x with xx being a good number, but xx is clearly coprime to r2sr^2s, so from r2s→xr^2s \to x we know r2sr^2s is a bad number.

Claim 3. If p>kp > k is a prime and n≥kn \ge k is a bad number, then npnp is also a bad number.
Proof. If not, then there exists a smallest bad number nn such that npnp is a good number. We derive a contradiction as follows.
1. Since nn is a bad number, Ana can make the move n→xn \to x, where xx is a good number. It is easy to see that (np,x)>1(np, x) > 1, otherwise npnp would be a bad number, a contradiction. But we know (n,x)=1(n, x) = 1, so p∣xp|x. Let x=pryx = p^r y, where (p,y)=1(p, y) = 1.
2. Note that y=1y = 1 is impossible, because if y=1y = 1, then x=prx = p^r; and since (p,k)=1(p, k) = 1, Ana can make the move x→kx \to k, so xx would be a bad number, a contradiction. Hence y>1y > 1, so there must exist a smallest positive integer α\alpha such that yα≥ky^\alpha \ge k.
3. Based on the fact that npnp and yαy^\alpha are coprime and npnp is a good number, by Claim B, yαy^\alpha must be a bad number.
4. By the minimality of α\alpha, we have yα<ky<py=xpr−1<npr−1y^\alpha < ky < py = \frac{x}{p^{r-1}} < \frac{n}{p^{r-1}}, so pr−1yα<np^{r-1}y^\alpha < n. Hence, by the minimality of nn, pr−1yαp^{r-1}y^\alpha must be a good number (because x=p(pr−1yα)x = p(p^{r-1}y^\alpha) is a good number). By the same argument, pr−2yα,…,yαp^{r-2}y^\alpha, \dots, y^\alpha must also all be good numbers.
5. But npnp and yαy^\alpha are both good numbers, so by Claim B, (np,yα)>1(np, y^\alpha) > 1, which contradicts (n,x)=1(n, x) = 1 and (p,y)=1(p, y) = 1. This completes the proof.

Now let Pk(x)P_k(x) denote the set of prime factors of xx that are less than or equal to kk. In what follows, we call two numbers a,ba, b similar if and only if Pk(a)=Pk(b)P_k(a) = P_k(b). To prove the original statement, we only need to show: if a,ba, b are similar, then a,ba, b are both good or both bad simultaneously. Note that abab is similar to both aa and bb at the same time, so this is equivalent to: if c≥kc \ge k is similar to some multiple dd of it, then c,dc, d are both good or both bad simultaneously.

proof If not, then there exists a smallest d0d_0 such that there exists a factor c0≥kc_0 \ge k of it such that c0,d0c_0, d_0 differ in being good or bad. By the Claims above, such a d0d_0 does not exist.

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

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.