Эйлер атындағы олимпиада, 2009-2010 оқу жылы, аймақтық кезеңнің 2 туры


Алты адамнан тұратын компанияда кез-келген бес адам дөңгелек стөл үстінде әрбір екі көрші таныс болатыңдай отыра алады. Әрбір екі көрші таңыс болатыңдай бүкіл компанияны дөңгелек стөл үстіне отырғызуға болатының дәлелдеңіз. ( С. Волчёнков )
посмотреть в олимпиаде

Комментарий/решение:

Комментарии от администратора Комментарии от администратора №1.     Решение. Заметим, что у каждого в компании не менее трёх знакомых. Действительно, если бы некто $X$ был знаком менее, чем с тремя, то, исключив из компании одного из его знакомых, мы получили бы пятёрку людей, в которой у $X $ не более одного знакомого, т.е. посадить их за круглый стол невозможно. Возьмём теперь любых пятерых и рассадим их за круглый стол. Шестой человек знаком, по крайней мере, с тремя из них; значит, он знаком с какой-то парой сидящих рядом людей. Если мы посадим шестого между ними, то получим требуемую рассадку.