1
$\begingroup$

By placing 27 squares with side $1$ in a circle with radius $2$, such that each square is entirely inside the circle, prove that there exists a point that 3 squares share (inside of their area).

I thought about dividing the circle into 9 equal areas and using the pigeonhole principle, but got stuck there. Any hint will help.

$\endgroup$
  • $\begingroup$ Well, what should I assign it to? It is a question I got at my combinatorics course. $\endgroup$ – Eliads Mar 15 '18 at 13:58
  • $\begingroup$ @idk Ok, thank you! didn't know about that tag. $\endgroup$ – Eliads Mar 15 '18 at 14:01
  • $\begingroup$ It belongs to correct tag just add the tag "Pigeonhole principle " $\endgroup$ – Rohan Shinde Mar 15 '18 at 14:03
  • $\begingroup$ @Manthanein thank you $\endgroup$ – Eliads Mar 15 '18 at 14:04
1
$\begingroup$

To get the desired conclusion, $26$ unit squares will suffice.

Let $D$ denote the disk of radius $2$, and let $C$ be the subregion of $D$ covered by some placement of $26$ unit squares within $D$.

Suppose every point of $D$ is contained in at most two of the unit squares.

Our goal is to derive a contradiction.

Let $X_i$ denote the $i$-th unit square.

For each $i$, let

  • $A_i$ be the subset of $X_i$ which does not intersect any of the other squares.$\\[4pt]$
  • $B_i = X_i{\setminus}A_i$.

For a given set $S$, let $[S]$ denote the area of $S$. \begin{align*} \text{Then}\;\; 4\pi&=[D]\\[4pt] &\ge [C]\\[4pt] &= \sum_{i=1}^{26}[A_i] + \left({\small{\frac{1}{2}}}\right) \sum_{i=1}^{26}[B_i]\\[4pt] &\ge \left({\small{\frac{1}{2}}}\right) \sum_{i=1}^{26}[A_i] + \left({\small{\frac{1}{2}}}\right) \sum_{i=1}^{26}[B_i]\\[4pt] &= \left({\small{\frac{1}{2}}}\right) \sum_{i=1}^{26}\left([A_i] + [B_i]\right)\\[4pt] &= \left({\small{\frac{1}{2}}}\right) \sum_{i=1}^{26}\,(1)\\[4pt] &= \left({\small{\frac{1}{2}}}\right)(26)\\[4pt] &= 13\\[4pt] \end{align*} contradiction.

This proves the claim.

Note:

Squares are an awkward shape for covering a large subregion of a disk, so I suspect the actual maximum number of unit squares which can be placed in a disk of radius $2$, such that each point of the disk is covered by at most two of the unit squares, is a lot less than $25$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Such an elegant solution! Thank you very much. $\endgroup$ – Eliads Mar 17 '18 at 12:04
0
$\begingroup$

Lets denote by $A$ the area that the squares occupy.

Of course $A\leq4\pi$(the area of the circle). Let's also suppose that there are no 3 squares that share a point.

Therefor only $2$ squares can intersect, i.e. $A>\frac{27}{2}$, so $$8\pi>27$$ which is false

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Shouldn't ie be $14$ instead of $27/2$ ? $\endgroup$ – Yves Daoust Mar 15 '18 at 14:22
  • $\begingroup$ @YvesDaoust $14>27/2$ so it works even better, doesn't really matter in my opinion $\endgroup$ – razvanelda Mar 15 '18 at 14:23
  • $\begingroup$ How did you get to these numbers ? $\endgroup$ – Eliads Mar 15 '18 at 14:24
  • $\begingroup$ @Eliads What numbers $\endgroup$ – razvanelda Mar 15 '18 at 14:25
  • $\begingroup$ @razvanelda $A > 27/2$ and $14$ $\endgroup$ – Eliads Mar 15 '18 at 14:25
0
$\begingroup$

@razvanelda: With your reasoning wouldn’t 26 squares be sufficient in order to force 3 squares to have a common interior point since $8\pi>26$ is also false?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yes it would be, so?... $\endgroup$ – razvanelda Mar 17 '18 at 10:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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