10
$\begingroup$

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.

  • 0
    Unfortunately the link to the problem page is broken, but I found the solution page: http://www.mit.edu/~alexrem/MiscellaneousProblemsSolutions.pdf2014-01-23

1 Answers 1

2

Let's induct on the number of colors, $n$

When $n$ is 2 (as @goodarz suggests) we do the following:
Take the left-most of the squares, stick a pin each in its upper right and lower right corners, and have thereby secured all squares of the other color.

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$)