7 попарно знакомых людей

[qwert129]

В группе из 42 человек каждый знаком, по крайней мере, с 36 людьми из группы. Докажите, что в этой группе найдется компания из 7 человек, в которой все знают друг друга.

[Yadryara]

Собственные попытки решения последуют?

[Gagarin1968]

qwert129 в сообщении #1622979 писал(а):

В группе из 42 человек каждый знаком, по крайней мере, с 36 людьми из группы

qwert129
В этой задаче отношение "знаком" симметричное?

[qwert129]

да , если человек знаком , то другой тоже знаком с ним.

-- 19.12.2023, 13:10 --

Yadryara в сообщении #1622985 писал(а):

Собственные попытки решения последуют?

собстваенные попытки ни к чему не привели. Я лишь пришел к тому что если взять что максимум 6 попарно знакомых если мы их уберем, то найдутся минимум группа из 36 людей , где каждый знаком c 30 людьми и при этом для любого найдется человек который не знаком с ним.

[Gagarin1968]

Выберите какого-то человека А, он с кем-то знаком. Назовём этого знакомого В.
Скажите, со сколькими людьми знакомы А и В вместе?

[Doctor Boom]

Странно, у меня выходит максимум 6

[ihq.pl]

Doctor Boom в сообщении #1623030 писал(а):

Странно, у меня выходит максимум 6

наверняка, ошибка в условии)

[Doctor Boom]

ihq.pl
Ага, легко контрпример придумать - шесть групп из семи попарно незнакомых людей

[Sinoid]

Gagarin1968 в сообщении #1622990 писал(а):

qwert129 в сообщении #1622979 писал(а):

В группе из 42 человек каждый знаком, по крайней мере, с 36 людьми из группы

qwert129
В этой задаче отношение "знаком" симметричное?

Еще можно добавить обычный в таких задачах вопрос: а это отношение рефлексивно?

[Gepidium]

Doctor Boom в сообщении #1623034 писал(а):

легко контрпример придумать - шесть групп из семи попарно незнакомых людей

не, этот контрпример не катит.
Даже если какой-то человек из группы знаком со всеми людьми из других групп, то максимум его знакомых 35. А по условию задачи каждый знаком как минимум с 36 людьми.
А это значит, что он должен быть знаком еще по меньшей мере с одним человеком из его родной группы. Противоречие.в Вашем контрпримере.

[Doctor Boom]

Gepidium
А себя то я и не приметил Тогда да, 7. Идея такая же, разбиваем на 7 подгрупп по 6 человек

[ihq.pl]

Doctor Boom в сообщении #1623042 писал(а):

разбиваем на 7 подгрупп по 6 человек

То есть, взяв наугад по человеку из каждой подгруппы, обязательно получим нужную семерку? Но кто-нибудь из 42 может не знать шестерых, и тогда один человек в семерке может не вписаться.

-- 20.12.2023, 01:45 --

Такой вариант. Возьмем одного человека. Допустим, он не знает шесть человек. Из $(42-7)$ оставшихся ему знакомых выберем второго. Допустим, второй тоже не знает шесть человек, и пусть пересечение множеств незнакомцев первого и второго пусто. Из $(42-14)$ оставшихся выбираем третьего общего знакомого. Пусть и у него шесть незнакомых, и пересечение множеств незнакомцев всех трёх пусто. Из $(42-21)$ оставшихся выбираем четвертого. Рассуждаем также и выбираем из $(42-28)$ оставшихся пятого, а из $(42-35)$ - шестого. Седьмого выбрать не получится, потому что $42-42=0$. Но такого не может быть, т.к. у каждого из выбранных таким образом шестерых оказалось бы по $35$ знакомых. Поэтому пересечение множеств незнакомцев не пусто, и седьмой обязательно найдется.

[Gagarin1968]

ihq.pl в сообщении #1623049 писал(а):

Допустим, он не знает шесть человек.

ihq.pl
А если допустить, что он не знает четверых? Или что он знаком со всеми? И Ваше доказательство рушится.
Нет, в таких задачах в доказательстве должны фигурировать слова "по крайней мере", "как минимум" или "по меньшей мере".
Но подожду топикстартера.

[ihq.pl]

Gagarin1968 в сообщении #1623059 писал(а):

Но подожду топикстартера.

На самом деле Doctor Boom уже решил. Сейчас только дошло, что 7 подгрупп по 6 незнакомых друг с другом - это самый худший из всех возможных раскладов, потому что у одного человека не может быть больше пяти незнакомых

[Gagarin1968]

ihq.pl в сообщении #1623063 писал(а):

На самом деле Doctor Boom уже решил.

Doctor Boom решил совсем другую задачу, а именно: в группе из 42 человек каждый знаком ровно с 36 определёнными людьми из группы. Докажите, что в этой группе найдется компания из 7 человек, в которой все знают друг друга.
Согласитесь, что это несколько отличается от первоначальной постановки задачи.

ihq.pl в сообщении #1623063 писал(а):

Сейчас только дошло, что 7 подгрупп по 6 незнакомых друг с другом - это самый худший из всех возможных раскладов, потому что у одного человека не может быть больше пяти незнакомых

Вы не сможете разделить людей на группы (даже в самом худшем раскладе), потому что Вы не знаете, кто с кем знаком. Вам известно только, что у каждого человека есть не меньше 36 знакомых, или, что то же самое, не больше 5 незнакомцев. И Вам именно в этих условиях нужно доказать наличие компании из 7 знакомых.
Такую задачу можно решить с помощью графа, а можно и обычным школьным рассуждением.
Но подожду топикстартера.