geometry
Question –
Given a hexagon of side 2 and 25 points inside it, show that there are atleast 2 among them which are at most a unit apart..
My try –
I know pigeon hole principle will apply taking 8×3 =24 regions so that atleast one region will contain more than 1 points or atleast 2 points…..but i.am not able to draw these 24 regions so that distance apart is at most a unit
…. kindly give me hint…
Your idea of constructing the graph is good.
Hint: Proceed by induction. Consider a vertex (not on the edge) of the convex hull. Show that it can be connected to at most 3 other vertices.
Note: This is a common competition problem.
Putting $10$ points in a square of size $1$ such that the minimal distance $d_{\text{min}}$ between two points is maximized, is exactly the same as finding an arrangement of $10$ non-overlapping disks of radius $r=d_{\text{min}}/2$ with center in the unit square with the maximum radius possible (look at the second picture below). Note that these disks are getting out of the unit square but form the most dense packing of $10$ spheres of the square of size $1+2r$. So the problem is equivalent to the disk packing in a square. According to wikipedia (or directly the exhaustive main reference of the wikipedia article), the best known packing of $10$ spheres in a square gives us a minimal distance $$d_{\text{min}}= 0,421...$$ This is significantly better then the original bound $\sqrt{2}/3=0.47...$ found by the grid and pigeon hole principle.
Before finding the Wikipedia article I played with geogebra and the best packing I found is the one below, one can compute the radius and find $d_{\text{min}}=(\sqrt{2 \left(1+2 \sqrt{2}\right)}-2)/(2 \left(2 \sqrt{2}-1\right))=0.419...$ which is not as good as the one mentioned aboved (you want to maximize $d_{\text{min}}$).
Best Answer
A hexagon can be decomposed into 6 equilateral triangles, and each equilateral triangle can be further decomposed into 4 smaller equilateral triangles. Can you finish from there?