Question

20 БАЛОВ СРОЧНО И ПОДРОБНО!!! На конференции присутствуют 50 ученых, каждый из которых знаком по крайней мере с 25 участниками конференции. Докажите, что найдутся четверо из них, которы: можно усадить за круглый стол так, чтобы каждый сидел рядом со знакомыми ем людьми.

Answer 1

задачу можно перефразировать:

у любого ученого есть пара друзей имеющих общего знакомого. Тогда мы сможем рассадить их в замкнутую цепь: ученый-первый друг-общий знакомый-второй друг-ученый...

Это действительно так:

у ученого есть два друга - факт

каждый друг имеет минимум 24 знакомых. если 24а и 24б то есть 48 человек, а свободных вариантов 50-3(*ученый и два друга*)=47, значит по принципу Дирихле два зайца попадут в одну клетку или один из знакомых будет общий.

Answer 2

Для доказательства этого утверждения воспользуемся принципом Дирихле (принцип ящиков).

Предположим, что у нас есть 50 ученых на конференции, каждый из которых знаком с 25 участниками. Создадим ящики, представляющие каждого ученого, и в каждый ящик поместим его знакомых. Таким образом, у нас будет 50 ящиков, и в каждом из них будет 25 знакомых ученого.

Теперь рассмотрим, как распределены знакомые ученых внутри этих ящиков. Поскольку каждый ученый знаком с 25 участниками, мы можем считать, что каждый ученый вносит по 25 монет в ящики своих знакомых (положим по монете в каждый ящик за каждого знакомого). Итак, у нас есть 50 ящиков, и в каждом из них 25 монет.

Теперь посчитаем общее количество монет (знакомых), которые находятся в ящиках. Это равно 50 (ящиков) * 25 (монет в каждом ящике) = 1250 монет.

Теперь мы можем рассмотреть 3 возможных случая:

1. Если в каждом ящике ровно по 25 монет (знакомых ученых), то все ученые знакомы с ровно 25 другими учеными, и мы можем усадить их за круглый стол так, чтобы каждый сидел рядом со знакомыми.

2. Если в каком-то ящике более 25 монет (более 25 знакомых ученых), тогда согласно принципу Дирихле, в этом ящике найдутся четыре ученых, так как 25 + 25 + 25 + 25 = 100 монет. Таким образом, эти четверо ученых можно усадить за круглый стол так, чтобы каждый сидел рядом со знакомыми.

3. Если в каком-то ящике менее 25 монет (менее 25 знакомых ученых), тогда согласно принципу Дирихле, в другом ящике должны быть более 25 монет. В противном случае, общее количество монет было бы меньше 1250. Таким образом, снова найдутся четверо ученых с более чем 25 знакомыми, и мы можем усадить их за круглый стол так, чтобы каждый сидел рядом со знакомыми.

Таким образом, во всех случаях у нас найдутся четверо ученых, которых можно усадить за круглый стол так, чтобы каждый сидел рядом со знакомыми.