В шахматном турнире каждый участник встретился с каждым один раз. В каждом туре каждый участник проводил по одной встрече. Не меньше чем в половине всех встреч оба участника были земляками (из одного города). Докажите, что в каждом туре была хотя бы одна встреча между земляками.
Предположим, что в каком-то туре не было игры между земляками. Тогда участники разбиваются на пары людей из разных городов. Рассмотрим произвольного участника. В каждой паре есть не более одного его земляка, также второй участник из его пары не является его земляком. Но тогда всего земляков у него меньше половины из всех участников. Значит, каждый участник сыграл больше игр с неземляками, чем с земляками, и в сумме игр между земляками было меньше половины. Противоречие.