В замке короля Артура любые два рыцаря либо дружат, либо враждуют. Оказалось, что среди этих рыцарей любые два врага имеют ровно двух общих друзей, а любые два друга общих друзей не имеют вовсе. Докажите, что у всех рыцарей в замке одно и то же число врагов.
1 Ответ
Рассмотрим произвольного рыцаря A. Так как у каждых двух его врагов есть ровно два общих друга, то все враги A разбиваются на пары, и в каждой паре есть ровно один общий друг A. Но у каждого из этих общих друзей есть ровно один враг, который не является другом A, поскольку общие друзья A не дружат друг с другом. Таким образом, каждый друг A увеличивает число врагов на 1, и число друзей A нацело делит число его врагов.
Теперь рассмотрим произвольного рыцаря B, не являющегося другом A. У каждых двух врагов B есть ровно два друга, которые не являются друзьями A (поскольку общие друзья B не дружат с A), поэтому враги B разбиваются на пары так, чтобы в каждой паре был один общий друг, не являющийся A. Это означает, что число врагов B, не являющихся друзьями A, четно.
Итак, мы показали, что для каждого рыцаря A число его друзей делит число его врагов, а для каждого рыцаря B число его врагов четно. Следовательно, число друзей и число врагов у каждого рыцаря совпадают тогда и только тогда, когда они оба делятся на одно и то же натуральное число.