20 БАЛОВ СРОЧНО И ПОДРОБНО!!!
На конференции присутствуют 50 ученых, каждый из которых знаком по крайней мере с 25 участниками конференции. Докажите, что найдутся четверо из них, которы: можно усадить за круглый стол так, чтобы каждый сидел рядом со знакомыми ем людьми.
На конференции присутствуют 50 ученых, каждый из которых знаком по крайней мере с 25 участниками конференции. Докажите, что найдутся четверо из них, которы: можно усадить за круглый стол так, чтобы каждый сидел рядом со знакомыми ем людьми.
More Questions From This User See All
Answers & Comments
задачу можно перефразировать:
у любого ученого есть пара друзей имеющих общего знакомого. Тогда мы сможем рассадить их в замкнутую цепь: ученый-первый друг-общий знакомый-второй друг-ученый...
Это действительно так:
у ученого есть два друга - факт
каждый друг имеет минимум 24 знакомых. если 24а и 24б то есть 48 человек, а свободных вариантов 50-3(*ученый и два друга*)=47, значит по принципу Дирихле два зайца попадут в одну клетку или один из знакомых будет общий.