|
|
 |
Условие
В колоде часть карт лежит рубашкой вниз. Время от времени Петя вынимает из колоды пачку из одной или нескольких подряд идущих карт, в которой верхняя и нижняя карты лежат рубашкой вниз, переворачивает всю пачку как одно целое и вставляет её в то же место колоды (если "пачка" состоит лишь из одной карты, то требуется только, чтобы она лежала рубашкой вниз). Докажите, что в конце концов все карты лягут рубашкой вверх, как бы ни действовал Петя.
Решение 1
Сопоставим каждой карте цифру: единицу, если она лежит рубашкой вверх, и двойку – если рубашкой вниз. Записав эти цифры слева направо, начиная с цифры, соответствующей верхней карте, мы получим некоторое натуральное число. При каждом переворачивании пачки карт это число уменьшается: двойка, соответствующая верхней карте в пачке, заменяется единицей, а цифры в более старших разрядах не меняются. Но натуральное число не может уменьшаться бесконечно, поэтому когда-нибудь переворачивания прекратятся. Это и значит, что все карты легли рубашкой вверх.
Решение 2
Индукция по толщине колоды. База (колода из одной карты) очевидна.
Шаг индукции. Пусть утверждение задачи доказано для колоды из n карт. Рассмотрим колоду из n + 1 карты.
Если верхняя карта лежит рубашкой вверх, то она в переворачиваниях не участвует, и фактически все действия Петя производит с колодой из n карт. По предположению индукции в конце концов все карты лягут рубашкой вверх.
Пусть верхняя карта лежит рубашкой вниз. Как только Петя её задействует, наверху окажется карта рубашкой вверх, что приводит нас к уже разобранному случаю. Если же Петя упорно не будет её трогать, то по предположению индукции в некоторый момент все оставшиеся карты лягут рубашкой вверх. Теперь Пете придется перевернуть верхнюю карту, на чём процесс и закончится.
Замечания
5 баллов
