Навчання / Бібліотека / Головоломки

Мирні коні на малій дошці

ГоловоломкиСкладне

Яка найбільша кількість коней, що можна поставити на дошку $5$ на $5$ , не більше одного на клітинку, так, щоб жоден кінь не бив іншого? Кінь б’є клітинки, на які може піти шаховий кінь, тобто клітинки на відстані $2$ в одному напрямку й $1$ в іншому.

Для перевірки відповіді потрібен JavaScript. Підказка й розв’язок відкриваються і без нього.

Підказка

Кінь завжди переходить на клітинку протилежного кольору шахівниці. Для верхньої оцінки об’єднайте клітинки, що б’ють одна одну, в пари.

Розв’язок

Кінь завжди переходить на клітинку протилежного кольору шахівниці, тож коні на всіх $13$ клітинках кольору кутів нічого не б’ють, а отже $13$ можливо.
Для верхньої оцінки пронумеруйте рядки й стовпці від $1$ до $5$ ; $12$ пар $(1, 2) - (3, 1)$ , $(1, 4) - (2, 2)$ , $(2, 1) - (4, 2)$ , $(2, 3) - (4, 4)$ , $(2, 5) - (1, 3)$ , $(3, 2) - (5, 1)$ , $(3, 4) - (1, 5)$ , $(4, 1) - (5, 3)$ , $(4, 3) - (5, 5)$ , $(4, 5) - (2, 4)$ , $(5, 2) - (3, 3)$ , $(5, 4) - (3, 5)$ розділені кожна ходом коня, і лише клітинка $(1, 1)$ лишається без пари.
З кожної пари може стояти щонайбільше один кінь, тож поміститься щонайбільше $12 + 1$ коней.
Отже, найбільша кількість дорівнює $13$ .

Відповідь: $13$

Наступна задача Назад до бібліотеки