Разделы 
Дополнительно
Задача по математике - 3132
2019-05-19 
В математическом кружке принимают участие 100 школьников. Известно, что среди любых четырех участников кружка всегда найдется, по меньшей мере, один, знакомый с остальными тремя. Доказать, что существует участник кружка, знакомый со всеми остальными 99 школьниками. Каким может быть число школьников, знакомых со всеми остальными?
Решение:
Возьмем произвольного участника А. Если А знаком со всеми остальными 99 школьниками, то утверждение доказано. Будем поэтому считать, что А не знаком с некоторым участником В.
Рассмотрим некоторого школьника С. Если С знаком со всеми остальными 99 школьниками, то утверждение доказано. Будем поэтому считать, что С не знаком с некоторым участником кружка.
Пусть С не знаком со школьником D. Тогда среди четырех участников А, В, С и D кружка ни один не знаком со всеми остальными тремя. Противоречие.
Пусть С не знаком с одним из школьников А и В, Для определенности будем считать, что С не знаком с А. Рассмотрим некоторого школьника D. Как показано выше, D знаком со всеми участниками кружка, кроме, может быть, А, В, С.
Рассмотрим четырех участников А, В, С и D кружка. Один из них знаком со всеми остальными тремя. Но ни один из школьников А, В, С этим свойством не обладает. Значит, D знаком с А, В и С, то есть D знаком со всеми остальными 99 школьниками.
Рассуждение, проведенное выше, показывает, что в кружке найдутся хотя бы 97 школьников, знакомых со всеми остальными. С другой стороны, ясно, что таких школьников может быть ровно 97.
Итак, наименьшее число школьников в кружке, знакомых со всеми остальными, равно 97.
В математическом кружке принимают участие 100 школьников. Известно, что среди любых четырех участников кружка всегда найдется, по меньшей мере, один, знакомый с остальными тремя. Доказать, что существует участник кружка, знакомый со всеми остальными 99 школьниками. Каким может быть число школьников, знакомых со всеми остальными?
Решение:
Возьмем произвольного участника А. Если А знаком со всеми остальными 99 школьниками, то утверждение доказано. Будем поэтому считать, что А не знаком с некоторым участником В.
Рассмотрим некоторого школьника С. Если С знаком со всеми остальными 99 школьниками, то утверждение доказано. Будем поэтому считать, что С не знаком с некоторым участником кружка.
Пусть С не знаком со школьником D. Тогда среди четырех участников А, В, С и D кружка ни один не знаком со всеми остальными тремя. Противоречие.
Пусть С не знаком с одним из школьников А и В, Для определенности будем считать, что С не знаком с А. Рассмотрим некоторого школьника D. Как показано выше, D знаком со всеми участниками кружка, кроме, может быть, А, В, С.
Рассмотрим четырех участников А, В, С и D кружка. Один из них знаком со всеми остальными тремя. Но ни один из школьников А, В, С этим свойством не обладает. Значит, D знаком с А, В и С, то есть D знаком со всеми остальными 99 школьниками.
Рассуждение, проведенное выше, показывает, что в кружке найдутся хотя бы 97 школьников, знакомых со всеми остальными. С другой стороны, ясно, что таких школьников может быть ровно 97.
Итак, наименьшее число школьников в кружке, знакомых со всеми остальными, равно 97.
