This nice and hard problem was proposed by Nikolay Beluhov, Bulgaria

Define a $k$-star to be the polyomino with $2k^2 - 2k + 1$ squares which consists of all squares with top left corner $(x,y)$ for $x,y$ integers and $|x| + |y| < k$. (So a 2-star is an X pentomino.) If we place any 25-star in the plane, all 1201 squares it colors are different, because the rectangle having as opposite corners any two squares of a 25-star has perimeter at most 100. So every 25-star contains a square of every color. Fix a color $A$ and for each square colored $A$, place a 25-star centered on that square. These 25-stars must cover every square on the plane exactly once. We claim that there are only two possible ways to cover the plane in 25-stars: choose $e \in \{-1,1\}$ and coordinatize each square on the plane with integer coordinates so that a 25-star is centered at $(0,0)$, then $(x,y)$ is colored $A$ if and only if $x = 25i + 24ej$ and $y = 24i - 25ej$ for some integers $i,j$. This claim would imply the problem.

Generalizing this problem and solution is straightforward; replace the 100 with $4k$ and 1201 with $2k^2 - 2k + 1$.

Can't the problem be generalised for the plane painted in $\left\lceil \frac{n^2}{2} \right\rceil$ colours so that no rectangle with a perimeter over $2(n+1)$ has same-coloured squares? I.e. should the perimeter condition necessarily be of form $4k$?

If you generalize the solution I had to perimeters 2 mod 4, you get a similar less-pointy star shape, and you can make a similar claim about there not being many ways to cover the plane with that shape. But the conclusion that any $1 \times c$ rectangle (where there are $c$ colors) contains all $c$ colors does not hold. For example, if the condition is for rectangles perimeter 10 and there are 8 colors, then we can color as follows ... 123412341234 567856785678 341234123412 785678567856 ... Though it's possible a similar conclusion holds for some other rectangle with area equal to the number of colors, maybe $n \times 2n$.

I'm sure I miss something if there is a rectangle 1201*1 or 1*1201 contains two squares of the same colour, then we can find a rectangle with perimeter 100 that contains two squares of the same colour. where is a mistake please. thankyou

reveryu wrote: I'm sure I miss something if there is a rectangle 1201*1 or 1*1201 contains two squares of the same colour, then we can find a rectangle with perimeter 100 that contains two squares of the same colour. where is a mistake please. thankyou Not really, in a $1\times 1201$ rectangle you can find $12$ rectangles with perimeter 100 with no common squares. So you won't necessarily find a 100 perimeter rectangle with two squares of the same colour.