Дано:
1. 25 человек сидят за круглым столом.
2. Каждому человеку розданы по две карточки с числами от 1 до 25, каждое число встречается ровно дважды (всего 50 карточек).
3. Раз в минуту каждый человек передаёт своему соседу справа ту карточку, на которой написано меньшее число.
Найти:
Доказать, что процесс закончится, когда у кого-то на руках окажутся две карточки с одинаковыми номерами.
Решение:
1. Обозначим числа на карточках, которые у человека i, как x_i и y_i, где x_i < y_i. Сначала человек i передаст карточку x_i своему соседу справа, а через минуту передаст карточку y_i.
2. Каждый человек передаёт карточку только ту, на которой написано меньшее число. Следовательно, если x_i < x_(i+1), то после передачи x_i карточка x_i переместится к человеку (i+1) и на его руках появится одна карточка x_i.
3. Поскольку на карточках написаны числа от 1 до 25, всего существует 25 пар чисел. Если на каком-то этапе у человека появляются две карточки с одинаковыми номерами, процесс заканчивается.
4. Рассмотрим количество уникальных пар карточек. Изначально у всех 25 человек уникальные пары карточек, которые распределены между ними. Но по мере передачи карточек в процесс вовлекается все больше карточек, и уникальные пары могут повторяться.
5. Рассмотрим распределение карточек между всеми людьми. Поскольку у каждого человека по две карточки, которые они передают, через какое-то время количество карточек на руках у каждого будет стремиться к равномерному распределению. Но поскольку мы передаем карточки по кругу и процесс передачи карточек влияет на весь круг, всегда будет возможность, что в какой-то момент два одинаковых числа окажутся у одного человека.
6. Обозначим состояние карточек как (x_i, y_i). Учитывая, что процесс передачи карточек неизменно движется к более равномерному распределению, мы можем сказать, что количество уникальных комбинаций постепенно сокращается по мере передачи карточек. Если процесс продолжается достаточно долго, одна из комбинаций обязательно станет повторяющейся, и у одного человека появятся две одинаковых карточки.
Ответ:
Процесс обязательно закончится, когда у какого-то человека на руках окажутся две карточки с одинаковыми номерами.