2014-06-08
a) В комнате находится 10 человек, причем среди любых трех из них есть двое знакомых между собой. Доказать, что найдутся четыре человека, любые два из которых знакомы друг с другом.
б) Останется ли верным утверждение п.а), если в нем число 10 заменить на 9?
Решение:
а) Предположим, что среди любых четырех человек имеются двое незнакомых. Тогда, скажем, человек А не может иметь более трех незнакомых: если А имеет четырех незнакомых, то, согласно предположению, среди них найдутся двое незнакомых между собой, а они образуют вместе с А тройку попарно незнакомых людей. Итак, А имеет не более трех незнакомых, а значит, не менее шести знакомых. Пусть А знаком с $B_{1}, B_{2}, \cdots, B_{6}$. Тогда среди $B_{1}, B_{2}, \cdots, B_{8}$ нет тройки попарно знакомых людей (иначе эта тройка вместе с А образовывала бы четверку попарно знакомых людей, что противоречило бы предположению). Значит, среди любых трех человек из $B_{1}, B_{2}, \cdots, B_{6}$ есть двое незнакомых. Тогда $B_{1}$ не может иметь более двух незнакомых среди $B_{2}, \cdots, B_{6}$ (если $B_{1}$ не знаком, например, с $B_{2}, B_{3}, B_{4}$, то $B_{2}, B_{3}$ и $B_{4}$ попарно знакомы). Поэтому $B_{1}$ имеет по крайней мере троих знакомых среди $B_{2}, \cdots, B_{6}$. Тогда в этой тройке людей найдутся двое знакомых друг с другом, образующих вместе с $B_{1}$ и $A$ четверку попарно знакомых, что противоречит предположению.
б) Докажем, что утверждение останется верным. Если какой-либо человек знаком по крайней мере с шестью людьми, то доказательство аналогично проведенному выше в п. а). Если же каждый человек знаком ровно с пятью людьми, то общее количество пар знакомых равно $9 \cdot 5/2$, т. е. не является целым, что невозможно. Наконец, если найдется человек, не знакомый по крайней мере с четырьмя людьми, то эти четверо попарно знакомы (иначе нашлась бы тройка попарно незнакомых людей), т. е. образуют искомую четверку людей. Утверждение доказано.