Bariz - Problem

Source: 2022 Austrian Federal Competition For Advanced Students, Part 1 p3

Tags: combinatorics

parmenides51

04.10.2022 18:57

Each person stands on a whole number on the number line from $0$ to $2022$ . In each turn, two people are selected by a distance of at least $2$. These go towards each other by $1$. 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)

HIDE: original wording 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.)

This is similar to Indonesian Olympiad, the Provincial stage, except in there it was done using numbers on the board. The average of all numbers is 1011, and each step does not change the average, so it makes sense that the final configuration must also have average 1011. This can happen if everyone is in 1011. If someone is greater than 1011, then someone else will be less than 1011, and a move is still possible between them. Now let $S$ be the sum of distances between every pair of people. Say $A$ moves from $a$ to $a+1$, and $B$ moves from $b$ to $b-1$, with $a+2 \leq b$. Consider the categories of people other than $A$ and $B$: 1. People standing on $a$ or less. Their distance to $A$ increases by 1, but their distance to $B$ decreases by 1. So the contribution to $S$ is unchanged. 2. People standing on $b$ or greater. Same argument, their contribution to $S$ is unchanged. 3. People standing in $(a,b)$. Their distance to $A$ decreases by 1, and their distance to $B$ decreases by 1, so the contribution to $S$ decreases by 2 PER PERSON. And finally note that the distance between $A$ and $B$ themselves also decrease by 2. So even if no one is in the third category, $S$ will decrease by at least 2 per move, so it is guaranteed that the process will terminate.