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

Пляшки в ряд

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

$15$ пляшок стоять у ряд на місцях від $1$ до $15$ . $2$ гравці ходять по черзі; хід полягає в тому, щоб збити або $1$ пляшку, що стоїть, або $2$ пляшки, що стоять на сусідніх місцях. Пляшки не пересуваються, тож збита пляшка лишає проміжок, який розділяє ряд. Виграє той, хто зіб’є останню пляшку. Ви ходите першим, обидва гравці грають оптимально. Перший хід визначається множиною пляшок, які він збиває. Скільки різних перших ходів гарантують вам виграш?

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

Підказка

Дзеркальна відповідь працює після ходу в центрі, але виграшними можуть бути й інші перші ходи: надайте кожному відрізку ряду значення й поєднайте ці значення.

Розв’язок

Якщо збити пляшку на місці $8$ , лишаться $2$ ряди по $7$ , і дзеркальне повторення кожного ходу суперника з іншого боку дає виграш, тож виграшний хід існує.
Щоб порахувати всі виграшні ходи, надайте кожному ряду з $n$ пляшок значення $g (n)$ : найменше ціле невід’ємне число, якого немає серед XOR значень частин, що лишаються після його ходів.
Звідси значення від $g (0)$ до $g (14)$ такі: $0$ , $1$ , $2$ , $3$ , $1$ , $4$ , $3$ , $2$ , $1$ , $4$ , $2$ , $6$ , $4$ , $1$ , $2$ , і перший хід виграє тоді й лише тоді, коли XOR значень рядів, які він лишає, дорівнює $0$ .
Жоден хід, що збиває $2$ пляшки, не підходить, а збиття $1$ пляшки виграє, коли лишаються ряди з $1$ і $13$ , $5$ і $9$ або $7$ і $7$ пляшок, у будь-якому порядку.
Це пляшки на місцях $2$ , $6$ , $8$ , $10$ і $14$ , тож відповідь $5$ .

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

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