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

Парні перевертання в ряду монет

ГоловоломкиЛегке

$12$ монет лежать в ряд. Монети на позиціях $1$ , $3$ , $4$ , $8$ , $9$ і $12$ показують решку, а всі інші показують орла. Один хід вибирає $2$ сусідні монети й перевертає обидві. Яка мінімальна кількість ходів потрібна, щоб усі $12$ монет показували орла?

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

Підказка

Уявіть кожну монету з решкою як фішку. Хід може зсунути фішку на одне місце, прибрати $2$ сусідні фішки або створити $2$ .

Розв’язок

Кожен хід перевертає $2$ монети, тож решки зникають парами, а пару решок на відстані $d$ можна прибрати за $d$ ходів (зсунути одну решку на $d - 1$ місць, а потім прибрати обидві), але не менше.
Отже, мінімум — це найдешевше з’єднання $6$ решок у пари за відстанню, а на прямій найдешевше з’єднання поєднує сусідів по порядку.
Решки на $1, 3$ , $4, 8$ і $9, 12$ мають відстані $2$ , $4$ і $3$ , а будь-яке інше парування коштує більше (наприклад, $1, 3$ , $4, 9$ , $8, 12$ коштує $11$ ).
Мінімальна кількість ходів дорівнює $2 + 4 + 3 = 9$ .

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

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