Наткнулся на видео https://www.youtube.com/watch?v=wWQ9YdreY9c и не сразу поверил, что в цикле всегда будет твой номер, объяснения из видео мне не хватило)) Для тех, кто не смотрел и не хочет смотреть, кратенько условие:

Имеется n коробок, пронумерованных от 1 до n. Внутри коробок лежат n карточек с теми же номерами от 1 до n, причем в каждой коробке лежит ровно одна карточка, и все номера уникальны. Нужно доказать, что если выбрать коробку с некоторым номером и каждый раз переходить к коробке, номер которой указан на лежащей в ней карточке, то рано или поздно мы найдем карточку с исходным номером.

И немного подумав, я сразу вспомнил про перестановки, и что любая перестановка это композиция циклических перестановок, и вообще большую часть алгебры с первого курса. Ну и само решение крайне простое, попытаюсь его изложить без какой-либо терминологии.

Нужно показать, что невозможно начать с какой-либо коробки i и не вернуться к ней же. Коробок конечное число, поэтому куда-то мы должны вернуться. Предположим, что не к изначальной, номер на ней обозначим за k. Но из этого сразу же следует, что в двух разных коробках лежат одинаковые карточки, потому что коробку, к которой они ведут, мы посетили дважды:

• Первый раз, когда открывали коробки от i до k

• Второй раз, когда вернулись в нее от коробки k

Получили противоречие, поэтому верно обратное, что все же мы вернемся к той коробке, с которой начинали.

Оффтоп

Приятно иногда так возвращаться к математике, особенно в таких мелочах, навевает прям ностальгию.

Здесь еще могла быть реклама моего тгк, но, увы, его нет и вряд ли будет:( Вместо этого вопрос, а можно ли как-то интересно усложнить задачку?