усиление классической задачи про знакомства

[qwert129]

В компании из 100 людей среди любых 50 есть один, знающий остальных. Докажите, что в этой компании есть 51 человек, знающий всех.

[sergey zhukov]

qwert129
Возьмем "худший случай": есть 49 человек (группа "49"), каждый из которых не знает никого. Тогда остается вторая группа (группа "51"), причем по условию:

1. При добавлении любого из группы "51" в группу "49" человек из группы "51" должен знать там всех;
2. При удалении любого из группы "51" в ней всегда должен оставаться тот, кто знает в ней всех.

Это значит, что в группе "51" все знают всех остальных.

Остается только показать, что случай "49 не знают никого" - самый "худший".

Можно, наверное, даже так подойти. Создадим группу, в которой знакомы не все. Если это невозможно, то просто все знают всех. Если возможно, то по условию она не может быть более 49 человек. Тогда остальные 51 по условию должны знать всех согласно рассуждению выше.

[manul91]

Вроде тривиально.
Допустим, что в компании есть 50 (или более) человек "не знающих остальных".
Тогда из этих людей можно было бы выбрать 50, и получим 50 человек "не знающих остальных".
Но это противоречит условию (из любых 50 есть один, знающих остальных" - а мы выбрали 50 для которых никто не знает остальных).
Значит в компании человек "не знающих остальных" - должно быть 49 или менее.
Из этого и то что в компании 100 человек, следует что в компании 51 (или более) человек знающих остальных.

[sergey zhukov]

qwert129
Вот так лучше:

Возьмем "худший случай": есть 49 человек (группа "49"), каждый из которых не знает вообще никого. Тогда остается вторая группа (группа "51"), причем по условию:

1. Каждый человек из "51" знает всех из "49" (иначе можно добавить человека из "51" в "49" и получить 50 человек, в которой нет никого, кто-бы знал всех в группе);
2. В любой подгруппе "50" из группы "51" есть тот, кто знает всех в подгруппе "50". Это не может быть всегда один и тот же человек в группе "51" (его можно исключить и набрать группу из 50 человек без него). Допустим, на группу "51" их двое. Тогда заменим второго на одного человека из группы "49". Условие "В любой подгруппе "50" из группы "51" есть тот, кто знает всех в подгруппе "50"" должно сохраняться, т.е. таких людей в изначальной группе "51" должно быть минимум трое и т.д.

Это значит, что в группе "51" все знают вообще всех.

[EUgeneUS]

manul91 в сообщении #1624856 писал(а):

Вроде тривиально.
Допустим, что в компании есть 50 (или более) человек "не знающих остальных".

В компании из 50 человек есть как минимум один, знающий всех в этой компании, а не вообще всех.

[TOTAL]

Всех, у кого есть незнакомцы, покрасим в красное. Пусть таких набралось не менее 50.

Двух красных, которые не знакомы друг с другом, перекрасим в синий. Из оставшихся красных возьмём пару взаимно не знакомых — и тоже в синий. Если среди красных на каком-то шаге отсутствует пара взаимно не знакомых, то каждый из них не знаком с кем-то из синих, поэтому их тоже сделаем синими. Среди 50 синих нет того, кто знаком с остальными