Каждый ход шахматного коня — перемещение на одну клетку по горизонтали и две по вертикали, либо наоборот — одну по вертикали и две по горизонтали. (На рисунке справа конь, отмеченный буквой К, может за один ход переместиться в любую из затемнённых клеток.)
В произвольной клетке прямоугольной доски размером 2 × 2016 клеток стоит шахматный конь. Перемещаясь по описанному правилу (и не выходя при этом за края доски), он может из этой клетки попасть в некоторые другие клетки доски, но не во все. Какое наименьшее количество клеток нужно добавить к доске, чтобы конь мог из любой клетки доски попасть во все остальные? (Добавление клетки происходит так, чтобы она имела общую сторону с одной из уже имеющихся. Добавлять можно любое количество клеток, получившаяся при этом доска не обязательно должна иметь прямоугольную форму).
Занумеруем клетки как показано на рисунке 1. Конь может из любой клетки попасть в любую клетку с таким же номером, и не может попасть в другие.
Таким образом, все клетки разбились на 4 множества, так что конь не может перескочить из одного множества в другое, но может свободно перемещаться внутри одного множества.
Добавим две клетки как на рисунке 2. Докажем, что теперь конь может попасть из любой клетки в любую другую. Клетка А соединяет клетки, отмеченные розовым цветом, т. е. через ней можно из множества 1 перескочить в множество 4. (Находясь в любой клетке с номером 1, можно прийти в розовую клетку с номером 1, затем через A попасть в розовую клетку с номером 4, и из ней в любую клетку с номером 4. В итоге из любой клетки с номером 1 можно с помощью А попасть в любую клетку с номером 4.)
Клетка В соединяет клетки, отмеченные зелёным, т. е. через ней можно из любого из множеств 2, 3, 4 перескочить так же в любое из этих множеств.
В итоге, сочетая клетки A, B, можно из любого множества попасть в любое другое. Например чтобы попасть из множества 1 в множество 2, вначале с помощью А попадаем из 1 в 4, затем с помощью В попадаем из 4 в 2.
Осталось убедиться, что одной клетки не хватит. Из рисунка 3 видно, что все добавляемые клетки разбиваются на два вида: в клетки А можно попасть не больше чем из 3 клеток доски, в клетки В можно попасть из 4-х клеток, но среди них всегда есть две из одного множества (отмеченные одинаковой цифрой). Т. е. клетки, в которую можно попасть из всех 4-х множеств, не существует.
Ответ: 2.