Задача 60418

Темы:    [ Теория графов (прочее) ] [ Сочетания и размещения ] [ Принцип Дирихле (прочее) ]

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

Условие

В компании из 10 человек произошло 14 попарных ссор. Докажите, что все равно можно составить компанию из трёх друзей.

Решение

Общее число способов выбрать компанию из трёх человек равно     Каждая ссора разрушает не более восьми таких компаний, поэтому число разрушенных компаний не больше  8·14 = 112.  Значит осталось по крайней мере 8 дружных компаний.

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

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	2
Название	Комбинаторика
Тема	Комбинаторика
параграф
Номер	3
Название	Размещения, перестановки и сочетания
Тема	Классическая комбинаторика
задача
Номер	02.084