Colouring a chessboard How can I demonstrate that I can colour a $2n\times\binom{2n}{2}$ chessboard, with $n$ different colours, such that there aren't $4$ separate unit squares of the same colour, the centers of which are vertices of a rectangle having sides parallel to the sides of the board? 
 A: Not a solution, but a start.  Let the $2n$ direction be rows and the ${2n \choose 2}$ direction be columns.  It seems obvious that you place two squares of a given color in each column, and each column is a different pair of rows.  There are just enough pairs of rows to do this.  If we can achieve this (that is, if one color doesn't get in another's way) we are done.  A quick sketch shows it works fine for $n=2$.  The problem comes for $n=3$.  It would be natural to step through the colors with columns like $112233, 122331, 223311, \ldots 311223, 123123, 312312, 213213$ but a problem arises with $1x1xxx$ as we can't fill that out with $2$'s and $3$'s with a single gap each.  This can be solved by mixing properly, giving $$123313212321123\\213221313132231\\131233221132312\\212132331213123\\331312122213231\\322121133321312$$ but I haven't found a nice formula or induction to show it always works.
A: As usual, $[m]=\{1,2,\dots,m\}$ for each $m\in\Bbb Z^+$, and for any set $S$, $[S]^2$ is the set of unordered pairs of elements of $S$. For a positive integer $m$ and integers $a$ and $b$ define $a\oplus_m b$ to be the unique $k\in[m]$ such that $a+b\equiv k\pmod m$. 
Now fix a positive integer $n$, and let $m=2n-1$. For $i,k\in\{0,\dots,m\}$ let $a_{i,k}=i\oplus_m k$, and let
$$b_{i,k}=\begin{cases}
0,&\text{if }i=k\\
a_{i,k},&\text{if }i\ne m\ne k\\
a_{i,i},&\text{if }i<k=m\\
a_{k,k},&\text{if }k<i=m
\end{cases}$$
It’s not hard to check that $a_{i,m}=a_{i,1}$ and then that $\{b_{i,0},\dots,b_{i,m}\}=\{0,\dots,m\}$ for $i=0,\dots,m$. Moreover, it’s clear that $b_{i,k}=b_{k,i}$ for $i,k\in\{0,\dots,m\}$. For $c\in[m]$ let 
$$P_c=\big\{\{i,k\}\in[m]^2:b_{i,k}=c\big\}\;,$$
and let $\mathscr{P}=\{P_c:c\in[m]\}$. Each $P_c\in\mathscr{P}$ is a partition of $[2n]$ into $n$ unordered pairs, and $\bigcup\mathscr{P}=[2n]^2$. For each $c\in[m]$ let $P_c=\big\{\{r_{c,k},s_{c,k}\}:k\in[n]\big\}$. 
Index the columns of the board by $[m]\times[n]$, partition the cells of column $\langle c,q\rangle$ according to $P_c$, and for $k\in[n]$ color the cells in rows $r_{c,k}$ and $s_{c,k}$ with color $k\oplus_nq$.
Suppose that $r,s\in[n]$, $\langle c,q\rangle,\langle d,p\rangle\in[m]\times[n]$, $r\ne s$, and the cells at the intersections of these rows $r$ and $s$ with columns $\langle c,q\rangle$ and $\langle d,p\rangle$ are all the same color. Then $\{r,s\}\in P_c\cap P_d$, so $c=d$, $\{r,s\}=\{r_{c,k},s_{c,k}\}$ for some $k\in[n]$, $k\oplus_nq=k\oplus_np$, and $q=p$, so that $\langle c,q\rangle=\langle d,p\rangle$. Thus, no rectangle with sides parallel to the sides of the board has all four corners the same color.
A: EDIT: This is not an answer; I tried.
As you follow this argument, it may help to keep the case $n=3$ in mind. Keep reading for a while before colorings and arrays come into play.
Consider the $n$ axes in $\mathbb{R}^n$. Give the standard basis vectors names $e_i$. Place a vertex at $\pm e_i$. Connect these vertices with edges in all $\binom{2n}{2}$ possible ways. Some of these edges ($n$ of them) are segments along the axes, and let's collect these edges in an ordered set $A=\{A_1,\ldots,A_n\}$. The rest form some kind of higher dimensional generalization of an octahedron. Let's name these edges $\pm e_i\pm e_j,i< j$. There is no literal addition or subtraction. For instance for $n=2$ we have $e_1+e_2,e_1-e_2,-e_1+e_2,-e_1-e_2$. Should $e_2-e_1$ arise, that means the same thing as $-e_1+e_2$.
For $k=2,3,\ldots n$, consider the ordered subset of these edges $S=\{e_1-e_2,e_2-e_3,\ldots,e_n-e_{1}\}$. No two edges in $S$ are adjacent since each vertex of the "octohedron" is present once. 
Now if only there were an orthogonal transformation $R$ with order $2(n-1)$ such that the orbits of $S$ covered all of the edges, I could proceed. It's easy to find that $R$ for $n=2,3$; we can envision $R$ as a rotation. But for higher $n$, I'm failing to find a generalization. If we had such an $R$, then we will have partitioned the $\binom{2n}{2}$ edges into $2(n-1)+1=2n-1$ blocks of size $n$; namely $A$ and the $R^kS$. Within each block, no two edges are adjacent. 
Now consider the array 
$$
\begin{array}{ccccc}
+e_1&+e_1&+e_1\cdots\\
-e_1&-e_1&-e_1\cdots\\
+e_2&+e_2&+e_2\cdots\\
-e_2&-e_2&-e_2\cdots\\
\vdots&\vdots&\vdots\\
+e_n&+e_n&+e_n\cdots\\
-e_n&-e_n&-e_n\cdots\\
\end{array}$$
with $\binom{2n}{2}$ columns. Identify each column with an edge from the graph. Each edge from the graph is in one of the ordered blocks we created, so note that in this way each column falls into one of those blocks.
In each column, locate the vertices that correspond to that column's associated edge, and color them the first color, let's say red. There cannot be a red rectangle, since that would imply we have two columns corresponding to the same edge.
$$\begin{array}{ccccc}
{\color{red}{+e_1}}&{\color{red}{+e_1}}&{\color{red}{+e_1}}\cdots\\
-e_1&-e_1&-e_1\cdots\\
+e_2&+e_2&+e_2\cdots\\
{\color{red}{-e_2}}&-e_2&-e_2\cdots\\
\vdots&\vdots&\vdots\\
+e_n&+e_n&+e_n\cdots\\
-e_n&-e_n&-e_n\cdots\\
\end{array}$$
In each column, look in the associated block and iterate to the next edge. Color those vertices the second color, blue. Again there will be no blue rectangle, since our blocks are disjoint.
$$\begin{array}{ccc}
{\color{red}{+e_1}}&{\color{red}{+e_1}}&{\color{red}{+e_1}}\cdots\\
-e_1&-e_1&-e_1\cdots\\
{\color{blue}{+e_2}}&{\color{blue}{+e_2}}&{\color{blue}{+e_2}}\cdots\\
{\color{red}{-e_2}}&-e_2&-e_2\cdots\\
+e_3&+e_3&+e_3\cdots\\
{\color{blue}{-e_3}}&{\color{red}{-e_3}}&-e_3\cdots\\
\vdots&\vdots&\vdots\\
+e_n&+e_n&+e_n\cdots\\
-e_n&-e_n&-e_n\cdots\\
\end{array}$$
Continue cycling this way through all the colors.
A: This is Corollary 3.7 (appears at the bottom of page 18) of Bill Gasarch et al's paper on Rectangle Free Colourings of Grids.
The paper is here: http://www.cs.umd.edu/~gasarch/papers/grid.pdf
There are a lot more results in there, if you are interested in them.
Good luck!
