Решение задачи 275

Условие:

В дебатах участвовали 9 кандидатов. Каждый заявил: "Кандидат, чей номер равен последней цифре квадрата моего номера -- рыцарь". Выяснилось, что среди них были рыцари, но их было не более трех. Кто из них кто?

Решение:

Представим задачу в виде ориентированного графа, в котором вершины это кандидаты, и если кандидат А говорит, что кандидат В рыцарь, то от вершины А к вершине В идет стрелка. Граф выглядит так:

Он состоит из трех компонент связности. Кандидаты с номерами 1, 5, 6 указывают сами на себя. Пусть кандидат A утверждает, что кандидат B рыцарь. Тогда если А рыцарь, то В тоже рыцарь, и наоборот. Получается, если хоть один кандидат из компоненты связности рыцарь, то все кандидаты из компоненты связности рыцари. Отсюда следует, что кандидат 5 рыцарь, а остальные лжецы.

Ответ: Кандидат 5 рыцарь, остальные лжецы.