Maths Olympiad Prep

Library / /23 of 520

Combinatorics Difficulty 6.2 National olympiad Find the answer

Each person stands on a whole number on the number line from 00 to 20222022 . In each turn, two people are selected by a distance of at least 22. These go towards each other by 11. When no more such moves are possible, the process ends.
Show that this process always ends after a finite number of moves, and determine all possible configurations where people can end up standing. (whereby is for each configuration is only of interest how many people stand at each number.)

(Birgit Vera Schmidt)

Bei jeder ganzen Zahl auf dem Zahlenstrahl von 0 bis 2022 steht zu Beginn eine Person.
In jedem Zug werden zwei Personen mit Abstand mindestens 2 ausgewählt. Diese gehen jeweils um 1 aufeinander zu. Wenn kein solcher Zug mehr möglich ist, endet der Vorgang.
Man zeige, dass dieser Vorgang immer nach endlich vielen Zügen endet, und bestimme alle möglichen Konfigurationen, wo die Personen am Ende stehen können. (Dabei ist für jede Konfiguration nur von Interesse, wie viele Personen bei jeder Zahl stehen.)

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

Solution

To show that the process always ends after a finite number of moves and to determine all possible configurations where people can end up standing, we will proceed as follows:

1. Invariant of the Average Position:
- Initially, each person stands on a whole number from 00 to 20222022. The average position of all people is:
Average=0+1+2++20222023=2022202322023=1011 \text{Average} = \frac{0 + 1 + 2 + \cdots + 2022}{2023} = \frac{\frac{2022 \cdot 2023}{2}}{2023} = 1011
- Each move involves two people moving towards each other by 1 unit each. This does not change the sum of their positions, and hence the average position remains 10111011.

2. **Sum of Distances SS:**
- Let SS be the sum of distances between every pair of people. We will show that SS decreases with each move.
- Consider two people AA and BB standing at positions aa and bb respectively, with a+2ba + 2 \leq b. They move to a+1a+1 and b1b-1 respectively.

3. **Effect on SS:**
- We categorize the effect on SS based on the positions of other people relative to AA and BB:
- **People standing on aa or less:** Their distance to AA increases by 1, but their distance to BB decreases by 1. Thus, their contribution to SS is unchanged.
- **People standing on bb or greater:** Their distance to AA decreases by 1, but their distance to BB increases by 1. Thus, their contribution to SS is unchanged.
- **People standing in (a,b)(a, b):** Their distance to AA decreases by 1, and their distance to BB decreases by 1. Thus, their contribution to SS decreases by 2 per person.
- Additionally, the distance between AA and BB themselves decreases by 2.

4. **Decrease in SS:**
- Even if no one is in the interval (a,b)(a, b), the distance between AA and BB decreases by 2. Therefore, SS decreases by at least 2 per move.
- Since SS is a non-negative integer and decreases by at least 2 per move, the process must terminate after a finite number of moves.

5. Final Configuration:
- The final configuration must have all people standing at the same position, as any other configuration would allow further moves.
- Given the invariant that the average position is 10111011, the only possible final configuration is that all people stand at position 10111011.

\blacksquare

The final answer is all people standing at position 1011 \boxed{ 1011 } .

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.