Could it be n^2-1? If that is the answer, I might have found something that looks like a solution and I could post it later, but I don't feel compfortable enough right now. Sorry for my English and my modal-verb-mania.

Mmmm, maybe that was not a very appropriate question in a subforum called "unsolved problems" . I'll try not to say too many stupid things. First of all, given a pair of two different unit squares inside a square of side n other than those two made up from the one in the first row and column and the one in the last row and column or the one in the first column and last row and the one in the last column and first row (from now we will call them korners ), there exists a corner which contains both, so they must have different colours. This means that the minimum number of colours needed for a single n-sided square is at least n^2-2, and hence k>=n^2-2. It is possible to show that for n>2, we have k>n^2-2. Suppose for the sake of contradiction (if there are mistakes in my English, I think it's better that they sound funny) that k=n^2-2; then, by the above observation, two opposite korners of any square of side n in the lattice must be of the same colour. Take such a square and call 1, 2 .. n the colours of the u.squares in the leftmost column and n, n+1 ... n+(n-2), 1 the colours in the rightmost one (reading top-down). If we consider for both columns in the square the 2 whole infinite column in the latttice in which each one is contained, is easy to see that they must be colored in the cycle 1, 2, 3, .... n+(n-2)=2n-2. For instance, the u.s. just below the one colored with n in the left column of the n-square must have colour n+1, since it is an "opposite korner" of the one coloured with n+1 in the right column. For the same reason, the u.s. just below the one coloured with 1 in the right column must be coloured with 2. It is not difficult to formalize the induction step (). Since this argument holds for every pair of columns n-1 squares away from each other, we can state that every column is coloured in a cycle of lenght 2n-2 which repeats (even if "out of phase", can I say?) every n-1 columns (a sort of cycle of cycles). But if this happened, a colour could not appear in more than two different cycles, because it would mean there exists a u.s coloured with that colour which is at a horitzontal distance strictly less than n-1 from a column whose cycle contains that colour and at a vertical distance less or equal to n-1 ( [((2n-2)+1)/2] ) from a u.s of the same colour of that column, so being contained in the same corner as another u.s. of the same colour. This gives a total of k=(2n-2)(n-1), but (2n-2)(n-1)>n^2-2 for n>2. In the case n=2 the minimum is obviously k=2 and can be attained with a chessboard colouring. For n>2 the minimum k=n^2-1 can be attained in the following way. Our aim is to find a set of n^2-1 u.s. such that the whole lattice can be tesselated (well said?) from it in such a way that for each of the translations transforming one into another of the resulting sets of u.s. happens that either one of its components (vertical or horizontal) exceeds n-1 in absolute value or the absolute value of both their components is exactly n-1. If we colour differently each u.s. of the initial set and colour the other sets in the tesselation in the same way, for every two u.s. of the same colour would happen that either they are hor. or vertic. more than n-1 units away or that they are exactly n-1 units away in each direction; in both cases it would not be possible for them to be in the same corner. Take a square of side n and take out its bottom right korner (sorry again). Then apply all the traslations resulting of a linear integer combination of the vectors (n-1, -n+1) and (n, 1): that can be such a tesselation. [ I now nothing about the theme, but I suppose the shape fo the initial set is somehow superfluous and that what really matters is the pair of vectors from which combination you divide the lattice into equivelency classes (is it correct in English?). To begin with, its vectorial product: n^2-1. Any advice on where to find more about it? ] Sorry again for the possible mistakes in language or maths and for such a clumpsy demonstration.

i think you are correct the answer is indeed $n^{2}-1$. during the contest, the main thing in the problem was to write it down very well explained. i lost two points because i supposed too many things "obvious"

Mimoide wrote: For n>2 the minimum k=n^2-1 can be attained in the following way. Our aim is to find a set of n^2-1 u.s. such that the whole lattice can be tesselated (well said?) from it in such a way that for each of the translations transforming one into another of the resulting sets of u.s. happens that either one of its components (vertical or horizontal) exceeds n-1 in absolute value or the absolute value of both their components is exactly n-1. If we colour differently each u.s. of the initial set and colour the other sets in the tesselation in the same way, for every two u.s. of the same colour would happen that either they are hor. or vertic. more than n-1 units away or that they are exactly n-1 units away in each direction; in both cases it would not be possible for them to be in the same corner. Take a square of side n and take out its bottom right korner (sorry again). Then apply all the traslations resulting of a linear integer combination of the vectors (n-1, -n+1) and (n, 1): that can be such a tesselation. Please someone explain the construction. I don't understand it.

Nobody? I don't think it's clear at all, or even correct...