Odleglosc miedzy punktami w kwadracie

[olgalagowska]

Ile punktow musi zostac wybranych w srodku kwadratu o boku \(\displaystyle{ 2}\), zeby byc pewnym ze odleglosc pomiedzy przynajmniej jedna para punktow wynosi nie wiecej niz \(\displaystyle{ \sqrt{2}}\)?

[Adifek]

Pięć.

Dzielimy kwadrat przekątnymi na 4 przystające trójkąty. Zauważmy, że każdy z nich jest połową kwadratu o boku \(\displaystyle{ \sqrt{2}}\) i dwa dowolne punkty z takiego trójkąta (do trójkąta zaliczymy także jego brzeg) leżą w odległości mniejszej bądź równej \(\displaystyle{ \sqrt{2}}\).

Wybieramy punkt w kwadracie. Jeśli jest na środku, to od razu każdy inny będzie od niego w odległości mniejszej bądź równej \(\displaystyle{ \sqrt{2}}\). Załóżmy więc, że wybraliśmy z jednego z trójkątów.

Wybieramy teraz drugi punkt - ponownie załóżmy, że nie jest to punkt przecięcia przekątnych - żeby się nie trywializowało (dalej już będę miał to założenie w domyśle). Leży więc w którymś z trójkątów. Jeśli w tym, co poprzedni, to mamy już parę. Załóżmy jednak, że leży w innym.

Wybieramy trzeci punkt. Jeży w którymś z trójkątów, które już mają w sobie punkty, to mamy naszą parę. Jeśli nie - idziemy dalej.

Wybieramy czwarty punkt podobnie. Zakładamy, że nie leży w żadnym wcześniej wykorzystanym trójkącie. Leży więc w ostatnim "wolnym".

Teraz wybierając piąty punkt nie mamy już wolnych trójkątów, więc musi leżeć w pewnym trójkącie z wraz z pewnym innym punktem. Te dwa punkty tworzą nam szukaną parę.


Zatem 5 w zupełności wystarcza. Skąd wiemy, że nie mniej?
Ano wystarczy sobie wybrać 4 punkty dostatecznie blisko wierzchołków wyjściowego kwadratu (bądź same wierzchołki) i widzimy, że każda para jest od siebie oddalona o więcej niż \(\displaystyle{ \sqrt{2}}\).

[tometomek91]

Można mniej pisać:
dzielimy kwadrat na cztery kwadraty - każdy z nich jest wpisany w okrąg o promieniu \(\displaystyle{ \frac{\sqrt{2}}{2}}\), z Dirichleta mamy, że dla 5 odległość między każdymi dwoma jest mniejsza niż \(\displaystyle{ \sqrt{2}}\). Dla czterech punktów pokazujemy, że teza nie zachodzi umieszczając je w wierzchołkach