4. Let $n$ be a positive integer. Find the smallest positive integer $k$ with the property that for any colouring of the squares of a $2 n \times k$ chessboard with $n$ colours, there are 2 columns and 2 rows such that the 4 squares in their intersections have the same colour.
4. The answer is $2 n^{2}-n+1$.

Consider an $n$-colouring of the $2 n \times k$ chessboard. A vertical-pair is a pair of squares in the same column that are coloured the same. In every column there are at least $n$ vertical-pairs. Let $P$ be the total number of vertical-pairs and $P_{i}$ be the number of vertical-pairs with colour $i$. Then $P=P_{1}+\cdots+P_{n} \geq n k$. Thus there is colour $i$ with $P_{i} \geq k$. There are $\binom{2 n}{2}=2 n^{2}-n$ pairs of rows. Thus if $k \geq 2 n^{2}-n+1$, there is a pair of rows that contains two vertical-pairs with colour $i$.

Next for $k=2 n^{2}-n$, exhibit an $n$-colouring where no such sets of 4 squares exists. Note that it suffices to find such an $n$-colouring for the $2 n \times(2 n-1)$ board. We can then rotate the colours to obtain $n$ of these boards which can then be put together to obtain the requiring $n$-colouring of the $2 n \times\left(2 n^{2}-n\right)$ board. For each $i=1,2, \ldots, 2 n-1$, let $A_{i}=\{(i, 2 n-1+i),(i+1,2 n-2+i), \ldots,(n-1+i, n+i)\}$, where $2 n+k, k>0$, is taken to be $k$. Note that the pairs in each $A_{i}$ give a partition of $\{1,2, \ldots, 2 n\}$. Moreover, each pair of elements appears in exactly one $A_{i}$. Now colour the squares of column $i$ using $n$ colours so that the two squares in each pair of $A_{i}$ receive the same colour and the colours the $2 n$ pairs are mutually distinct. This gives an $n$-colouring of the $2 n \times 2 n-1$ board with the required property and we are done.