1. Initial Observations:
- We start with the numbers 1,2,…,n on the blackboard.
- In each move, we can choose two numbers x and y, erase them, and write down x+y and ∣x−y∣.
- We need to determine all integers X such that all numbers can be turned into X 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 n. Therefore, the final number X must be at least n, i.e., X≥n.
3. Divisibility by Odd Primes:
- Suppose X is divisible by an odd prime p. Consider reversing the operations on the final tuple (X,X,…,X).
- The reverse operation is (a,b)↦(2a+b,2∣a−b∣).
- If p divides X, then p must divide all numbers on the blackboard at all times. This is impossible since 1 was on the board initially.
- Therefore, X cannot be divisible by any odd prime, implying X must be a power of 2.
4. Sufficient Conditions:
- Let ℓ be the smallest positive integer such that 2ℓ≥n.
- We need to show that (2m,2m,…,2m) is attainable whenever m≥ℓ.
5. Doubling Technique:
- We can perform the operation (x,y)↦(x+y,∣x−y∣)↦(2x,2y).
- Specifically, (0,x)↦(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). Then:
(2x,2x,…,2x)↦(0,2x+1,2x,2x,…,2x)↦(0,2x+1,2x+1,…,2x+1)↦(2x+1,2x+1,…,2x+1)
- It suffices to show that (2ℓ,2ℓ,…,2ℓ) is attainable from (1,2,…,n).
7. Base Case:
- For n=3:
(1,2,3)↦(2,2,4)↦(0,4,4)↦(4,4,4)
8. General Case:
- Write n=2ℓ−m where 0≤m<2ℓ−1.
- If m=0, we induct on n−1 and add in the 2ℓ already present.
- Assume m≥1. Note that m<n, n≡m(mod2), and 2ℓ−1 is the midpoint of the interval [m,n].
- Use the operation on the numbers (2ℓ−1−i,2ℓ−1+i) for 1≤i≤n−2ℓ−1:
(1,2,…,m−1,m,m+1,…,n)↦(1,2,…,m−1,2,4,…,2(2n−m),2ℓ−1,2ℓ,2ℓ,…,2ℓ)
9. Casework:
- Case 1: m≥4 and n−m≥6:
- Use inductive hypotheses and scaling on (1,2,…,m−1) and (2,4,6,…,n−m) tuples.
- Case 2: m≥4 and n−m≤4:
- Convert (1,2,…,m−1)↦(2ℓ−1,2ℓ−1,…,2ℓ−1).
- Case 3: m≤3 and n−m≥6:
- Convert (2,4,…,n−m)↦(2ℓ,2ℓ,…,2ℓ).
- Case 4: m≤3 and n−m≤4:
- For n=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)
- For n=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)
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.