Question

Можно ли расставить на шахматной доске 11 коней так, чтобы каждый бил
ровно двух других?​

Answer 1

Ответ:

Нет

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

Пусть такая расстановка построена.

Тогда построим граф: его вершины - кони, а ребра соединяют лишь коней, бьющих друг друга.

Тогда из каждой вершины исходит ровно 2 ребра, т.е. получен 2-регулярный граф на 11 вершинах.

2-регулярные графы состоят из разрозненных циклов.

Число ребер в цикле на n вершинах равно n. А тогда общее кол-во ребер в разрозненных циклах равно сумме числа вершин в каждом из циклов - а значит число ребер в полученном графе равно 11.

Но тогда по крайней мере один цикл имеет нечетную длину (иначе сумма чисел ребер была бы четной).

Введем на доске своеобразную систему координат: середина нижней левой клетки имеет координаты (0;0), а единичный отрезок - длина стороны клетки.

Выберем произвольного коня с координатами (a;b), принадлежащего указанному циклу нечетной длины. Тогда координаты коня, которого бьет данный, имеют вид (a+x1;b+x2), где x=(x1;x2) - один из векторов (-2;1),(-1;2),(1;2),(2;1),(2;-1),(1;-2),(-1;-2),(-2;-1) [по сути, это интерпретация хода коня]

Пусть длина цикла [число ребер цикла] равна n - нечетное число.

Выбираем любое из ребер, инцидентных (a;b), и в этом направлении обходим цикл. В какой-то момент, после n переходов, попадем в исходную вершину (a;b). Но тогда сумма векторов, задающих сдвиги в соседнюю вершину цикла, равна 0.

А тогда $k_1(-2;1)+k_2(-1;2)+k_3(1;2)+k_4(2;1)+k_5(2;-1)+k_6(1;-2)+k_7(-1;-2)+k_8(-2;-1)=0$

Число сдвигов равно n, а тогда $k_1+k_2+k_3+k_4+k_5+k_6+k_7+k_8=n$

Получаем систему:

$\begin{equation*} \begin{cases} -2k_1-k_2+k_3+2k_4+2k_5+k_6-k_7-2k_8=0, \\ k_1+2k_2+2k_3+k_4-k_5-2k_6-2k_7-k_8=0, \\ k_1+k_2+k_3+k_4+k_5+k_6+k_7+k_8=n. \end{cases}\end{equation*}$

Сложив все уравнения, получим

$2k_2+4k_3+4k_4+2k_5-2k_7-2k_8=n\\ 2(k_2+2k_3+2k_4+k_5-k_7-k_8)=n$

Т.е. n кратно 2 - но n нечетно - противоречие.

А значит такой расстановки не существует