2014-06-08
Девять математиков встретились на международной конференции и обнаружили, что среди любых трех из них по меньшей мере двое говорят на одном языке. Кроме того, каждый математик может говорить не более чем на трех языках. Доказать, что хотя бы три из них говорят на одном и том же языке.
Решение:
Допустим, что никакие трое из математиков не говорят на одном и том же языке. Рассмотрим произвольного математика А. Он говорит не более чем на трех языках, причем на каждом из этих языков говорит еще не более чем один из математиков (иначе мы получили бы противоречие с допущением). Поэтому найдутся пять математиков, с которыми А не говорит на одном языке. Пусть одни из этих пяти - математик В. По той же причине, что и А, математик В может говорить на одном языке не более чем с тремя математиками. Поэтому среди остальных четырех математиков, не говорящих на одном языке с А, найдется математик С, не говорящий на одном языке с В. Таким образом, в тройке А, В, С никакие двое не говорят на одном языке, что противоречит условию задачи.