Оценка + пример
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Двенадцать стульев стоят в ряд. Иногда на один из свободных стульев садится человек. При этом ровно один из его соседей (если они были) встает и уходит. Какое наибольшее количество человек могут одновременно оказаться сидящими, если вначале все стулья были пустыми?
Источники:
Подсказка 1
Могут ли все стулья оказаться занятыми?
Подсказка 2
Правильно, не могут! Можно ли привести пример, где только один стул свободен?
Подсказка 3
Да, можно. Как его придумать? Попробуйте посадить двух людей на первые два стула, используя третий стул, а дальше продолжить этот алгоритм.
Оценка. Все стулья одновременно занять невозможно, так как в тот момент, когда сядет человек на последний незанятый стул, один из его
соседей встанет. Следовательно, одновременно сидящих может быть не больше чем 
Пример. Покажем, как посадить 
человек. Пронумеруем стулья числами от 
до 
Первый стул занять легко. Второй стул
займем в два этапа. На первом этапе человек садится на третий стул, а на втором этапе посадим человека на второй стул, а сидящий на
третьем стуле встанет. Дальше действуем аналогично: если заняты стулья с номерами от 
до 
то сначала посадим человека на стул с
номером 
а затем посадим на стул с номером 
освобождая при этом стул с номером 
После того как эта
операция будет проделана для всех 
от 
до 
стулья с номерами от 
до 
будут заняты, а двенадцатый стул —
свободен.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
