Bariz - Problem

Source: 44th International Tournament of Towns, Junior O-Level P1, Spring 2023

Tags: combinatorics

oVlad

09.01.2024 17:36

There are $N{}$ mess-loving clerks in the office. Each of them has some rubbish on the desk. The mess-loving clerks leave the office for lunch one at a time (after return of the preceding one). At that moment all those remaining put half of rubbish from their desks on the desk of the one who left. Can it so happen that after all of them have had lunch the amount of rubbish at the desk of each one will be the same as before lunch if a) $N = 2{}$ and b) $N = 10$? Alexey Zaslavsky

Let the $N$ mess-loving clerks have $a_1$, $a_2$, $\cdots$, $a_N$ amounts of rubbish. For $N=2$, we claim it only happens when $2a_1=a_2$. Equating the final amounts of rubbish with the original, \[a_1=\frac{a_1}{2}+\frac{a_2}{4} \]\[a_2=\frac{a_1}{2}+\frac{3a_2}{4}\]Solving, we get $2a_1=a_2$. The more interesting part is when $N=10$. A construction is $(1,2,4,8,\cdots, 2^9)$ which clearly works. In general, $(1,2,4,8,\cdots, 2^{N-1})$ works, since each move just cycles the numbers, and after $N$ moves, we get the same thing.