Ukrainian Mathematical Olympiad

Без обмеження загальності можна вважати, що всі багатії мають різну кількість монет. Тоді задачу можна переформулювати так: нехай $A$ — довільна 100-елементна множина з натуральних чисел, кожне з яких не менше від мільйона. Тоді знайдуться такі різні числа $t_1,t_2,\dots ,t_{100}$, які не перевищують мільйона, що множини $A_i=A-t_i=\{x-t_i\mid x\in A\}$ попарно не перетинаються.

Нехай $D=\{x-y\mid x,y\in A\}$. Очевидно, що умова $A_i\cap A_j=\varnothing$ рівносильна тому, що $t_i-t_j\notin D$. Помітимо, що в множині $D$ не більше за $100^2=10^4$ елементів. Будемо вибирати числа $t_i$ послідовно. Число $t_1$ виберемо довільно. Якщо числа $t_1,t_2,\dots ,t_k$ вибрано, то число $t_{k+1}$ потрібно вибрати так, щоб воно не лежало в жодній з множин $t_1+D,t_2+D,\dots ,t_k+D$. Для $k<100$ такий вибір можливий, оскільки загалом у цих множинах не більше за $99\cdot 10^4<10^6$ елементів.