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
10
$\begingroup$
geometry
combinatorics
-
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