Maths Olympiad Prep

Library / /156 of 520

Combinatorics Difficulty 6.6 National olympiad Find the answer

There are n2n \ge 2 numbers on the blackboard: 1,2,...,n1, 2,..., n. It is permitted to erase two of those numbers x,yx,y and write 2xy2x - y instead. Find all values of nn such that it is possible to leave number 00 on the blackboard after n1n - 1 such procedures.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

1. Base Cases:
- For n=1 n = 1 , the only number on the blackboard is 1. It is impossible to perform any operation to get 0.
- For n=2 n = 2 , the numbers are 1 and 2. We can perform the operation (1,2)(212)=0 (1, 2) \to (2 \cdot 1 - 2) = 0 .
- For n=3 n = 3 , the numbers are 1, 2, and 3. We can try different operations, but it is impossible to get 0. For example:
(1,2,3)(0,3)(0,3)(0,0)0 (1, 2, 3) \to (0, 3) \to (0, 3) \to (0, 0) \to 0
This sequence does not work, and trying other combinations will also fail.

2. Inductive Step:
- Assume that for some n2 n \geq 2 , it is possible to leave the number 0 on the blackboard after n1 n - 1 operations.
- We need to show that if it is possible for n n , then it is also possible for n+2 n + 2 .
- Consider the numbers 1,2,,n,n+1,n+2 1, 2, \ldots, n, n+1, n+2 . Perform the operation on n+1 n+1 and n+2 n+2 :
(n+1,n+2)(2(n+1)(n+2))=n (n+1, n+2) \to (2(n+1) - (n+2)) = n
- Now we have the numbers 1,2,,n,n 1, 2, \ldots, n, n . Since we assumed it is possible to leave 0 with n n numbers, we can perform the operations on the first n n numbers to eventually get 0. The extra n n does not affect the process.

3. Conclusion:
- By induction, if it is possible for n n , it is also possible for n+2 n + 2 .
- We have shown that it is possible for n=2 n = 2 and impossible for n=1 n = 1 and n=3 n = 3 .
- Therefore, it is possible for all n2 n \geq 2 except n=3 n = 3 .

The final answer is n2 \boxed{ n \geq 2 } except n=3 n = 3 .

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.