2019-04-29
На международной конференции присутствуют 17 ученых. Каждые два из них беседуют друг с другом на определенном языке; при этом всего все 17 человек знают три языка. Доказать, что среди участников конференции найдутся трое, которые говорят друг с другом на одном и том же языке.
Решение:
Пусть $A$ - какой-то один из присутствующих на конференции ученых; с каждым из 16 остальных он говорит на одном из трех (или на меньшем числе, если он не владеет, всеми тремя) языков. Нетрудно видеть, что имеется такой язык (назовем его «тарабарским»), на котором $A$ разговаривает не менее чем с 6 учеными: в самом деле, в противном случае собеседников у $A$ будет не больше чем $5 \cdot 3 = 15$, а по условию задачи любые два ученых могут говорить между собой. Если двое из этих 6 ученых говорят между собой на тарабарском языке, то утверждение задачи доказано; если же это не так, то между собой 6 ученых говорят лишь на двух языках.
Пусть теперь $В$ - произвольный из выделенных 6 ученых. Ясно, что найдутся такие 3 из 5 остальных ученых, с которыми он говорит па одном н том же («таратарабарском») языке: ведь если бы это было не так, то среди 5 ученых В мог бы иметь не более чем $2 \cdot 2 = 4$ собеседников. Если хоть какие-то два - скажем $C$ и $D$ - из этих трех участников конференции говорят между собой на таратарабарском языке, то мы уже получаем тройку ученых $A, B$ и $D$, разговаривающих между собой на одном языке; если же эти трое ученых между собой говорят на третьем («таратаратарабарском») языке, то они и составляют искомую тройку.