Question

Дам 50 балов пж помогите. Задача:В универстите учатся 2019 студентов.Алибек хочет поступить в этот универститет,но в этом учебном заведении есть 4 учеников нерях(короч типо комнату в чистоте не оставляют),а остальные чистые(назовём их так).Алибек может задавать вопрос:ты можешь сказать кто неряха.Чистые отвечают рондомно трех студентов,а неряхи выбирают точно остальных трех студентов нерях.Можно ли найти точно чистого пару для Алибека в комнату?​

Answer 1

Ответ:

Можно

Пошаговое объяснение:

Представим в графах.

Пусть ученики - это вершины, а ориентированные рёбра появляются если один указывает на другого.

Неряхи образуют четырёхугольник из которого наружу не выходит рёбер (но входить могут). Значит если найти вершину которая не входит не в один из таких четырёхугольников, то это точно чистый ученик. 2019 на 4 не делится значит граф не может состоять только из таких четырёхугольников и можно выделить чистого ученика.

Answer 2

Да, можно найти точно чистого пару для Алибека в комнате. Рассмотрим следующий алгоритм:

1. Алибек задает вопрос первому студенту, пусть он ответит, что, например, студент А - нерях.
2. Затем Алибек задает вопрос второму студенту, пусть он ответит, что студент Б - нерях.
3. Теперь Алибек знает, что студенты А и Б - неряхи, и студенты В, Г и Д - чистые.

Теперь сравним ответы трех чистых студентов на вопрос Алибека. Пусть они ответили так: студент В назвал студента Г, студент Г назвал студента В и студент Д назвал студента В. Теперь понятно, что студент В точно является чистым, так как все чистые студенты называют его. Остается только один чистый студент - это студент Д (поскольку остальные двое, В и Г, неряхи).

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