Maths Olympiad Prep

Library / /18 of 21

, 2006

Combinatorics Difficulty 6.8 National Olympiad Prove it Vietnam

Let mm and nn be two integers greater than 33 and let be given a rectangular m×nm \times n board. At each step, one puts simultaneously 44 marbles into 44 cells of the board (each marble into a cell) so that these four cells form one of the following schemata.
Figure 1
Figure 2
Figure 3
Figure 4
Is it true that starting from a rectangular m×nm \times n board without marbles in it after a finite number of steps of appropriate puttings, one can put marbles into all cells of the board so that each cell is filled with a same (positive) number of marbles for all cells when:
i) m=2004m = 2004 and n=2006n = 2006?
ii) m=2005m = 2005 and n=2006n = 2006?
(At each step, it is not necessary that the four cells which are selected to put marbles into contained no marbles).

Solution

i) After two steps: one can put into each cell of a small board of size (4×2)(4 \times 2) a marble. One can partition the given board of size (2004×2006)(2004 \times 2006) into small boards of size (4×2)(4 \times 2). Therefore, after some steps, one can put marbles into all cells of the given board so that the number of marbles in each cell is the same for all cells.

ii) We now prove by contradiction that in the second case, the response to the problem is "no". Indeed, suppose that the contrary: after some steps, there would be kk marbles (k>0k > 0) in each cell of the given board of size (2005×2006)(2005 \times 2006). Color black all cells belonging to the odd rows and consider each non colored cell as white. Then, the number of black cells is equal to 1003×20061003 \times 2006 and the number of white cells is equal to 1002×20061002 \times 2006. But at each step we put exactly 22 marbles into black cells and 22 marbles in white cells. Therefore, after an arbitrary number of steps, the number of marbles in all black cells must be equal to the number of the marbles in all white cells. Consequently, we would have 1003×2006×k=1002×2006×k1003 \times 2006 \times k = 1002 \times 2006 \times k and so get 1=01 = 0. This contradiction proves our assertion.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.