Maths Olympiad Prep

Library / /420 of 520

Number theory Difficulty 7.4 National olympiad, round 2 Find the answer

Given integer n3n \geq 3. 1,2,,n1, 2, \ldots, n were written on the blackboard. In each move, one could choose two numbers x,yx, y, erase them, and write down x+y,xyx + y, |x-y| in the place of x,yx, y. Find all integers XX such that one could turn all numbers into XX within a finite number of moves.

A number or a short expression. Spacing and $ signs are ignored.

Solution

1. Initial Observations:
- We start with the numbers 1,2,,n1, 2, \ldots, n on the blackboard.
- In each move, we can choose two numbers xx and yy, erase them, and write down x+yx + y and xy|x - y|.
- We need to determine all integers XX such that all numbers can be turned into XX within a finite number of moves.

2. Necessary Conditions:
- Consider the largest number on the blackboard at any point in time. This number either increases or stays constant.
- Initially, the largest number is nn. Therefore, the final number XX must be at least nn, i.e., XnX \geq n.

3. Divisibility by Odd Primes:
- Suppose XX is divisible by an odd prime pp. Consider reversing the operations on the final tuple (X,X,,X)(X, X, \ldots, X).
- The reverse operation is (a,b)(a+b2,ab2)(a, b) \mapsto \left(\frac{a+b}{2}, \frac{|a-b|}{2}\right).
- If pp divides XX, then pp must divide all numbers on the blackboard at all times. This is impossible since 11 was on the board initially.
- Therefore, XX cannot be divisible by any odd prime, implying XX must be a power of 2.

4. Sufficient Conditions:
- Let \ell be the smallest positive integer such that 2n2^\ell \geq n.
- We need to show that (2m,2m,,2m)(2^m, 2^m, \ldots, 2^m) is attainable whenever mm \geq \ell.

5. Doubling Technique:
- We can perform the operation (x,y)(x+y,xy)(2x,2y)(x, y) \mapsto (x+y, |x-y|) \mapsto (2x, 2y).
- Specifically, (0,x)(0,2x)(0, x) \mapsto (0, 2x), meaning that as long as there is a zero in the tuple, any arbitrary number can be doubled.

6. Inductive Step:
- Suppose we can reach (2x,2x,,2x)(2^x, 2^x, \ldots, 2^x). Then:
(2x,2x,,2x)(0,2x+1,2x,2x,,2x)(0,2x+1,2x+1,,2x+1)(2x+1,2x+1,,2x+1) (2^x, 2^x, \ldots, 2^x) \mapsto (0, 2^{x+1}, 2^x, 2^x, \ldots, 2^x) \mapsto (0, 2^{x+1}, 2^{x+1}, \ldots, 2^{x+1}) \mapsto (2^{x+1}, 2^{x+1}, \ldots, 2^{x+1})
- It suffices to show that (2,2,,2)(2^\ell, 2^\ell, \ldots, 2^\ell) is attainable from (1,2,,n)(1, 2, \ldots, n).

7. Base Case:
- For n=3n = 3:
(1,2,3)(2,2,4)(0,4,4)(4,4,4) (1, 2, 3) \mapsto (2, 2, 4) \mapsto (0, 4, 4) \mapsto (4, 4, 4)

8. General Case:
- Write n=2mn = 2^\ell - m where 0m<210 \leq m < 2^{\ell-1}.
- If m=0m = 0, we induct on n1n-1 and add in the 22^\ell already present.
- Assume m1m \geq 1. Note that m<nm < n, nm(mod2)n \equiv m \pmod{2}, and 212^{\ell-1} is the midpoint of the interval [m,n][m, n].
- Use the operation on the numbers (21i,21+i)(2^{\ell-1}-i, 2^{\ell-1}+i) for 1in211 \leq i \leq n-2^{\ell-1}:
(1,2,,m1,m,m+1,,n)(1,2,,m1,2,4,,2(nm2),21,2,2,,2) (1, 2, \ldots, m-1, m, m+1, \ldots, n) \mapsto \left(1, 2, \ldots, m-1, 2, 4, \ldots, 2\left(\frac{n-m}{2}\right), 2^{\ell-1}, 2^\ell, 2^\ell, \ldots, 2^\ell\right)

9. Casework:
- Case 1: m4m \geq 4 and nm6n-m \geq 6:
- Use inductive hypotheses and scaling on (1,2,,m1)(1, 2, \ldots, m-1) and (2,4,6,,nm)(2, 4, 6, \ldots, n-m) tuples.
- Case 2: m4m \geq 4 and nm4n-m \leq 4:
- Convert (1,2,,m1)(21,21,,21)(1, 2, \ldots, m-1) \mapsto (2^{\ell-1}, 2^{\ell-1}, \ldots, 2^{\ell-1}).
- Case 3: m3m \leq 3 and nm6n-m \geq 6:
- Convert (2,4,,nm)(2,2,,2)(2, 4, \ldots, n-m) \mapsto (2^\ell, 2^\ell, \ldots, 2^\ell).
- Case 4: m3m \leq 3 and nm4n-m \leq 4:
- For n=5n = 5:
(1,2,3,4,5)(1,2,2,4,8)(1,0,4,4,8)(0,8,8,8,8)(8,8,8,8,8) (1, 2, 3, 4, 5) \mapsto (1, 2, 2, 4, 8) \mapsto (1, 0, 4, 4, 8) \mapsto (0, 8, 8, 8, 8) \mapsto (8, 8, 8, 8, 8)
- For n=6n = 6:
(1,2,3,4,5,6)(1,4,3,4,5,8)(1,4,2,4,8,8)(1,0,2,8,8,8)(0,8,8,8,8,8)(8,8,8,8,8,8) (1, 2, 3, 4, 5, 6) \mapsto (1, 4, 3, 4, 5, 8) \mapsto (1, 4, 2, 4, 8, 8) \mapsto (1, 0, 2, 8, 8, 8) \mapsto (0, 8, 8, 8, 8, 8) \mapsto (8, 8, 8, 8, 8, 8)

Combining the above cases, we have proven the inductive hypothesis, and consequently, the problem is solved.

The final answer is all powers of two at least n \boxed{ n } .

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.