2014-06-08
На вечере собралось несколько юношей и девушек. При этом оказалось, что если выбрать любую группу юношей, то число девушек, знакомых по крайней мере с одним из юношей этой группы, будет не меньше числа юношей в группе. Доказать, что все юноши одновременно смогут танцевать каждый в паре со знакомой девушкой.
Решение:
Будем решать задачу индукцией по $n$ - числу юношей. Для $n = 1$ утверждение вытекает из того, что для одного юноши обязательно найдется знакомая девушка. Пусть утверждение доказано для всех чисел, меньших $n$. Докажем его для числа $n$. Рассмотрим два случая.
1) Найдется такая группа А из $k < n$ юношей, что общее число всех знакомых с ними девушек равно $k$. Пусть каждый юноша из этой группы танцует со знакомой девушкой (это возможно в силу предположения индукции). Тогда для оставшихся юношей и девушек условие задачи будет выполнено. Действительно, если имеется группа В из $i$ не входящих в А юношей, то у юношей из объединения множества В с множеством А имеется не менее чем $i + k$ знакомых девушек. Юноши, входящие в А, знакомы в общей сложности не более чем с $k$ девушками. Значит, $i$ юношей из группы В знакомы по крайней мере с $i$ из оставшихся девушек. Таким образом, по предположению индукции, каждый из юношей, не входящих в А, также может танцевать со знакомой ему девушкой.
2) У любой группы из любого количества $k < n$ юношей число знакомых девушек превышает $k$. Тогда, если один из юношей будет танцевать со знакомой ему девушкой, то множество оставшихся юношей и девушек будет по-прежнему удовлетворять условию задачи. Действительно, любая группа из $k \leq n -1$ оставшихся юношей знакома не менее чем с $k + 1$ девушками (одна из которых, возможно, уже танцует). Значит, по предположению индукции, каждый из оставшихся юношей также сможет танцевать со знакомой ему девушкой.