Consider an 8x8 board divided in 64 unit squares. We call diagonal in this board a set of 8 squares with the property that on each of the rows and the columns of the board there is exactly one square of the diagonal. Some of the squares of this board are coloured such that in every diagonal there are exactly two coloured squares. Prove that there exist two rows or two columns whose squares are all coloured.
Problem
Source: Romanian JBTST VI 2007, problem 1
Tags: analytic geometry, geometry, rectangle, combinatorics proposed, combinatorics
08.06.2007 22:06
Ok, it id easier than I first thought : 1) Consider any diagonal and then its two coloured cells in different rows and columns. Assume that they are the ones with coordinates $(i,j)$ and $(r,s)$. Then consider the diagonal obtained from the one above by replacing the two coloured cells by the cells $(i,s)$ and $(r,j)$. Since this new diagonal has two coloured cells and that the initial one has no other coloured cells, it follows that these two new cells are coloured too. 2) There is no coloured cells which does not belong to row $j$ or $s$ and to columns $i$ or $r$, otherwise with the two first coloured cells above, we may find a diagonal with at least three coloured cells. 3) Wlog, assume that the four coloured cells in 1) are the ones in the upper left $2\times 2$ square, that are $(1,8),(2,8),(1,),(2,7).$ Now, assume that there exists a non-coloured cell in the upper row, say $(x,8)$ with $x>2.$. By considering this cell and $(2,7)$ and $(1,y)$ with $y <7$, we may complete them to form a diagonal and, using 2), we deduce that $(1,y)$ is coloured. Thus all the first column is coloured. We prove in the same way that the second column is coloured by considering $(2,y)$ instead of $(1,y).$ Therefore there are two coloured columns. If all the upper row is coloured, then as in 1), we deduce that all the second row from above is coloured, and we are done. Pierre.
09.06.2007 01:44