# Identical colored squares in plane

Several identical paper squares of $n$ different colors are lying on a rectangular table, with sides of the squares parallel to the sides of the table. Among any $n$ squares of pairwise distinct colors, it is possible to find $2$ which can be pinned to the table using one pin. Prove that all the squares of a certain color can be pinned to the table using $2n-2$ pins.

-
You have to use the geometry of the squares to prove this. If $n=2, K(3,3)$ (with edges representing overlap) violates it, but I don't think you can create it with squares. – Ross Millikan Nov 20 '11 at 22:23
For what it’s worth, you can formulate it as follows. You have a finite $S\subseteq\mathbb{R}^2$ and a function $c:S\to[n]$ such that if $A\subseteq S$ and $c\upharpoonright A:A\to[n]$ is a bijection, there are $p,q\in A$ s.t. $\|p-q\|_\infty<1$. The goal is to show that there is a set $P\subseteq\mathbb{R}^2$ and a $k\in[n]$ s.t. $|P|=2n-2$ and $\forall p\in c^{-1}[\{k\}]\exists q\in P(\|p-q\|_\infty<1)$. – Brian M. Scott Nov 20 '11 at 22:55
what is geometry of squares?? and BTW for $n=2$, there is an easier way, just consider the leftmost square. squares of the other color satisfy the conditions. I really don't think this needs that much of mathematics because I picked it up from an olympiad paper..... – Goodarz Mehr Nov 21 '11 at 4:54
No, @RossMillikan is right: use of the geometry of the squares is crucial. His counterexample that ignores the shape/size/orientation requirements is enough to show this. – Ternary May 11 '12 at 15:26
If you like this kind of problem, it's number 11 on page 3 of individual.utoronto.ca/alexrem/MiscellaneousProblems.pdf (but no solutions are given there). – Gerry Myerson May 14 '12 at 23:46

Let's induct on the number of colors, $n$
When $n$ is 2 (as @goodarz suggests) we do the following:
Now assuming the statement holds for $n-1$:
Take the left-most square $s$ and stick a pin each in its upper right and lower right corners (just as before). Now examine all unpinned squares of a different color from $s$. Either we have just pinned the entirety of some color (and are done with just 2 pins), or we're left with the $n-1$ case (since none of these squares overlap with $s$) and can find a color from among the $n-1$ remaining that can be pinned with $2(n-1)-2$ pins (and so, in our full set of squares, have pinned that color with $2n-2$)