В колоде часть карт лежит "рубашкой вниз". Время от времени Петя
вынимает из колоды пачку из одной или нескольких подряд идущих карт, в которой
верхняя и нижняя карты лежат "рубашкой вниз", переворачивает всю пачку как одно
целое и вставляет её в то же место колоды. Докажите, что в конце концов все
карты лягут "рубашкой вверх", как бы ни действовал Петя.
Скрыть решение
Решение
Расположению карт в колоде сопоставим число, в котором цифр
столько, сколько в колоде карт, причём на k-м месте справа стоит "1", если k-я
карта снизу лежит рубашкой вверх, и "2" в противном случае. Тогда после каждого
преобразования это число уменьшается. (Действительно, сравним полученное число с
предыдущим. Среди всех цифр, которые изменились, выберем самую левую, т. е.
найдём самый старший изменившийся разряд. Очевидно, в этом разряде цифра "2"
сменилась на "1".) Поскольку количество n-значных чисел из единиц и двоек
конечно (не больше 2n), в конце концов мы получим число, состоящее из
одних единиц, что соответствует расположению всех карт рубашкой вверх.