Олимпиадная задача по комбинаторике для 10-11 классов от Бердникова А.: дежурства сторожей
В команде сторожей у каждого есть разряд (натуральное число). Сторож N-го разряда N суток дежурит, потом N суток спит, снова N суток дежурит, N – спит, и так далее. Известно, что разряды любых двух сторожей различаются хотя бы в три раза. Может ли такая команда осуществлять ежедневное дежурство? (Приступить к дежурству сторожа могут не одновременно, в один день могут дежурить несколько сторожей.)
Показать ответ
Не может.
Разобрать решение
Занумеруем сторожей в порядке убывания разряда. У сторожей жизнь делится на равные периоды сна и дежурства. При этом у каждого сторожа периоды, как минимум, втрое короче, чем у предыдущего; поэтому любой период предыдущего делится, как минимум, на три части периодами следующего, причём как минимум две из этих частей будут целыми периодами следующего. Следовательно, период сна предыдущего содержит целый период сна следующего. Так продолжая, найдём вложенный друг в друга набор периодов снов всех сторожей. В день, входящий в самый маленький из вложенных периодов сна, никто не дежурит.
Обсуждение
0Комментариев пока нет.