Задача М1500‍‍‍

Предположим противное: пусть у каждых двух из 50 человек нечётное число общих знакомых.

Пусть $A$‍‍ — один из этих людей, $M=\{B_1,B_2,\ldots,B_k\}$‍‍ — множество его знакомых.

Лемма. Число $k$‍‍ знакомых у каждого $A$‍‍ чётно.

Действительно, составим для каждого $B_i\in M$‍‍ список всех его знакомых в $M$‍.‍ Суммарное число мест во всех $k$‍‍ списках чётно, поскольку оно равно удвоенному числу пар знакомых в $M$‍,‍ а число людей в каждом списке нечётно. Значит, $k$‍‍ чётно.

(Читатель, видимо, встречался с каким-то вариантом этой хорошо известной задачи.)

Итак, пусть $k=2n$‍.‍ Составим теперь для каждого $B_i\in M$‍‍ список всех его знакомых, кроме $A$‍‍ (не только в $M$‍).‍ Каждый список по лемме (применённой к $B_i$‍)‍ состоит из нечётного числа людей и потому суммарное число мест во всех $2m$‍‍ списках чётно. Но тогда кто-то из 49 людей (кроме $A$‍)‍ входит в чётное число списков, т. е. имеет нечётное число общих знакомых с $A$‍.‍

Противоречие с предположением доказывает, что у каких-то двух из 50 человек будет чётное число общих знакомых.