Maths Olympiad Prep

Library / /10 of 20

Number theory Difficulty 6.4 National olympiad Find the answer

On a blackboard there are n2,nZ\plus n \geq 2, n \in \mathbb{Z}^{\plus{}} numbers. In each step we select two numbers from the blackboard and replace both of them by their sum. Determine all numbers n n for which it is possible to yield n n identical number after a finite number of steps.

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

Solution

We are given n2 n \geq 2 positive integers on a blackboard. At each step, we pick two numbers, say a a and b b , and replace them with their sum a+b a + b . We aim to determine all values of n n for which it is possible to make all numbers on the blackboard identical after a sequence of such operations.

To solve this problem, we consider the following steps:

1. Understanding the Operation: Each operation selects two numbers and replaces them with their sum. The total sum of all numbers on the blackboard remains constant throughout all operations. Let this total sum be S S .

2. Final Condition: For all n n numbers to be identical, each must equal Sn \frac{S}{n} . Therefore, S S must be divisible by n n .

3. Divisibility Constraint: Initially, consider numbers that are distributed arbitrarily. The sum S S of these numbers is fixed. To make all numbers the same, say k k , we need S=nk S = nk . Hence, n n must divide the initial sum S S .

4. Parity Argument: The crucial aspect is whether n n is even or odd:

- If n n is even, the sum S S of any set of numbers can be manipulated to be divisible by n n through a series of operations, stemming from the fact that each operation induces parity adjustments which explore all even divisions of the initial S S .

- If n n is odd, regardless of the initial numbers, at least one number’s parity will dominate the configuration (either more odds than evens), resulting in an inability to achieve an all-even or all-odd homogeneous setup without altering S S .

5. Conclusion:
- Operations that preserve divisibility imply that every operation change retains the evenness of S S concerning n n , when n n is even. Hence, equalizing all numbers is feasible when n n is even.
- In contrast, for odd n n , such parity balance required across the steps is generally not achievable starting from arbitrary initial conditions.

Thus, the values of n n for which it is possible for all numbers on the blackboard to become identical are when n n is even. Therefore, we conclude that the solution is:

n is even \boxed{\text{n is even}}

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