Гра в квадрати

Аліса та Боб грають з $k$-вимірним прямокутним паралелепіпедом, що складається з n_1 \times n_2 \times \ldots \times n_k одиничних гіперкубів. Вони по черзі роблять ходи. Аліса починає, обираючи одиничний гіперкуб і розрізаючи паралелепіпед через центр цього гіперкуба всіма можливими площинами, паралельними його граням. Усі одиничні гіперкуби, які перетинає хоча б одна площина, видаляються, а те, що залишається, — це серія менших прямокутних паралелепіпедів. Вимагається, щоб принаймні одна з цих менших частин мала довжини ребер, які попарно є взаємно простими з відповідними довжинами ребер початкового паралелепіпеда. Також дозволяється зробити розріз так, щоб не залишилося жодної частини.

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

Розглянемо приклад. Нехай k = 2, і у нас є прямокутник 6 \times 5. Розрізавши гіперкуб у точці $(1,4)$, ми отримуємо дві частини: 5 \times 1 та 5 \times 3. Оскільки (зокрема друга, хоча й перша теж, але це не принципово) довжини ребер другої частини є взаємно простими з відповідними довжинами початкового прямокутника ($5$ — взаємно просте з $6$, а $3$ — з $5$), це дозволений хід. Однак розріз у точці $(3,2)$ — недозволений хід, тому що жодна з отриманих частин (2 \times 1, 3 \times 1, 2 \times 3, 3 \times 3) не задовольняє наведену вище умову.