Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 9 down vote favorite
5

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.

share|improve this question
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
1  
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
1  
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
show 2 more comments

1 Answer

up vote 2 down vote

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.