Question

В народной армие 100 человек и каждый вечер на охрану выходят трое . Доведите , что не можно сделать такой график охраны , чтобы любые 2 человека охраняли вместе ровно один раз.

Answer 1

Возьмем одного из дружинников. Если бы такое разделение было возможным, то остальные должны были бы разбиться на пары, кот. должны были бы дежурить с выбранным дружинником. Так как 99 нечётное, то это невозможно.

Answer 2

Для доказательства невозможности создания графика охраны, при котором любые два человека будут охранять вместе ровно один раз, можно воспользоваться методом Дирихле (Принципом ящиков).

Допустим, у нас есть 100 человек, и каждый вечер на охрану выходят трое. Создадим график, где на каждый день мы будем записывать троих охранников. Таким образом, нам понадобятся 100 дней, чтобы записать всех членов народной армии. Поскольку каждый день трое человек выходят на охрану, общее количество записей в графике будет равно 100 * 3 = 300.

Теперь предположим, что каждые двое из наших 100 человек будут охранять вместе ровно один раз. Каждая такая пара будет соответствовать одной записи в нашем графике. Но общее количество записей у нас 300. Это значит, что у нас должно быть 150 различных пар, чтобы каждые двое охраняли вместе ровно один раз.

Теперь воспользуемся методом Дирихле: если нужно распределить N объектов (в нашем случае, 150 пар) по M ящикам (в нашем случае, 100 дней в графике), причем N > M, то как минимум один ящик должен содержать не менее (N-1)/M + 1 объектов.

Применяя этот принцип к нашей ситуации, у нас 150 пар и 100 дней (ящиков). Подставим значения в формулу:

(N-1)/M + 1 = (150-1)/100 + 1 ≈ 1.51.

Итак, как минимум один день в графике должен содержать 1.51 пару, что невозможно, так как количество пар должно быть целым числом. Это доказывает, что невозможно составить график охраны, при котором каждые двое из 100 человек будут охранять вместе ровно один раз.