Rearranging a $10 \times 10$ matrix of naturals $1\le n\le 100$ s.t. the sum of every two neighbouring numbers is composite in max. 35 steps

We are given a $10 \times 10$ matrix which contains every natural number between $1$ and $100$ in arbitrary order. We are to prove that it is always possible to rearrange the matrix by swapping any two entries of choice in at most 35 steps, such that in the resulting matrix every two neighbouring (horizontally or vertically, not diagonally) entries' sum is composite.

Naturally, one should begin with showing that such an arrangement is possible in the first place. A very simple example that sprang to mind is constructing the matrix s.t. the first 50 entries are occupied by odd numbers and the last 50 by even numbers. Then, the sum of every two odd entries is even and thus composite and the sum of every two even entries is also even and thus composite. We then need to ensure that the rows in the middle contain even-odd pairs that give composite numers, e.g. $2+7,5+10,12+9,14+11,24+3,20+13,18+17,16+23,37+8,43+6$. It is therefore possible to construct such a matrix.

However, I had some trouble proving that this can be achived by transforming any matrix in maximum 35 swappings. Can you transform any matrix to the configuration I have described in maximum 35 steps or do you need to construct a different configuration within the limits for that?

Does one actually need to demonstrate the procedure or can we prove this indirectly?

Thank you for your help.

Solution 1:

Your strategy is good. Putting odds on one side and evens on the other can clearly be done in $25$ swaps or fewer. You then want to repair the boundary.... working on one side only, set the boundary values so that each cross-boundary sum is divisible by three. This can be done in $10$ more swaps. Note that even in the worst case, where all the boundary values on the fixed side of the boundary are equal modulo $3$, you have $16$ candidate values on the other side to use in the pairing-off swaps.