Разделы 
Дополнительно
Задача по математике - 3812
2019-06-16 
В некотором поселке 1000 жителей. Ежедневно каждый из них делится узнанными вчера новостями со всеми своими знакомыми. Известно, что любая новость становится известной всем жителям поселка.
Докажите, что можно выбрать 90 жителей так, что если одновременно всем им сообщить какую-то новость, то через 10 дней она станет известной всем жителям поселка.
Решение:
Будем говорить, что жители $X, A_1, A_2, \cdots, A_k, Y$ образуют цепочку, если $X$ знаком с $A_1, A_2$ знаком с $A_3, \cdots, A_k$ знаком с $Y$. Из условия следует, что любые два жителя соединены некоторой цепочкой. Будем считать, что замкнутых цепочек (т. е. цепочек, в которых $X$ знаком с $Y$) нет. Возьмем самую длинную цепочку $X - A_1 - A_2 - \cdots - A_{10} - \cdots - A_k - Y$. Если $k \leq 19$, то новость, сообщенная $A_{10}$, через 10 дней станет известна всем жителям поселка. Если $k \geq 20$, отделим жителей $X, A_1, \cdots, A_{10}$ и всех, кто связан с ними не через $A_{11}$ (их не меньше 11). Оставшаяся группа жителей по-прежнему удовлетворяет условию задачи. Повторяя уже описанную процедуру 89 раз (и на каждом шагу выделяя своего $A_{10}$), мы либо на каком-то шагу исчерпаем всех жителей, либо останется не более $1000 - 89 \cdot 11 = 21$, из которых выберем еще одного, как описано выше. Если же в поселке есть замкнутые цепочки, то их можно разорвать, сохраняя условия задачи.
В некотором поселке 1000 жителей. Ежедневно каждый из них делится узнанными вчера новостями со всеми своими знакомыми. Известно, что любая новость становится известной всем жителям поселка.
Докажите, что можно выбрать 90 жителей так, что если одновременно всем им сообщить какую-то новость, то через 10 дней она станет известной всем жителям поселка.
Решение:
Будем говорить, что жители $X, A_1, A_2, \cdots, A_k, Y$ образуют цепочку, если $X$ знаком с $A_1, A_2$ знаком с $A_3, \cdots, A_k$ знаком с $Y$. Из условия следует, что любые два жителя соединены некоторой цепочкой. Будем считать, что замкнутых цепочек (т. е. цепочек, в которых $X$ знаком с $Y$) нет. Возьмем самую длинную цепочку $X - A_1 - A_2 - \cdots - A_{10} - \cdots - A_k - Y$. Если $k \leq 19$, то новость, сообщенная $A_{10}$, через 10 дней станет известна всем жителям поселка. Если $k \geq 20$, отделим жителей $X, A_1, \cdots, A_{10}$ и всех, кто связан с ними не через $A_{11}$ (их не меньше 11). Оставшаяся группа жителей по-прежнему удовлетворяет условию задачи. Повторяя уже описанную процедуру 89 раз (и на каждом шагу выделяя своего $A_{10}$), мы либо на каком-то шагу исчерпаем всех жителей, либо останется не более $1000 - 89 \cdot 11 = 21$, из которых выберем еще одного, как описано выше. Если же в поселке есть замкнутые цепочки, то их можно разорвать, сохраняя условия задачи.
