в некоторой группе людей из 100 человек среди любых десяти есть трое попарнол знакомых. можно ли выбрать восьмерых из них так чтобы любой из - вопрос №2566343

оставшихся был знаком с кем то из этих восьмерых

Ответы

Да, таких восьмерых человек можно выбрать из этой группы в 100 человек. Докажем это методом от противного. Действительно, предположим, что требуемой группы из восьми человек не существует. Это означает,  что какую бы произвольную группу из восьми человек мы не выбрали, среди оставшихся 92 человек обязательно найдётся хотя бы один, назовём его А1, который не знаком ни с одним из этих 8 человек. Тогда добавляем этого А1 в нашу группу из 8 человек, а какого-то другого человека Б1 выкидываем из нашей группы. Итак,  у нас снова есть некоторая новая группа из  8 людей.  Тогда, ввиду исходного предположения, среди оставшихся 92 человек снова найдётся хотя бы один (А2), который не знаком ни с одним из этих 8 людей. Добавляем его в нашу группу,  а какого-то третьего, Б2, отличного от А1, выкидываем из нашей группы.  Снова имеем группу из  8 человек, и аналогичную процедуру продолжаем повторять дальше.    Очевидно, что через некоторое количество таких повторений мы создадим группу из  8 человек, в которой никто не знаком друг с другом!  Более того, согласно исходному предположению, среди оставшихся 92 людей найдётся один, обозначим его А9, не знакомый ни с одним из этих 8 в нашей группе попарно незнакомых людей!  Мы легко добавляем этого А9 в нашу группу эгоистов! Итак, у нас есть группа 9 человек, никто из которых не знаком  друг с другом!!! Развязка близка! Мы добавим в эту нашу группу девяти людей любого из оставшихся 91.  Таким образом мы имеем группу из 10 человек.  В этой группе очевидно нет троих попарно знакомых людей. Противоречие.
26.08.17

Михаил Александров

Эксперт месяца
Читать ответы

Андрей Андреевич

Читать ответы

Eleonora Gabrielyan

Читать ответы
Посмотреть всех экспертов из раздела Учеба и наука > Математика
3 ответа
15.05.11
Вопрос задан анонимно
Пользуйтесь нашим приложением Доступно на Google Play Загрузите в App Store