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
pbornsztein
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.
MellowMelon
09.06.2007 01:44
Label the columns $a,b,c\ldots$ and the rows $1,2,3\ldots$. Begin by considering the main diagonal $a1-h8$. It must have two colored squares. WLOG rearrange the rows and columns so that they are on $a1$ and $b2$. Then diagonals containing $a1$ and $b2$ can contain any square within the rectangle defined by $c3$ and $h8$, and since the diagonal must have exactly two colored squares ($a1$ and $b2$), none of the squares in that rectangle can be colored.
Now consider the diagonal containing $a3, b2, c1$ and any other 5 squares we know are not colored. We know $b2$ is colored, so either $a3$ or $c1$ is colored.
Assume $a3$ is colored. Then the diagonals containing $b1,a3$ and $b2,a3$ show that no square on columns $c-h$ is colored. And then by necessity the entire $a$ and $b$ columns must be colored to satisfy the conditions. If $c1$ is colored, the entire $1$ and $2$ rows are colored by a similar argument. This completes the proof.