Question

За круглым столом сидят 2015 представителей четырех племен: люди, гномы, эльфы и гоблины. Известно, что люди никогда не сидят рядом с гоблинами, а эльфы - рядом с гномами. Докажите, что какие-то два представителя одного племени сидят рядом.

Answer 1

Доказательство проведем методом от противного. Допустим, что никакие два соплеменника не сидят рядом. Назовём условно людей и гоблинов красными племенами, а эльфов и гномов - синими. Тогда синие могут сидеть рядом только с красными, а красные - только с синими. Но в таком случае красные и синие за столом должны чередоваться, а это возможно только в случае, когда сидящих - чётное число. Получили противоречие с тем, что сидящих нечетное число (2015). Следовательно, какие-то два представителя одного племени сидят рядом. Что и требовалось доказать.