Олимпиадная задача о сержантах и наряде — теория чисел и алгоритмы, 8–10 класс
Во взводе служат три сержанта и несколько солдат. Сержанты по очереди дежурят по взводу. Командир издал такой приказ.
1. За каждое дежурство должен быть дан хотя бы один наряд вне очереди.
2. Никакой солдат не должен иметь более двух нарядов и получать более одного наряда за одно дежурство.
3. Списки получивших наряды ни за какие два дежурства не должны совпадать. 4. Сержант, первым нарушивший одно из изложенных выше правил, наказывается гауптвахтой.
Сможет ли хотя бы один из сержантов, не сговариваясь с другими, давать наряды так, чтобы не попасть на гауптвахту?
Показать ответ
Сможет тот сержант, который дежурит третьим.
Разобрать решение
Назовём циклом три дежурства, идущие подряд. Чтобы не попасть на гауптвахту, третий сержант будет в последний день каждого цикла давать наряды в точности тем солдатам, которые получили за предыдущие два дня ровно по одному наряду (из п. 3 следует, что такие солдаты найдутся). При такой стратегии по окончании каждого цикла у каждого солдата будет либо два наряда, либо ни одного, причём количество вторых будет убывать. Стало быть, когда-то окажется, что все солдаты имеют по два наряда, и на гауптвахту отправится первый сержант (или еще раньше отправится первый или второй).
Обсуждение
0Комментариев пока нет.