Разделы 
Дополнительно
Задача по математике - 3316
2019-06-02 
В колоде часть карт лежит «рубашкой вниз». Время от времени Петя вынимает из колоды пачку из одной или нескольких подряд идущих карт, в которой верхняя и нижняя карты лежат «рубашкой вниз», переворачивает всю пачку как одно целое и вставляет ее в то же место колоды. Докажите, что в конце концов все карты лягут «рубашкой вверх», как бы ни действовал Петя.
Решение:
Будем кодировать расположение карт в колоде числом, в котором цифр столько, сколько в колоде карт. Это число строится по следующему правилу: на $k$-м месте справа стоит 1, если $k$-я карта снизу лежит рубашкой вверх, и 2, если эта карта лежит рубашкой вниз. Например, колода, в которой все карты лежат рубашкой вниз, кодируется числом, десятичная запись которого состоит из одних двоек.
Нетрудно видеть, что после каждого Петиного действия это число уменьшается. Действительно, сравним полученное число с предыдущим. Среди всех цифр, которые изменились, выберем самую левую, т. е. найдем самый старший изменившийся разряд. Очевидно, в этом разряде цифра 2 сменилась на 1. Но это означает, что число уменьшилось.
Поскольку количество $n$-значных чисел из единиц и двоек конечно, число не может уменьшаться «до бесконечности» - в конце концов мы получим число, состоящее из одних единиц, что соответствует расположению всех карт рубашкой вверх.
В колоде часть карт лежит «рубашкой вниз». Время от времени Петя вынимает из колоды пачку из одной или нескольких подряд идущих карт, в которой верхняя и нижняя карты лежат «рубашкой вниз», переворачивает всю пачку как одно целое и вставляет ее в то же место колоды. Докажите, что в конце концов все карты лягут «рубашкой вверх», как бы ни действовал Петя.
Решение:
Будем кодировать расположение карт в колоде числом, в котором цифр столько, сколько в колоде карт. Это число строится по следующему правилу: на $k$-м месте справа стоит 1, если $k$-я карта снизу лежит рубашкой вверх, и 2, если эта карта лежит рубашкой вниз. Например, колода, в которой все карты лежат рубашкой вниз, кодируется числом, десятичная запись которого состоит из одних двоек.
Нетрудно видеть, что после каждого Петиного действия это число уменьшается. Действительно, сравним полученное число с предыдущим. Среди всех цифр, которые изменились, выберем самую левую, т. е. найдем самый старший изменившийся разряд. Очевидно, в этом разряде цифра 2 сменилась на 1. Но это означает, что число уменьшилось.
Поскольку количество $n$-значных чисел из единиц и двоек конечно, число не может уменьшаться «до бесконечности» - в конце концов мы получим число, состоящее из одних единиц, что соответствует расположению всех карт рубашкой вверх.
