"Симметричные" шашки

[Ktina]

Ход в "симметричных" шашках делается так: некоторая шашка А выбирает другую шашку Б и ходит на поле, симметричное А относительно Б (при условии, что это поле не занято). Например, если на полях е4 и е5 стоит по шашке, то шашка, стоящая на е4, может пойти на е6, а шашка, стоящая на е5, может пойти на е3.

Расставьте на доске 8х8 максимально возможное число шашек таким образом, чтобы любая шашка могла сделать ход.

[Dave]

Максимально возможное число шашек: 60. Их нужно расставить по всем клеткам, кроме четырёх угловых, т.е. так:

$$\begin{bmatrix} \, & \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc & \,\\ \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc\\ \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc\\ \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc\\ \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc\\ \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc\\ \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc\\ \, & \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc & \circledcirc & \, \end{bmatrix}$$

[Ktina]

Dave в сообщении #511316 писал(а):

Максимально возможное число шашек: 60. Их нужно расставить по всем клеткам, кроме четырёх угловых

Их нужно расставить по всем клеткам, кроме четырёх угловых, а затем доказать, что большее число шашек расставить подобным образом не удастся

[Dave]

Для доказательства пронумеруем вертикальные ряды доски не буквами, как это принято в шахматно-шашечной нотации, а цифрами от 1 до 8 (так же, как и горизонтали) и будем обозначать каждую клетку парой её координат $(x,y)$, т.е., к примеру, клетку a2 обозначим парой (1,2).
Для начала заметим, что ход шашки $(a,b)$ через шашку $(p,q)$ на поле $(c,d)$ возможен тогда и только тогда, когда

$$\begin{cases} a + c = 2p,\\ b + d = 2q. \end{cases}$$

Отсюда, в частности, следует, что ход на некоторую клетку $A$ возможен только с клеток, координаты которых имеют ту же чётность, что и координаты клетки $A$ (да и то, если посередине между ними есть шашка). Нетрудно посчитать, что клеток с такими координатами на доске ровно $4\cdot4=16$ (включая клетку $A$). Таким образом, одна пустая клетка может "покрывать" возможный ход не более, чем для $15$ шашек и сама занимать одно место. Поэтому всего незанятых клеток должно быть не менее $64/16=4$, т.е. шашек - не более $64-4=60$.
Что касается доказательства правильности вышеприведённого расположения 60 шашек, то для шашки $(a,b)$ ход производится следующим образом - шашка прыгает на поле $(c,d)$ через шашку $(p,q)$, где

$$c=\begin{cases} 1,&\text{если $a$ - нечётное;}\\ 8,&\text{если $a$ - чётное,} \end{cases} d=\begin{cases} 1,&\text{если $b$ - нечётное;}\\ 8,&\text{если $b$ - чётное,} \end{cases} p=(a+c)/2, \; q=(b+d)/2.$$

Очевидно, что клетка $(c,d)$ - угловая, числа $p$ и $q$ - целые, находятся в диапазоне от 1 до 8 и хотя бы одно из них не равно ни 1, ни 8, ибо в противном случае клетка $(a,b)$ была бы угловой, т.к., к примеру, $p=1 \; \Rightarrow \; a=1$, а $q=8 \; \Rightarrow \; b=8$. Значит клетка $(p,q)$ - не угловая и на ней находится шашка, через которую и нужно совершать ход шашкой $(a,b)$.

[Ktina]

Очень красивое и развёрнутое доказательство!