Дам 50 балов пж помогите.
Задача:
В универстите учатся 2019 студентов.Алибек хочет поступить в этот универститет,но в этом учебном заведении есть 4 учеников нерях(короч типо комнату в чистоте не оставляют),а остальные чистые(назовём их так).Алибек может задавать вопрос:ты можешь сказать кто неряха.Чистые отвечают рондомно трех студентов,а неряхи выбирают точно остальных трех студентов нерях.Можно ли найти точно чистого пару для Алибека в комнату?
Задача:
В универстите учатся 2019 студентов.Алибек хочет поступить в этот универститет,но в этом учебном заведении есть 4 учеников нерях(короч типо комнату в чистоте не оставляют),а остальные чистые(назовём их так).Алибек может задавать вопрос:ты можешь сказать кто неряха.Чистые отвечают рондомно трех студентов,а неряхи выбирают точно остальных трех студентов нерях.Можно ли найти точно чистого пару для Алибека в комнату?
More Questions From This User See All
Answers & Comments
Ответ:
Можно
Пошаговое объяснение:
Представим в графах.
Пусть ученики - это вершины, а ориентированные рёбра появляются если один указывает на другого.
Неряхи образуют четырёхугольник из которого наружу не выходит рёбер (но входить могут). Значит если найти вершину которая не входит не в один из таких четырёхугольников, то это точно чистый ученик. 2019 на 4 не делится значит граф не может состоять только из таких четырёхугольников и можно выделить чистого ученика.