В этой задаче запутаются все.
В прошлый раз мы решали задачу про хакатон и неразбериху с местами. После того как все наконец уселись, выяснилось, что среди любых пяти программистов есть хотя бы один, кто знает всех остальных из пятёрки.
При каком количестве Х участников хакатона может оказаться так, что как минимум один из них точно знаком со всеми?
Решаем как математики
Сначала докажем, что если количество участников хакатона чётное, то среди них может не быть программиста, знакомого со всеми. Пусть X = 2Y, где Y — целое число больше 2. В этом случае всех участников хакатона можно разбить на Y пар.
Представим, что в каждой из таких пар участники не знакомы друг с другом, а два любых из разных пар — знакомы. Тогда получается, что нет ни одного программиста из любых пяти, кто знает всех остальных.
Если же количество участников нечётное, то каких бы 5 программистов мы ни взяли, среди них может быть не больше двух таких пар. Значит, кто-то из пяти программистов не будет знать кого-то в паре с ним, но будет знаком с остальными четырьмя программистами из пяти. Получается, что x должно быть нечётным.
Теперь докажем, что знакомый со всеми программист найдётся при всех нечётных X > 5. Представим, что каждый программист не знаком хотя бы с одним участником хакатона. Тогда при нечётном x участников у нас будет программист Миша, который не знает минимум двух других участников, например Максима и Иру. Если бы это было не так, всех программистов можно было бы разбирать на пары. Тогда два любых программиста из X − 3 участников знакомы, иначе они с Мишей, Максимом и Ирой образовали пятёрку, а это противоречит условию.
Возьмём двух программистов из числа участников X − 3, например Машу и Кирилла. Хотя бы один из них знаком с Мишей, Максимом и Виталием, иначе пятёрка Миша, Максим, Виталий, Маша и Кирилл противоречила бы условию. Поэтому этот программист — Маша или Кирилл — знаком со всеми участниками хакатона. Получается, что x — все нечётные больше 5.
