В стае 50 ворон, причём среди любых 4-х из них найдётся такая , которая враждует с тремя...

0 голосов
56 просмотров

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


Алгебра (45 баллов) | 56 просмотров
Дан 1 ответ
0 голосов
Правильный ответ

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

(11.8k баллов)