Разделы 
Дополнительно
Задача по математике - 1681
2019-01-20 
На встречу выпускников пришло 45 человек. Оказалось, что любые двое из них, имеющие одинаковое число знакомых среди пришедших, не знакомы друг с другом. Какое наибольшее число пар знакомых могло быть среди участвовавших во встрече?
Решение:
Приведем пример. Поскольку $45 = 1 + 2 + 3 +\cdots + 9$, можно разбить 45 человек на группы по 1, по 2, $\cdots$, по 9 человек Пусть люди, принадлежащие одной группе, не знакомы между собой, а люди, принадлежащие разным группам, знакомы. Тогда каждый человек из $k$-й группы имеет $45 - k$ знакомых. При этом, очевидно, условие задачи выполнено, и общее количество пар знакомых людей равно $\frac{45 \cdot 44}{2} - (\frac{2 \cdot 1}{2} + \frac{3 \cdot 2}{2} + \cdots + \frac{9 \cdot 8}{2}) = 870$.
Докажем, что большего числа знакомств быть не могло. Зафиксируем некоторое $к, 0 \leq k \leq 44$. Пусть имеется некоторый выпускник, который знаком ровно с $k$ людьми. По условию любой его знакомый не может иметь ровно к знакомых. Поэтому количество выпускников, знакомых ровно с $k$ людьми, не превосходит $45 - k$.
Обозначим через $A_0, A_1, \cdots, A_{44}$ количество выпускников, имеющих соответственно $0, 1, \cdots, 44$ знакомых. Как показано выше, $A_k \leq 45 - k$, кроме того, $A_0 + A_1 + \cdots + A_{44} - 45$.
Оценим общее число знакомств $S = \frac{1}{2} (0 \cdot A_0 + 1 \cdot А_1 + \cdots + 44 \cdot А_{44}) = \frac{1}{2} (А_{44} + (А_{44}+А_{43})+ \cdots +(А_{44}+А_{43}+ \cdots + А_{36}) + \cdots + (А_{44} + А_{43} + \cdots + A_0)) \leq \frac{1}{2} (1+ (1 + 2) + \cdots + (1 + 2 + \cdots + 9) + 45 + 45 + \cdots + 45) = \frac{1}{2}(45 \cdot 44 - ((9 + 8 + \cdots + 2) + (9 + 8 + \cdots + 3) + \cdots + 9)) = 870$.
Ответ. 870.
На встречу выпускников пришло 45 человек. Оказалось, что любые двое из них, имеющие одинаковое число знакомых среди пришедших, не знакомы друг с другом. Какое наибольшее число пар знакомых могло быть среди участвовавших во встрече?
Решение:
Приведем пример. Поскольку $45 = 1 + 2 + 3 +\cdots + 9$, можно разбить 45 человек на группы по 1, по 2, $\cdots$, по 9 человек Пусть люди, принадлежащие одной группе, не знакомы между собой, а люди, принадлежащие разным группам, знакомы. Тогда каждый человек из $k$-й группы имеет $45 - k$ знакомых. При этом, очевидно, условие задачи выполнено, и общее количество пар знакомых людей равно $\frac{45 \cdot 44}{2} - (\frac{2 \cdot 1}{2} + \frac{3 \cdot 2}{2} + \cdots + \frac{9 \cdot 8}{2}) = 870$.
Докажем, что большего числа знакомств быть не могло. Зафиксируем некоторое $к, 0 \leq k \leq 44$. Пусть имеется некоторый выпускник, который знаком ровно с $k$ людьми. По условию любой его знакомый не может иметь ровно к знакомых. Поэтому количество выпускников, знакомых ровно с $k$ людьми, не превосходит $45 - k$.
Обозначим через $A_0, A_1, \cdots, A_{44}$ количество выпускников, имеющих соответственно $0, 1, \cdots, 44$ знакомых. Как показано выше, $A_k \leq 45 - k$, кроме того, $A_0 + A_1 + \cdots + A_{44} - 45$.
Оценим общее число знакомств $S = \frac{1}{2} (0 \cdot A_0 + 1 \cdot А_1 + \cdots + 44 \cdot А_{44}) = \frac{1}{2} (А_{44} + (А_{44}+А_{43})+ \cdots +(А_{44}+А_{43}+ \cdots + А_{36}) + \cdots + (А_{44} + А_{43} + \cdots + A_0)) \leq \frac{1}{2} (1+ (1 + 2) + \cdots + (1 + 2 + \cdots + 9) + 45 + 45 + \cdots + 45) = \frac{1}{2}(45 \cdot 44 - ((9 + 8 + \cdots + 2) + (9 + 8 + \cdots + 3) + \cdots + 9)) = 870$.
Ответ. 870.
