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.
Identical colored squares in plane
-
0You 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. – 2011-11-20
-
1For 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)$. – 2011-11-20
-
0what 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..... – 2011-11-21
-
0No, @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. – 2012-05-11
-
0One nice consequence of the requirement that square edges be parallel to table edges is this: Three squares pairwise intersecting implies overlap of all three. – 2012-05-11
-
1If you like this kind of problem, it's number 11 on page 3 of http://individual.utoronto.ca/alexrem/MiscellaneousProblems.pdf (but no solutions are given there). – 2012-05-14
-
0Thanks!In fact, first of all I found the problem in that article! – 2012-05-15
-
0Unfortunately the link to the problem page is broken, but I found the solution page: http://www.mit.edu/~alexrem/MiscellaneousProblemsSolutions.pdf – 2014-01-23
1 Answers
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$)