ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 65507
Темы:    [ Процессы и операции ]
[ Теория алгоритмов (прочее) ]
Сложность: 3+
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

Двенадцать стульев стоят в ряд. Иногда на один из свободных стульев садится человек. При этом ровно один из его соседей (если они были) встаёт и уходит. Какое наибольшее количество человек могут одновременно оказаться сидящими, если вначале все стулья были пустыми?


Решение

  Оценка. Все стулья одновременно занять невозможно, так как в тот момент, когда сядет человек на последний незанятый стул, один из его соседей встанет. Следовательно, одновременно сидящих может быть не больше чем 11.

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


Ответ

11.

Источники и прецеденты использования

олимпиада
Название Окружная олимпиада (Москва)
год
Год 2015
класс
Класс 8
задача
Номер 8.4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .