# Pigeonhole question and generalization

Let H be a regular hexagon with side length 1 unit.

(a) Show that if more than 6 points are speci ed inside H then the points of at least one pair of them are at most 1 unit apart.

(b) State and prove a generalization of the result in (a) to the situation where there are in excess of $2^{2n+1}3$ points inside H.

I did part (a), I solved it using the Pigeonhole Principle. On the other side, I don't understand what part (b) is about. Any suggestions is more that appreciate it!!

• Let $H$ be a regular n-gon with side length 1 unit. show that if more than $2^{2n+1}3$ are specified inside $H$, then atleast one pair of them at most 1 unit apart. – GA316 Oct 30 '13 at 2:48
• @GA316 Thank you both, but I still don't get it. $2^{2n+1}3$ are the points, but if I proved it that more than 6 are at most 1 unit apart, what do I have to do for this question? – user99638 Oct 30 '13 at 2:56
• @doppz When n =1, then there are 12 points. The distance between then is still at most 1 unit, no? – user99638 Oct 30 '13 at 3:00
• use the same idea as (a). enough to prove there is "atleat one pair" which are one unit apart.Use Pigeon Hole Principle. – GA316 Oct 30 '13 at 3:00
• @GA316 Drawing the same conclusion from a stronger assumption, how is that a generalization? – bof Oct 30 '13 at 3:01

Hint: An equilateral triangle with sides of unit length can be split into $2^{2n}$ triangles of side length $\frac{1}{2^n}$.

As you noticed before, a regular hexagon with side lengths 1 can be split into 6 equilateral triangles of unit length. Thus, a regular hexagon with side lengths 1 can be split into $2^{2n+1}3$ equilateral triangles of side length $\frac{1}{2^n}$.

Now, how can you use the pigeonhole principle to prove a more general result for your part (b)?

• I don't see it.. What I am finding the most difficult is identifying when the PH Principle goes in. – user99638 Oct 30 '13 at 3:30
• The use of the PHP is the same as in part (a) which you did. Put more than 7 points in 6 triangles, two points will be in the same triangle. Put more than 24 points in 24 triangles, two points will be in the same triangle. – bof Oct 30 '13 at 3:47
• And more generally, if you have more than $2^{2n+1}3$ points and $2^{2n+1}3$ triangles, two points will be in the same triangle. – Dennis Meng Oct 30 '13 at 3:48

In case $n=0$ you have more than $6$ points in $H$. You solved that by dissecting $H$ into $6$ equilateral triangles of side $1$; by the pigeonhole principal, two of the points must be in the same triangle.

In case $n=1$ you have more than $24$ points in $H$. Now you want to dissect $H$ into $24$ congruent equilateral triangles. You do that by subdividing each of the $6$ triangles into four smaller triangles of side $\frac12$.

• n = 1, then there are more than 12 points, no 24. right? – user99638 Oct 30 '13 at 3:21
• it is obvious that the more points there are in a triangle, and the smaller the triangles get, then the closer the points will be with respect to each other. – user99638 Oct 30 '13 at 3:22
• If $n=1$ then $2^{2n+1}\cdot3=2^{2\cdot1+1}\cdot3=2^3\cdot3=8\cdot3=24$. – bof Oct 30 '13 at 3:41
• The idea is to divide the hexagon into a number of little triangles. If you put more points in the hexagon than there are triangles, then two points will be in the same triangle, so the distance between those two points is less than or equal to the longest side of the triangle. – bof Oct 30 '13 at 3:50
• sorry, I was thinking $2^{n+1}$ – user99638 Oct 30 '13 at 3:51