Задача 32783

Тема:    [ Принцип Дирихле (прочее) ]

Сложность: 3+ Классы: 7,8,9

Условие

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

Решение

1) Посмотрим, кого за столом больше: людей с гоблинами или эльфов с гномами. Без ограничения общности можно считать, что людей с гоблинами больше; тогда их по крайней мере 17, так как всего за столом сидят 33 существа.
  2) Пусть теперь эльфы с гномами встанут со своих мест. Из оставшихся какие-то двое обязательно сидят на соседних местах, поскольку занятых мест больше половины. Но эти двое не могут из разных племен, так как по условию люди не сидят рядом с гоблинам; значит, рядом сидят представители одного племени, что и требовалось доказать.

Источники и прецеденты использования

Кружок
Название	ВМШ 57 школы
класс
Класс	7
год
Год	2001/02
Место проведения	57 школа
занятие
Номер	1
Название	Простые вводные задачи
Тема	Неопределено
задача
Номер	07