On a board of $8 \times 8$ exists $64$ kings, all initially placed in different squares. Alnardo and Bernaldo play alternately, with Arnaldo starting. On each move, one of the two players chooses a king and can move it one square to the right, one square up, or one square up to the right. In the event that a king is moved to an occupied square, both kings are removed from the game. The player who can remove two of the last kings or leave one last king in the upper right corner wins the game. Which of the two players can ensure victory?
Problem
Source: Cono Sur 2024
Tags: combinatorics
mijail
29.09.2024 18:02
Solved with Enigma714.
Bernaldo wins, let's see his strategy:
First divide the squares of the board with the numbers $1,2,3,4$ as in the above figure, then consider at all times the associated quadruple $(x_1,x_2,x_3,x_4)$ where each $x_i \in \{0,1\}$ represents the parity of the number of kings that are in the squares with numbers $i$, at the beginning Arnaldo is in the quadruple $(0,0,0,0)$, note that after each move the parity of exactly two entries of the quadruple changes.
Now if you choose any two different numbers $A,B \in \{1,2,3,4\}$ it always holds that one (e.g. A) of those numbers holds that any square with that number can go to a square with the other number (resp. B), the verification of this can be done manually or see the guide graph.
guide graph
So every time Arnaldo changes the quadruple to one with two 1 inputs and two 0 inputs, Bernaldo could bring this quadruple back to $(0,0,0,0)$ ensuring that Bernaldo cannot lose.
alexgsi
02.10.2024 01:05
mirza5
03.11.2024 16:48
Fake solve noob???
mirza5
03.11.2024 16:50
Symmtery?
Nguyen
30.12.2024 17:42
Since the parity of the amount of kings is invariant, the game must end with removing two last kings, "leave one last king in the upper right corner" seems meaningless. But it makes sense if I want to determine the winner at any position. First, we notice that, if we can change the rule such that no king is removed, and multiple kings can be in one square, the player who moves all kings to the upper right corner wins, the winning player does not change. This is because if a player wins in the original rule, in the new rule, if his opponent moves a king that would have been removed in the original rule, he can move the king that would have been removed together with that king to the same square. As such, the board can be split into multiple boards, with each board holding one king. Since the moves of the kings are irreversible, it's easy to think about the Sprague-Grundy theorem. The SG value of each square is the mex of the SG values of the squares that can be reached from it, which is 1 less than the value in the table posted by mijail. 1 0 1 0 1 0 1 0 2 3 2 3 2 3 2 1 1 0 1 0 1 0 3 0 2 3 2 3 2 1 2 1 1 0 1 0 3 0 3 0 2 3 2 1 2 1 2 1 1 0 3 0 3 0 3 0 2 1 2 1 2 1 2 1 A position is a second player win iff the XOR of the SG values of the kings equals 0. Since the SG values are at most 3, the second player wins iff the amount of kings in the squares with SG value 1, 2 and 3 have the same parity.