|
|
 |
Условие
Двенадцать стульев стоят в ряд. Иногда на один из свободных стульев садится человек. При этом ровно один из его соседей (если они были) встаёт и уходит. Какое наибольшее количество человек могут одновременно оказаться сидящими, если вначале все стулья были пустыми?
Решение
Оценка. Все стулья одновременно занять невозможно, так как в тот момент, когда сядет человек на последний незанятый стул, один из его соседей встанет. Следовательно, одновременно сидящих может быть не больше чем 11.
Пример. Покажем, как посадить 11 человек. Пронумеруем стулья числами от 1 до 12. Первый стул занять легко. Второй стул займем в два этапа. На первом этапе человек садится на третий стул, а на втором этапе посадим человека на второй стул, а сидящий на третьем стуле встанет. Дальше действуем аналогично: если заняты стулья с номерами от 1 до k, то сначала посадим человека на стул с номером k + 2, а затем посадим на стул с номером k + 1, освобождая при этом стул с номером k + 2. После того как эта операция будет проделана для всех k от 1 до 10, стулья с номерами от 1 до 11 будут заняты, а двенадцатый стул – свободен.
Ответ
11.
