|
|
 |
Условие
Докажите, что среди 50 человек найдутся двое, у которых чётное число общих знакомых (быть может, 0) среди остальных 48 человек.
Решение
Пусть A – один из наших 50 человек, N – группа людей, знакомых с ним. Для каждого B из N его общие знакомые с A – это в точности люди из N, знакомые с B. Если в N нечётное число людей, то в N найдется человек B, у которого чётное число знакомых в N, (см. задачу 87972 б) и тогда (A, B) – искомая пара.
Остается рассмотреть случай, когда у каждого из наших 50 человек чётное число знакомых. Тогда в группе M незнакомых с A – нечётное число людей, и поэтому в M найдется некто C, у которого чётное число знакомых в M. Поскольку C незнаком с A, а всего у него чётное число знакомых, то у него чётное число знакомых в N. Поэтому (C, A) – искомая пара.
Замечания
1. Утверждение остается справедливым для множества из любого чётного числа элементов. Условие чётности необходимо: если все 2k + 1 людей знакомы между собой, то каждые двое имеют 2k – 1 общих знакомых.
2. 10 баллов
