Suppose you have a $8\times 8$ square board where the number on the square in column $i$ and row $j$ is $(j-1)8+i$ you have to place knights on the board so no two knights threaten each other and the sum of the numbers on which the knights are is maximized. How can we do this?
My conjecture is that the solution is given by coloring the board as a chessboard and picking any of the colors for the positions of the knights, either color will add up to $1040$. However I have not managed to prove it is indeed the max. Thank you very much
Regards.
The result is in fact $1040$.
Consider the graph where the vertices are the squares and edges are given by knight moves.
First note that the vertices of the graph can be split into $16$ cycles of length $4$.
To prove this it suffices to notice it is true for the $4\times 4$ grid.
We now show that for each cycle the sum of the tiles on the cycle that have a knight can be at most half of the total sum of the squares. One way to see this is to note that the center mass of two opposite vertices in a cycle is the same as the center of mass of the other two opposite vertices in the cycle (and since our expression is of the form $ai+bj+c$ the result follows).
So we can change $(j-1)8+i$ for $ai+bj+c$ with $a,b,c \geq 0$ and it still works.