Разделы 
Дополнительно
Задача по математике - 1144
2015-07-21 
В группе переводчиков, каждый из которых знает один или несколько иностранных языков, 24 владеют японским, 24 — малайским, 24 — персидским. Докажите, что можно выделить подгруппу, в которой ровно 12 человек владели бы японским, ровно 12 — малайским и ровно 12 — персидским.
Решение:
Группу переводчиков, в которой каждый язык знают ровно $a$ человек, назовем группой объема $a$. Докажем по индукции, что из группы объема $2n$ можно отобрать подгруппу объема $2k(k \leq n)$, тем самым будет, в частности, доказано утверждение задачи.
Для $k=0$ и $k=n$ утверждение очевидно. Значит, достаточно взять $k < n > 1$. Пусть $p$ человек знают Я и $M$ языки (квалификация А), $q - M$ и П (квалификация $B$), $r - П$ и Я (квалификация $С$). Очевидно, все эти люди разные. Если $p > 0, q > 0$ и $r > 0$, то возьмем по одному человеку квалификации $A$, $B$ и $C$. Оставшиеся образуют группу объема $2(n-1)$, а из нее можно выбрать искомую подгруппу по условию индукции.
Если $p=0$, $q=0$, $r=0$, то все переводчики — или полиглоты (числом $l$), знающие все три языка, либо моноспециалисты, знающие ровно один язык. Моноспециалистов по каждому языку одинаковое число $2n-l$. Поэтому мы объединим их по три в коллективных полиглотов. Всего полиглотов и коллективных полиглотов $2n$, а из них мы всегда можем отобрать $2k$.
Будем теперь для определенности считать, что $p \leq q \leq r$. Если $p=q=0,r > 0$, то после выделения полиглотов и максимально возможного числа коллективных полиглотов из моноспециалистов остается $r$ квалификации $C$. Поскольку общее число знатоков каждого языка одинаково, то существует еще по крайней мере $r$ моноспециалистов по $M$ языку. Образуем еще $r$ полиглотных пар из переводчика П и Я языка и переводчика $M$ языка. Оставшиеся переводчики могут быть только моноспециалистами, а их должно быть одинаковое число по каждой специальности, т. е. их можно разбить на коллективы полиглотов. Таким образом, и в этом случае можно из полиглотов, пар и коллективов набрать группу нужного объема. Если $p=0,q >0, r > 0$, то после выделения полиглотов и максимально возможного числа коллективных полиглотов из моноспециалистов, будет среди билингвистов $q+r$ знатоков П языка, $q$ знатоков $M$ языка и $r - Я$ языка. Значит, существует еще по крайней мере $q$ моноспециалнстов по Я языку и $r$ специалистов по $M$ языку. Возьмем из них одного моноспециалиста по Я языку, одного по $M$ языку, одного квалификации $B$ и одного квалификации $C$. Остальные образуют группу объема $2(n-1)$, а из нее можно выбрать искомую подгруппу по условию индукции.
В группе переводчиков, каждый из которых знает один или несколько иностранных языков, 24 владеют японским, 24 — малайским, 24 — персидским. Докажите, что можно выделить подгруппу, в которой ровно 12 человек владели бы японским, ровно 12 — малайским и ровно 12 — персидским.
Решение:
Группу переводчиков, в которой каждый язык знают ровно $a$ человек, назовем группой объема $a$. Докажем по индукции, что из группы объема $2n$ можно отобрать подгруппу объема $2k(k \leq n)$, тем самым будет, в частности, доказано утверждение задачи.
Для $k=0$ и $k=n$ утверждение очевидно. Значит, достаточно взять $k < n > 1$. Пусть $p$ человек знают Я и $M$ языки (квалификация А), $q - M$ и П (квалификация $B$), $r - П$ и Я (квалификация $С$). Очевидно, все эти люди разные. Если $p > 0, q > 0$ и $r > 0$, то возьмем по одному человеку квалификации $A$, $B$ и $C$. Оставшиеся образуют группу объема $2(n-1)$, а из нее можно выбрать искомую подгруппу по условию индукции.
Если $p=0$, $q=0$, $r=0$, то все переводчики — или полиглоты (числом $l$), знающие все три языка, либо моноспециалисты, знающие ровно один язык. Моноспециалистов по каждому языку одинаковое число $2n-l$. Поэтому мы объединим их по три в коллективных полиглотов. Всего полиглотов и коллективных полиглотов $2n$, а из них мы всегда можем отобрать $2k$.
Будем теперь для определенности считать, что $p \leq q \leq r$. Если $p=q=0,r > 0$, то после выделения полиглотов и максимально возможного числа коллективных полиглотов из моноспециалистов остается $r$ квалификации $C$. Поскольку общее число знатоков каждого языка одинаково, то существует еще по крайней мере $r$ моноспециалистов по $M$ языку. Образуем еще $r$ полиглотных пар из переводчика П и Я языка и переводчика $M$ языка. Оставшиеся переводчики могут быть только моноспециалистами, а их должно быть одинаковое число по каждой специальности, т. е. их можно разбить на коллективы полиглотов. Таким образом, и в этом случае можно из полиглотов, пар и коллективов набрать группу нужного объема. Если $p=0,q >0, r > 0$, то после выделения полиглотов и максимально возможного числа коллективных полиглотов из моноспециалистов, будет среди билингвистов $q+r$ знатоков П языка, $q$ знатоков $M$ языка и $r - Я$ языка. Значит, существует еще по крайней мере $q$ моноспециалнстов по Я языку и $r$ специалистов по $M$ языку. Возьмем из них одного моноспециалиста по Я языку, одного по $M$ языку, одного квалификации $B$ и одного квалификации $C$. Остальные образуют группу объема $2(n-1)$, а из нее можно выбрать искомую подгруппу по условию индукции.
