Yasha writes in the cells of the table $99 \times 99$ all positive integers from 1 to $99^2$ (each number once). Grisha looks at the table and selects several cells, among which there are no two cells sharing a common side, and then sums up the numbers in all selected cells. Find the largest sum Grisha can guarantee to achieve.
Problem
Source: Caucasus MO 2024, Seniors P4
Tags: combinatorics
bin_sherlo
15.03.2024 16:07
Answer: $\frac{9901.4901+1}{2}=24017351$ Second player colours the board as a chess board. One of the black coloured or white coloured squares' sum must be at least half of the sum of the numbers written on the board. Proof: $A$ writes $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 2i&99^2-2i+1 \\\hline 2i+1&99^2-2i+2\\\hline \end{array} $$for $96x96$. $A$ writes $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 2i+1&99^2-2i+1 \\\hline 2i&99^2-2i+2\\\hline m&m+2\\\hline \end{array} $$or $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 2i+1&99^2-2i+1& m\\\hline 2i&99^2-2i+2&m+2\\\hline \end{array} $$for the rest part except the right bottom $3x3$ square. $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 2 & 9800&100& 9702&.&4706&5097&4805\\\hline 3& 9801& 101&9703&.&4705&5098&4807\\\hline 4& 9798&102&9700 &.&4708&5095&4809\\\hline 5& 9799&103&9701&.&4707&5096&4811\\\hline .&.&.&.&.&.&.&.\\\hline .&.&.&.&.&.&.&.\\\hline .&.&.&.&.&.&.&.\\\hline .&.&.&.&.&.&.&.\\\hline .&.&.&.&.&.&.&.\\\hline .&.&.&.&.&.&.&.\\\hline 99& 9704&197&9606&.&X&X&X\\\hline 98&9705&196&9607&.&X&X&X\\\hline 4804&4806&4808&4810&.&X&X&X\\\hline \end{array} $$For the right bottom $3x3$ square, we want to have at most $1$ difference between black and white squares with writing the numbers $(4802,4803,5000,5001,1,4996,4997,4998,4999)$. We can do it by writing $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 5001&5000&4996\\\hline 4803&4802&4997\\\hline 4999&4998&1\\\hline \end{array} $$