Question

В кружок пришло 35 ребят. Оказалось, что есть 10 из них, каждый из которых знает более, чем 2/ остальных 25. Докажите, что найдутся такие двое ребят, не входящих в эту десятку, что каждый из десятки знает хотя одного из этих двоих.

Answer 1

Назовём десятерых, о которых идёт речь в задаче, знатоками, а остальных членов кружка ¾ дружками. Будем говорить, что знаток портит пару дружков, если он не знает никого из этой пары. По условию каждый знаток знает более 50/3, то есть не меньше 17 дружков. Значит, он незнаком самое большее с 8 дружками и может испортить максимум 8×7/2 = 28 пар дружков. Стало быть, вместе все 10 знатоков могут испортить максимум 280 пар дружков, а всего пар дружков ¾ 25×24/2 = 300. Поэтому найдется неиспорченная пара дружков (и даже не меньше 20 таких пар), что и требовалось доказать.

Answer 2

Допустим, что есть десять детей из этой группы, каждый из которых знает более, чем 2/3 остальных детей. Мы хотим доказать, что найдутся двое детей из оставшихся 25, таких, что каждый из десяти знает хотя бы одного из этих двоих.

Давайте воспользуемся методом противоположного предположения (от противного) для доказательства. Предположим, что для каждой пары из оставшихся 25 детей существует хотя бы один из десяти, который не знает ни одного из этих двоих.

Итак, у нас есть 10 детей, обозначим их A1, A2, ..., A10. Теперь у нас есть 25 оставшихся детей, обозначим их B1, B2, ..., B25.

Для каждой пары из детей B1, B2, ..., B25 возьмем одного из десяти, например, A1, который, согласно предположению, не знает ни одного из этих двоих. То есть, для каждой пары Bi и Bj существует Ai, такой что Ai не знает Bi и Bj.

Теперь посчитаем, сколько отношений сосуществует у десяти детей A1, A2, ..., A10 и оставшихся 25 детей B1, B2, ..., B25. У каждого из десяти детей есть 25 возможных детей из группы B, которых он не знает (так как существует 25 детей в группе B). По предположению, каждый из десяти знает более 2/3 оставшихся детей, то есть как минимум 17. Таким образом, каждый из десяти знает не менее 17 детей из группы B.

Теперь подсчитаем общее количество отношений сосуществования: 10 детей * (не менее 17 детей из группы B) = 170 отношений сосуществования.

Но у нас есть 25 детей в группе B. Каждая пара из них может существовать в максимум 1 отношении сосуществования (потому что если два разных детей из группы B знают одного и того же ребенка из десяти, это всего лишь одно отношение).

Поэтому общее количество отношений сосуществования должно быть не больше, чем количество возможных пар детей в группе B, что равно C(25, 2) = 25 * 24 / 2 = 300.

Итак, получили противоречие: 170 отношений сосуществования (беря каждого из десяти детей) не может быть больше 300 возможных пар детей в группе B. Это противоречие возникает из-за нашего предположения, что каждый из десяти не знает хотя бы одного из пары B. Таким образом, предположение неверно, и мы доказали, что найдутся такие двое детей из группы B, что каждый из десяти знает хотя бы одного из этих двоих.