Znany i lubiany węgierski matematyk Paul Erdős postawił kiedyś interesujący problem:
Na płaszczyźnie należy znaleźć pięć punktów spełniających następujące własności:
1. Odległość między dowolnymi dwoma punktami jest liczbą całkowitą
2. Żadne trzy punkty nie należą do jednej prostej
3. Żadne cztery punkty nie należą do jednego okręgu.
Zagadkę udało się rozwiązać praktycznie od razu: tak, oczywiście, da się. Oto przykładowe współrzędne tych punktów:
A: (16,33), B: (0,63), C: (32,63), D: (16,0), E: (72,33)
Jak widać, udało się nie tylko znaleźć takie punkty, które spełniają warunki zadania, ale bonusowo wszystkie współrzędne tych punktów są liczbami całkowitymi. Yay!
A co, jeżeli poprosimy o sześć takich punktów?
Tu już robi się nieco trudniej, ale również się da:
\( P1: (0,0), P2: (\frac{5}{6} \sqrt{3}, \frac{1}{2}), P3: (\frac{5}{6} \sqrt{3}, \frac{3}{2}), P4: (0, 1), P5: (\frac{\sqrt{3}}{6}, \frac{1}{2}), P6: (2 \frac{\sqrt{3}}{3},1)\)
Jak widać, bonusik w postaci całkowitych współrzędnych już nie obowiązuje. Ale nie szkodzi - zobaczmy, co będzie dalej.
Naturalnym odruchem jest zapytać o siedem takich punktów. Tu już sprawa robi się bardziej skomplikowana, ale nie niemożliwa. Po dość długim czasie paru jajogłowym udało się znaleźć co najmniej dwa takie zestawy siedmiu punktów. A także - uwaga - wracamy do liczb całkowitych!
(0,0) (327990000,0) (238776720,118951040) (222246024,-103907232) (243360000,21896875) (198368352,50379264) (176610000,-94192000)
(0,0) (374400,-2230800) (1081600,-1488240) (-453024,-1630200) (426725,-1630200) (569088,-1291680) (-439040,-1308720)
Takie całkowitolicznbowe zbiory punktów spełniających zagadkę Erdősa nazywane są "N-klastrami" (czyli 5-klaster, 6-klaster itd.)
No i teraz samo gęste: czy istnieją 8-klastry?
Jak na razie udało się tylko udowonić, że N jest ograniczone od góry. A więc, że istnieje takie N, dla którego istnieje N-klaster, ale nie istnieje P-klaster, dla dowolnego P>N. Jeżeli jednak chodzi o konkrety, zatrzymaliśmy się na etapie 7-klastrów.
Fascynujące.
a jak się te punkty znajduje? analitycznie czy komputer tego szuka?
Te małe, pięcioelementowe klastry, można znaleźć analitycznie (ale nie wiem dokładnie jak, próbowałem się wczytać w metody, ale poległem). 6- i 7-elementowe już tylko komputerowo. 8-elementowe wymagają szukania kombinacji wśród liczb sześcio- i więcej – cyfrowych i nawet algorytmy się krztuszą. Dopóki się nie wynajdzie lepszej metody, może być słabo z szukaniem…