Условие
В колоде
n карт. Часть из них лежит рубашками вверх, остальные – рубашками вниз.
За один ход разрешается взять несколько карт сверху, перевернуть полученную стопку и снова положить
ее сверху колоды. За какое наименьшее число ходов при любом начальном расположении карт можно
добиться того, чтобы все карты лежали рубашками вниз?
Решение
За
n ходов.
Докажем сначала, что не более чем за
n ходов всегда можно положить все
карты рубашками вниз. Если изначально все карты лежат рубашками вниз, то
утверждение доказано. В противном случае разобьем колоду на группы подряд
идущих карт, лежащих одинаково (т.е. в каждой группе все карты лежат либо
рубашками вверх, либо рубашками вниз). Перевернем самую верхнюю группу.
Тогда число групп уменьшится на единицу. Будем далее повторять эту
процедуру до тех пор, пока не останется одна группа, т.е. все карты в
колоде будут лежать одинаково. Так как изначально было не более
n групп,
то для этого потребуется не более
n-1
ходов. Полученную в результате
группу можно, если это необходимо, за один ход перевернуть, добившись,
чтобы все карты лежали рубашками вниз.
Покажем теперь, что существует расположение карт, при котором нельзя
получить требуемое расположение карт в колоде менее, чем за
n ходов. Так
как каждый ход, как легко проверить, уменьшает число групп не более, чем
на единицу, то колода, содержащая
n групп, может быть приведена к одной
группе минимум за
n-1
ходов. Рассмотрим колоду, в которой нижняя карта
лежит рубашкой вверх, вторая снизу – рубашкой вниз, и так далее. Если
каждый раз делается ход, уменьшающий число групп, то вся колода
целиком не переворачивалась, поэтому через
n-1
ходов такая колода будет
приведена к одной группе, в которой все карты лежат рубашками вверх (т.е.
так, как первоначально лежала нижняя карта). Следовательно, понадобится
n -й ход, чтобы перевернуть все карты и положить их, как требуется в
условии задачи. Если же, кроме
n-1
ходов, уменьшающих число групп, будут
сделаны какие-то ходы, не уменьшающие число групп, то, очевидно, всего
будет сделано не менее
n ходов. Таким образом, указанную колоду нельзя
привести к одной группе менее, чем за
n ходов.
Ответ
За
n ходов.
Источники и прецеденты использования
|
|
|
олимпиада |
|
Название |
Всероссийская олимпиада по математике |
|
год |
|
Год |
1993 |
|
Этап |
|
Вариант |
4 |
|
класс |
|
Класс |
9 |
|
задача |
|
Номер |
93.4.9.4 |
