Разделы 
Дополнительно
Задача по математике - 2736
2019-04-29 
Среди принятых в университет студентов имеется ровно 50 знающих английский язык, ровно 50 знающих французский язык и ровно 50 знающих немецкий язык (при этом, разумеется, среди студентов могут быть такие, которые знают сразу два или даже все три языка, так что общее число знающих хоть один язык студентов, вообще говоря, меньше $3 \cdot 50 = 150$). Докажите, что всех студентов можно разбить на 5 таких (вообще говоря - не совпадающих по численности) групп, что в каждой группе ровно 10 человек будут знать английский язык, ровно 10 человек - французский и ровно 10 человек - немецкий.
Решение:
Докажем, прежде всего, что если в некотором коллективе студентов каждый из трех языков - $\:а$ (английский), $\:ф$ (французский) и $\:н$ (немецкий) знают ровно $n$ человек, где $n^2$, то можно составить такую группу студентов, в которой каждый язык будут знать ровно 2 человека. Ясно, что из сформулированного предложения утверждение задачи уже вытекает: выбрав (и исключив из рассмотрения) указанную группу студентов, мы придем к совокупности студентов, в которой каждый из трех языков знают ровно 50 - 2 = 48 студентов; из этой совокупности студентов мы снова можем выбрать группу, в которой каждый язык знают ровно 2 студента, после чего у нас останется коллектив, в котором каждый язык знают ровно 48 - 2 = 46 студентов, и т. д. Объединив затем пять отобранных таким образом небольших групп, в которых каждый язык знают по 2 человека, мы получим первую из интересующих нас групп, в которой каждый язык знают ровно 10 человек; далее так же (т. е. исходя из «маленьких» групп, в которых каждый язык знают ровно 2 студента) мы станем составлять вторую и третью группы студентов (каждая из них будет состоять из 5 «маленьких» групп).
Для доказательства напечатанного выше курсивом утверждения можно использовать метод математической индукции. В самом деле, ясно, что если $n = 2$, то наше утверждение выполняется (рассматриваемая группа здесь - это совокупность всех студентов); предположим теперь, что оно верно для всех значений $n$, меньших некоторого, и докажем, что в таком случае оно справедливо и для этого значения $n$. Условимся обозначать число студентов, знающих только английский язык, через $N_{a}$; знающих английский и французский языки, но не немецкий, через $N_{аф}$ и т. д.; соответственно символ $a$ (или $a^{ \prime}$, или $a^{ \prime \prime}$) будет обозначать студента, знающего только английский язык; символ аф (или $(аф)^{ \prime}$) - студента, знающего языки а и ф, но не н, и т. д. Если при этом $N_{a} \neq 0$, $N_{ф} \neq 0, N_{н} \neq 0$, то мы просто исключим из нашего коллектива трех студентов а, ф и н и придем к новой совокупности студентов, для которой наше утверждение выполняется в силу предположения индукции; аналогично этому, если $N_{афн} \neq 0$, то мы откинем студента афн и снова придем к новому коллективу, для которого наше утверждение верно. Далее, если $N_{аф} \neq 0$, $N_{ан} \neq 0$ и $N_{фн} \neq 0$, то сформулированное предложение выполняется тривиально - требуемую группу составляют три студента аф, ан и фн. Наконец, если два из чисел $N_{аф}$, $N_{ан}$ и $N_{фн}$ отличны от нуля, а третье,- скажем, последнее из них - равно нулю, то отличны от нуля числа $N_{ф}$ и $N_{н}$ (ибо в объединении всех студентов аф, $(аф)^{ \prime}$, и т. д. и всех студентов ан, $(ан)^{ \prime}$, и т. д. больше студентов знают язык а, чем язык ф и чем язык н); поэтому мы можем исключить из числа студентов двух студентов аф и н и снова прийти к коллективу студентов, в котором каждый язык знают $n - 1$ человек и в котором, по предположению индукции, требуемую «малую» группу студентов составить можно. Аналогично, если скажем, лишь $N_{аф} \neq 0$, а $N_{ан} = N_{фн} = 0$, то, очевидно, $N_{н} \neq 0$ - и мы можем снова использовать предположение индукции, удалив студентов аф и н. [Заметим, что равенства $N_{аф} = N_{ан} = N_{фн} = 0$ (и $N_{афн} = 0$) противоречат предположению, что хоть одно из чисел $N_{а}, N_{ф}$ и $N_{н}$ равно нулю.]
Примечание. Ясно, что числа 50 и 10 в условии этой задачи являются случайными: в точности так же можно доказать, что если в нашем коллективе студентов каждый из трех языков (где, впрочем, и число 3 можно пытаться заменять другими) знают ровно $n$ студентов, то из описанных «малых» групп можно конструировать группы, в которых каждый из языков знают, любое не большее $n$ заданное четное число $m$ студентов; однако предположение о четности $m$ здесь является существенным (попытайтесь доказать это!)
Среди принятых в университет студентов имеется ровно 50 знающих английский язык, ровно 50 знающих французский язык и ровно 50 знающих немецкий язык (при этом, разумеется, среди студентов могут быть такие, которые знают сразу два или даже все три языка, так что общее число знающих хоть один язык студентов, вообще говоря, меньше $3 \cdot 50 = 150$). Докажите, что всех студентов можно разбить на 5 таких (вообще говоря - не совпадающих по численности) групп, что в каждой группе ровно 10 человек будут знать английский язык, ровно 10 человек - французский и ровно 10 человек - немецкий.
Решение:
Докажем, прежде всего, что если в некотором коллективе студентов каждый из трех языков - $\:а$ (английский), $\:ф$ (французский) и $\:н$ (немецкий) знают ровно $n$ человек, где $n^2$, то можно составить такую группу студентов, в которой каждый язык будут знать ровно 2 человека. Ясно, что из сформулированного предложения утверждение задачи уже вытекает: выбрав (и исключив из рассмотрения) указанную группу студентов, мы придем к совокупности студентов, в которой каждый из трех языков знают ровно 50 - 2 = 48 студентов; из этой совокупности студентов мы снова можем выбрать группу, в которой каждый язык знают ровно 2 студента, после чего у нас останется коллектив, в котором каждый язык знают ровно 48 - 2 = 46 студентов, и т. д. Объединив затем пять отобранных таким образом небольших групп, в которых каждый язык знают по 2 человека, мы получим первую из интересующих нас групп, в которой каждый язык знают ровно 10 человек; далее так же (т. е. исходя из «маленьких» групп, в которых каждый язык знают ровно 2 студента) мы станем составлять вторую и третью группы студентов (каждая из них будет состоять из 5 «маленьких» групп).
Для доказательства напечатанного выше курсивом утверждения можно использовать метод математической индукции. В самом деле, ясно, что если $n = 2$, то наше утверждение выполняется (рассматриваемая группа здесь - это совокупность всех студентов); предположим теперь, что оно верно для всех значений $n$, меньших некоторого, и докажем, что в таком случае оно справедливо и для этого значения $n$. Условимся обозначать число студентов, знающих только английский язык, через $N_{a}$; знающих английский и французский языки, но не немецкий, через $N_{аф}$ и т. д.; соответственно символ $a$ (или $a^{ \prime}$, или $a^{ \prime \prime}$) будет обозначать студента, знающего только английский язык; символ аф (или $(аф)^{ \prime}$) - студента, знающего языки а и ф, но не н, и т. д. Если при этом $N_{a} \neq 0$, $N_{ф} \neq 0, N_{н} \neq 0$, то мы просто исключим из нашего коллектива трех студентов а, ф и н и придем к новой совокупности студентов, для которой наше утверждение выполняется в силу предположения индукции; аналогично этому, если $N_{афн} \neq 0$, то мы откинем студента афн и снова придем к новому коллективу, для которого наше утверждение верно. Далее, если $N_{аф} \neq 0$, $N_{ан} \neq 0$ и $N_{фн} \neq 0$, то сформулированное предложение выполняется тривиально - требуемую группу составляют три студента аф, ан и фн. Наконец, если два из чисел $N_{аф}$, $N_{ан}$ и $N_{фн}$ отличны от нуля, а третье,- скажем, последнее из них - равно нулю, то отличны от нуля числа $N_{ф}$ и $N_{н}$ (ибо в объединении всех студентов аф, $(аф)^{ \prime}$, и т. д. и всех студентов ан, $(ан)^{ \prime}$, и т. д. больше студентов знают язык а, чем язык ф и чем язык н); поэтому мы можем исключить из числа студентов двух студентов аф и н и снова прийти к коллективу студентов, в котором каждый язык знают $n - 1$ человек и в котором, по предположению индукции, требуемую «малую» группу студентов составить можно. Аналогично, если скажем, лишь $N_{аф} \neq 0$, а $N_{ан} = N_{фн} = 0$, то, очевидно, $N_{н} \neq 0$ - и мы можем снова использовать предположение индукции, удалив студентов аф и н. [Заметим, что равенства $N_{аф} = N_{ан} = N_{фн} = 0$ (и $N_{афн} = 0$) противоречат предположению, что хоть одно из чисел $N_{а}, N_{ф}$ и $N_{н}$ равно нулю.]
Примечание. Ясно, что числа 50 и 10 в условии этой задачи являются случайными: в точности так же можно доказать, что если в нашем коллективе студентов каждый из трех языков (где, впрочем, и число 3 можно пытаться заменять другими) знают ровно $n$ студентов, то из описанных «малых» групп можно конструировать группы, в которых каждый из языков знают, любое не большее $n$ заданное четное число $m$ студентов; однако предположение о четности $m$ здесь является существенным (попытайтесь доказать это!)
