In an $8\times 8$ square, what's the min number of dots to be placed so that there's always a pair with distance apart at most $\sqrt8$?

89 Views Asked by At

By the Pigeon Hole Principle (PHP), we know that when we are to place $17$ dots in an $8 \times 8$ square, then there will always be a pair with distance $< \sqrt8$. However, does PHP actually prove that "$17$" is the minimum number of dots required? I.e.. maybe $13$ dots are already enough to have at least a pair with distance apart $< \sqrt8$?

1

There are 1 best solutions below

0
On

By the way, the minimum is at least $14$ because the following placement of $13$ dots yields minimum distance $2.928765827>2\sqrt{2}$:

X       Y 
0.00000 2.14185 
0.00000 5.07063 
0.00000 8.00000 
1.99757 0.00000 
2.53622 6.53532 
2.96492 2.90621 
4.92635 0.00000 
5.07245 5.07067 
5.07245 8.00000 
6.46319 2.49317 
8.00000 0.00000 
8.00000 4.98635 
8.00000 7.91537 

enter image description here