Условие
Колода перфокарт четырёх цветов разложена в один ряд. Если две перфокарты
одного цвета лежат рядом или через одну, то можно выбрасывать ту из них,
которая левее. Кроме того, можно подкладывать справа любое количество перфокарт
из других колод. Доказать, что можно подкладывать и выбрасывать перфокарты
таким образом, чтобы в конце концов их осталось только четыре.
Решение
Покажем, что если в колоде лежат перфокарты
k разных цветов, то можно
подкладывать и выбрасывать перфокарты таким образом, чтобы в конце концов их
осталось только
k. Мы будем подкладывать только те цвета, что уже есть
в колоде.
Заметим сначала, что последние две карты можно поменять местами.
Действительно, если
a1,...,
an - 1,
an — цвета карт в колоде,
записанные слева направо, то, подложив справа карту цвета
an - 1 и убрав
карту
an - 1, мы получим колоду
a1,...,
an - 2,
an,
an - 1.
Следовательно, можно подкладывать карту на предпоследнее место: для этого
достаточно подложить карту на последнее место и поменять две последние карты
местами. Продолжая это рассуждение, индукцией по
n доказывается, что можно
подложить карту на любое место и поменять любые две соседние карты местами.
Следовательно, можно получить любую перестановку карт в колоде.
Докажем теперь, что если в колоде больше
k перфокарт, то количество
перфокарт можно уменьшить. Действительно, в этом случае найдутся две карты
одного цвета. Переставим карты так, чтобы эти две оказались стоящими через
одну и выбросим одну из них. Итак, если количество карт больше
k, то число
карт можно уменьшить. Следовательно, можно подкладывать и выбрасывать карты
таким образом, чтобы осталось только
k карт. При
k = 4 получаем утверждение
задачи.
Источники и прецеденты использования
