|
|
 |
Условие
На предприятии трудятся 50000 человек. Для каждого из них сумма количества его непосредственных начальников и его непосредственных подчинённых равна 7. В понедельник каждый работник предприятия издаёт приказ и выдаёт копию этого приказа каждому своему непосредственному подчинённому (если такие есть). Далее, каждый день работник берёт все полученные им в предыдущий день приказы и либо раздаёт их копии всем своим непосредственным подчинённым, либо, если таковых у него нет, выполняет приказы сам. Оказалось, что в пятницу никакие бумаги по учреждению не передаются. Докажите, что на предприятии не менее 97 начальников, над которыми нет начальников.
Решение
Если на предприятии k верховных начальников, то каждый работник в конце концов должен увидеть хотя бы один из k изданных в понедельник приказов этих начальников. В понедельник их увидели не более 7k работников,
во вторник – не более 7k·6, в среду – не более
7k·36 работников. Все, кто увидел эти приказы в четверг, не имеют подчиненных: значит, они все имеют по семь начальников и количество всех их начальников не более 7k·36, причём у каждого из этих начальников не более шести подчиненных. Таким образом, в четверг приказы увидели не более (7k·36)· 6/7 = 6k·36 работников. Отсюда
50000 ≤ k + 7k + 42k + 252k + 216k = 518k, значит, k ≥ 97.
