You are given 64 stones labelled with number 1 to 64 each. All those stones are randomly placed on the squares of a 8x8 chess board such that each square is occupied with exactly one stone. A move is defined by exchanging the stones of two squares. The goal of those moves is to get a constellation where the sum of any two adjacent numbers either horizontally, vertically or diagonally is not a prime number.
Can this be achieved with a maximum of 26 moves?
I claim the answer is
yes.
Strategy:
Split the board in the middle either horizontally or vertically and place all even numbers in one half, all odds in the other. Line the frontier with numbers that are all congruent x modulo 3 on one side and congruent -x on the other. Make sure 1 and 2 are not next to each other.
Can this always be achieved in 26 moves?
By swapping the minorities (in terms of even/odd) out of each half we can get the even-odd separation in no more than 16 swaps. If 1 and 2 are already on the right sides and happen to be next to each other then: 1. If the halves were unbalanced (in terms of odd and even) we didn't have to spend all 16 moves to unmix them and can spare a move to swap either 1 or 2 away from the frontier. 2. If the halves were balanced the choice which side we made even and which one odd was arbitrary and we can take it back and reverse it. Now 1 and 2 are sitting on the wrong sides and we can make sure that when it is each one's turn to be swapped they will not end up on the frontier.
Write down the residue classes mod 3 of the 8 even stones lining the frontier and minus the residue classes of their odd counterparts. By pigeon hole principle there are at least 6 matching and we have just the right number of swaps left to replace the other 10 with correct parity, correct residue class mod 3.
