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

Нерівні стоси монет

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

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

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

Підказка

Обчисліть XOR $4$ розмірів і з’ясуйте, який стос можна зменшити, щоб XOR став $0$ .

Розв’язок

Позиція в цій грі програшна для того, хто ходить, тоді й лише тоді, коли XOR розмірів стосів дорівнює $0$ .
Крок за кроком: $6$ XOR $10$ дає $12$ , далі $12$ XOR $15$ дає $3$ , далі $3$ XOR $21$ дає $22$ .
Стос розміру $s$ можна зменшити до $s$ XOR $22$ , лише якщо це менше за $s$ ; для цього стос має містити старший біт числа $22$ , тобто $16$ , а він є лише в $21$ .
Тож стос із $21$ монети зменшується до $21$ XOR $22$ , тобто до $3$ , і тоді XOR чисел $6$ , $10$ , $15$ і $3$ дорівнює $0$ .
Виграшний хід забирає $21 - 3 = 18$ монет, тож відповідь $18$ .

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

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