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
    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.2011-11-20
  • 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)$.2011-11-20
  • 0
    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.....2011-11-21
  • 0
    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.2012-05-11
  • 0
    One 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
  • 1
    If 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
  • 0
    Thanks!In fact, first of all I found the problem in that article!2012-05-15
  • 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