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

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

Условие

Во взводе служат три сержанта и несколько солдат. Сержанты по очереди дежурят по взводу. Командир издал такой приказ.
  1. За каждое дежурство должен быть дан хотя бы один наряд вне очереди.
  2. Никакой солдат не должен иметь более двух нарядов и получать более одного наряда за одно дежурство.
  3. Списки получивших наряды ни за какие два дежурства не должны совпадать.
  4. Сержант, первым нарушивший одно из изложенных выше правил, наказывается гауптвахтой.
Сможет ли хотя бы один из сержантов, не сговариваясь с другими, давать наряды так, чтобы не попасть на гауптвахту?


Решение

Назовём циклом три дежурства, идущие подряд. Чтобы не попасть на гауптвахту, третий сержант будет в последний день каждого цикла давать наряды в точности тем солдатам, которые получили за предыдущие два дня ровно по одному наряду (из п. 3 следует, что такие солдаты найдутся). При такой стратегии по окончании каждого цикла у каждого солдата будет либо два наряда, либо ни одного, причём количество вторых будет убывать. Стало быть, когда-то окажется, что все солдаты имеют по два наряда, и на гауптвахту отправится первый сержант (или еще раньше отправится первый или второй).


Ответ

Сможет тот сержант, который дежурит третьим.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 1996
Этап
Вариант 5
Класс
Класс 10
задача
Номер 96.5.10.6

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

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