Задача о мулах на шахматной доске

[Ktina]

Шахматная фигура "мул" отличается от коня тем, что у него папа осёл что не может ходить вверх. Если конь с поля (i, j) может сделать ход на одно из восьми полей (i+1, j+2), (i+1, j-2), (i+2, j+1), (i+2, j-1), (i-1, j+2), (i-1, j-2), (i-2, j+1), (i-2, j-1), то мул - только на одно из четырёх полей (i+1, j-2), (i+2, j-1), (i-1, j-2), (i-2, j-1).

Какое наименьшее число мулов можно расставить на шахматной доске так, чтобы они били все поля?
(мул бьёт поле, на котором стоит)

[Sirion]

Очевидно, их должно быть не менее 18. А вот сколько точно - пока что ещё неочевидно...

[hippie]

Ответ: 21.

Расстановка:

MMMMMMMM
........
.MM.MM..
.M...MM.
........
.MMMMMM.
........
........
(к сожалению, не знаю, как здесь установить монотайпный шрифт, чтобы было понятнее).

Абсолютно очевидно, что мулов не меньше 20 (8-я горизонталь + вертикали a, b, g, h). Но доказательство, что их не меньше 21 (длинный тупой перебор) слишком длинное, чтобы приводить его здесь.

[arseniiv]

(Оффтоп)

hippie в сообщении #533890 писал(а):

(к сожалению, не знаю, как здесь установить монотайпный шрифт, чтобы было понятнее).

В этом случае подойдёт тег [code] (ещё пробелов наставил):

M M M M M M M M
. . . . . . . .
. M M . M M . .
. M . . . M M .
. . . . . . . .
. M M M M M M .
. . . . . . . .
. . . . . . . .

[Ktina]

А у меня с 21 симметричная расстановка получилась (если не ошиблась):
a8, b8, c2-8, d8, e2, e8, f8, g2-8, h8

(не совсем, конечно, симметричная)