any idea??? Carlos Bravo

Can you give a hint? At least an upper bound.

The answer is n=10

for n=10 we can painted like this(any 11 columns of it satisfied the problem)

Attachments:

for n=11,find all pairs of squares which is in the same column and have the same colour. In every column,there is at least $C_4^2+C_3^2+C_3^2=12$ pairs. So there is at least $12\times 12=144$ pairs. So at least one of the colours has 48 pairs of squares like that. But their positions in the rows has only $C_{10}^2=45$ different conditions. So there must be two pairs in the same rows.And they kill the problem. ($C_n^m$ is the binomial coefficient).

Hi everybody. My first post here. My English (and math, I should probably add) is terrible: please forgive my mistakes in advance... Anyway, with jin's trick you can bound the different boards that can be painted. More specifically, you can prove the impossibility for 4x19, 5x16, 7x13 and 10x12. It's also quite easy/not too difficult to colour cases 3x<whatever>, 4x18, 6x15, 9x12. These facts cover all the possible boards, except for 10x10, 10x11 and 11x11. The first turns out to be possible, whereas the other two are not. Impossibility for 11x11 is a little harder, but 10x11 is definitely the most difficult (supposing I am not mistaken ;-) ). Anyone wants to try? M.

The example can be generalized for any prime power quantity of colors. Suppose there are $p^k$ colors. We can build a grid of size $(p^k)^2\times ( p^k\cdot ( p^k + 1) )$ without a rectangle with monochromatic corners. To do this look at the vector space $\mathbb F_{p^k}^2$ (the space of dimension $2$ over the field with $p^k$ elements). Each row is going to correspond to one of the vectors in $(\mathbb F_{p^k}^2$. And therefore every column just corresponds to a coloring of all the vectors using $\mathbb F_{p^k}$ colors. Notice that there are $p^k+1$ lines that pass through the origin. Each such line $L$ is going to give us $p^k$ columns as follows: Look at the lines parallel to $L$, they partition the entire space. We label the $p^{k}$ parallel lines $l_1,l_2,...,l_{p^k}$. We are now ready to define the $p^k$ colorings the correspond to $L$. The $i'th$ coloring that corresponds to $L$ is going to paint the vectors of line $l_j$ with color $i+j$. To check that this works we just have to pick two columns and pick a color $c$. We have to check that the vectors of color $c$ in the first column and the second column share at most one vector. Notice that these sets are two lines in a vector space and so they intersect at at most one point. This is unless the two lines are the same, which is clearly never the case. The case $10\times 12$ is when $p^k=2^1$.