Question

В стае 50 ворон, причём среди любых 4-х из них найдётся такая , которая враждует с тремя остальными. ( Если А враг В, то В враг А) Докажите , что среди них есть не меньше 1000 пар врагов.

Answer 1

Если “среди любых 4-х ворон найдётся такая, которая враждует с 3-я остальными”, то у каждой из 50-ти ворон в стае будет 49 врагов. Помня из комбинаторики “если элемент А можно выбрать n способами, а элемент В можно выбрать m способами, то пару А и В можно выбрать n*m способами”, общее количество враждующих пар составит 50*49=2450. Чтобы учесть условие “если А враг В, то В враг А” надо отбросить взаимопротивоположные пары, т.е. 24502=1225. Таким образом, среди 50-ти ворон есть не менее 1000 пар врагов.