a) Is it possible to place $2024$ checkers on a board $70 \times 70$ so that any square $2 \times 2$ contains even number of checkers? b) Is it possible to place $2023$ checkers on a board $70 \times 70$ so that any square $2 \times 2$ contains odd number of checkers?
Problem
Source: Serbia JBMO TST 2024 P3
Tags: combinatorics
26.05.2024 14:42
Is it me or this is actually hard? A lot of global summation/colouring ideas fail (if one relies only on parity) since there are examples in a) with 2450 (chessboard) and in b) with 1225 (cells with odd coordinates). Sketch for a): Each connected component must be a rectangle and any component has to have at least one other component with a common vertex (but not even common side length 1 as otherwise them together would form a single component). Moreover, messing around with gluing components etc. shows that a configuration works if and only if the associated configuration with checkered $a \times b$ rectangle on top left and $(70-a) \times (70-b)$ on bottom right works. But $ab + (70-a)(70-b) = 2024$ has no solution in positive integers $a, b < 70$, since it is equivalent to $(a-35)(b-35)+163 = 0$ and $163$ is prime.
27.05.2024 16:05
Here's a crazy example for b) by @daninnm. Suppose the table is initially white. Change the colour of all cells in rows $2,1,3,5,7,9,11$, then in all cells in columns $2,4,6,\ldots,26$ and then in all cells which are at an odd row and odd column. We put a checker in a cell if and only if its final colour is black. The total amount is $7*(70-13)+13*(70-7)+29*35-6*35 = 2023$.
30.12.2024 18:47
For A cant we just: $\begin{bmatrix} 506 & 506 &... \\ 506& 506 &... \\ ...& ...& ... \end{bmatrix}$?
30.12.2024 19:18
You can't place two or more checkers in the same cell I believe wizixez wrote: For A cant we just: $\begin{bmatrix} 506 & 506 &... \\ 506& 506 &... \\ ...& ...& ... \end{bmatrix}$?