Прав ли ИИ Вася, который утверждает, что может поменять стрелочки не более чем в 10 клетках так, что после этого можно будет обойти всю доску 5 х 5, начав с какой то клетки и следуя по стрелочкам (посетив каждую клетку по разу)?

Question

Вопрос:

Прав ли ИИ Вася, который утверждает, что может поменять стрелочки не более чем в 10 клетках так, что после этого можно будет обойти всю доску 5 х 5, начав с какой то клетки и следуя по стрелочкам (посетив каждую клетку по разу)?

Фотография

Ответ ассистента

Accepted Answer

Да, ИИ Вася прав. Вот как это можно сделать: Представь себе шахматную доску 5x5. Раскрасим её в шахматном порядке в чёрные и белые клетки. Всего на доске 25 клеток, значит, 13 клеток будут одного цвета (например, чёрного), а 12 – другого (белого). Теперь сделаем так, чтобы все стрелки из чёрных клеток вели в белые клетки, а все стрелки из белых – в чёрные. Это значит, что нужно будет поменять направление стрелок на тех клетках, где это условие не выполняется. В самом худшем случае, нам придётся поменять направление стрелок на всех 12 клетках одного цвета (например, белого), потому что стрелки на чёрных клетках и так будут показывать куда надо. Так как 12 меньше 10, то это невозможно сделать. Теперь, если мы начнём обход с любой клетки, мы будем попадать из клетки одного цвета в клетку другого цвета, пока не обойдём всю доску.

Ответ ассистента

Другие решения