Разделы 
Дополнительно
Задача по математике - 1503
2019-01-19 
На предприятии трудятся 50000 человек. Для каждого из них сумма количества его непосредственных начальников и его непосредственных подчиненных равна 7. В понедельник каждый работник предприятия издает приказ и выдает копию этого приказа каждому своему непосредственному подчиненному (если такие есть). Далее, каждый день работник берет все полученные им в предыдущие день приказы и либо раздает их копии всем своим непосредственным подчиненным, либо, если таковых у него нет, выполняет приказы сам. Оказалось, что в пятницу никакие бумаги по учреждению не передаются. Докажите, что на предприятии не менее 97 начальников, над которыми нет начальников.
Решение:
Если на предприятии $k$ верховных начальников, то каждый работник должен увидеть хотя бы один из $k$ приказов этих начальников. В понедельник их увидели не более $7k$ работников, во вторник - не более $7k \cdot 36$,в среду - не более $7k \cdot 36$ работников. Все, кто увидел эти приказы в четверг, не имеют подчиненных: значит, они все имеют по 7 начальников и количество всех их начальников не более $7k \cdot 36$, причем у каждого из этих начальников не более 6 подчиненных. Таким образом, в четверг приказы увидели не более $(7k \cdot 36) \cdot 6/7 = 6k \cdot 36$ работников. Отсюда получаем $50000 \leq k + 7k + 42k + 252k + 216k = 518k$ и $k \geq 97$.
На предприятии трудятся 50000 человек. Для каждого из них сумма количества его непосредственных начальников и его непосредственных подчиненных равна 7. В понедельник каждый работник предприятия издает приказ и выдает копию этого приказа каждому своему непосредственному подчиненному (если такие есть). Далее, каждый день работник берет все полученные им в предыдущие день приказы и либо раздает их копии всем своим непосредственным подчиненным, либо, если таковых у него нет, выполняет приказы сам. Оказалось, что в пятницу никакие бумаги по учреждению не передаются. Докажите, что на предприятии не менее 97 начальников, над которыми нет начальников.
Решение:
Если на предприятии $k$ верховных начальников, то каждый работник должен увидеть хотя бы один из $k$ приказов этих начальников. В понедельник их увидели не более $7k$ работников, во вторник - не более $7k \cdot 36$,в среду - не более $7k \cdot 36$ работников. Все, кто увидел эти приказы в четверг, не имеют подчиненных: значит, они все имеют по 7 начальников и количество всех их начальников не более $7k \cdot 36$, причем у каждого из этих начальников не более 6 подчиненных. Таким образом, в четверг приказы увидели не более $(7k \cdot 36) \cdot 6/7 = 6k \cdot 36$ работников. Отсюда получаем $50000 \leq k + 7k + 42k + 252k + 216k = 518k$ и $k \geq 97$.
