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

Хто спорожнить, той програє

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

Є $3$ коробки, у яких $1$ , $4$ і $6$ кульок. $2$ гравці ходять по черзі; хід полягає в тому, щоб забрати будь-яку додатну кількість кульок рівно з однієї коробки. Той, хто забере останню кульку, програє. Ви ходите першим, обидва гравці грають оптимально. Рівно один перший хід гарантує вам виграш. Скільки кульок забирає цей хід?

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

Підказка

Поки в якійсь коробці лежить $2$ або більше кульок, грайте так само, як у звичайній грі, де забрати останню кульку вигідно.

Розв’язок

У цьому варіанті правило те саме, що й у звичайній грі, доки хоча б в одній коробці є щонайменше $2$ кульки: ходіть так, щоб XOR розмірів дорівнював $0$ .
Лише наприкінці, коли після вашого ходу в кожній коробці лишиться щонайбільше $1$ кулька, ви натомість залишаєте непарну кількість одиничних кульок.
Тут $1$ XOR $4$ дає $5$ , а $5$ XOR $6$ дає $3$ , тож позиція для вас виграшна.
Лише коробку з $6$ кульок можна зменшити до $6$ XOR $3$ , тобто до $5$ ; лишаються $1$ , $4$ і $5$ , з XOR $0$ , і ще є коробка, більша за $1$ .
Отже, виграшний хід забирає $6 - 5 = 1$ кульку, і відповідь $1$ .

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

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