Разделы 
Дополнительно
Задача по математике - 1077
2015-02-22 
Каждый из 17 ученых переписывается с остальными. В их переписке речь идет лишь о трех темах. Каждая пара ученых переписывается друг с другом лишь по одной теме. Докажите, что не менее трех ученых переписываются друг с другом по одной и той же теме.
Решение:
Выберем наугад одного ученого. Он переписывается с каждым из остальных 16 ученых только об одной теме. Докажем, что хотя бы по одной теме из трех он переписывается с 6 учеными. Пусть это не так. Тогда по каждой теме он переписывается не более чем с 5 учеными. Следовательно, по трем темам он переписывается не более чем с 15 учеными, что противоречит условию. Эту тему будем называть темой $A$. Если среди этих шестерых найдутся два, переписывающихся друг с другом по теме $A$, то задача решена. Возможен другой вариант: никто из этих 6 ученых не переписывается по теме $A$. Тогда они переписываются по двум другим темам. Рассмотрим одного из 6 ученых. Он переписывается с остальными 5 учеными шестерки. Найдется тема, по которой он переписывается с тремя из 5 ученых. В противном случае он переписывался бы только с 4 учеными. Назовем эту тему темой $B$. Если один из этих трех ученых переписывается с другим по теме $B$, то задача решена. Если они все трое переписываются между собой по третьей теме (теме $C$), то они и составили искомую тройку. Все случаи рассмотрены. Тем самым доказано, что указанная тройка всегда найдется.
Каждый из 17 ученых переписывается с остальными. В их переписке речь идет лишь о трех темах. Каждая пара ученых переписывается друг с другом лишь по одной теме. Докажите, что не менее трех ученых переписываются друг с другом по одной и той же теме.
Решение:
Выберем наугад одного ученого. Он переписывается с каждым из остальных 16 ученых только об одной теме. Докажем, что хотя бы по одной теме из трех он переписывается с 6 учеными. Пусть это не так. Тогда по каждой теме он переписывается не более чем с 5 учеными. Следовательно, по трем темам он переписывается не более чем с 15 учеными, что противоречит условию. Эту тему будем называть темой $A$. Если среди этих шестерых найдутся два, переписывающихся друг с другом по теме $A$, то задача решена. Возможен другой вариант: никто из этих 6 ученых не переписывается по теме $A$. Тогда они переписываются по двум другим темам. Рассмотрим одного из 6 ученых. Он переписывается с остальными 5 учеными шестерки. Найдется тема, по которой он переписывается с тремя из 5 ученых. В противном случае он переписывался бы только с 4 учеными. Назовем эту тему темой $B$. Если один из этих трех ученых переписывается с другим по теме $B$, то задача решена. Если они все трое переписываются между собой по третьей теме (теме $C$), то они и составили искомую тройку. Все случаи рассмотрены. Тем самым доказано, что указанная тройка всегда найдется.
