Ziarnko do ziarnka

1 sierpnia 2009
Marek Penszko

W lipcowym numerze Świata Nauki sadziłem ziarenka – między innymi na grządce. To, że na grządce, a nie na grządkach, jest istotne, bo nasionka umieszczane były w rzędzie. Zmieńmy jednak przejściowo ogrodnika na matematyka i powiedzmy bez ogródka…, to znaczy bez ogródek:
oznaczałem na osi liczbowej punkty odpowiadające liczbom całkowitym nieujemnym.
Mówiąc ściślej, chodziło o to, aby punktów ulokować jak najwięcej na jak najkrótszym odcinku, zachowując następującą zasadę:
wszystkie odległości między punktami powinny być różne (a więc nie tylko między kolejnymi, ale między każdą parą punktów).
Korzystając z informacji o kilku ciekawych ciągach zaproponowałem prosty i (na pozór) skuteczny sposób radzenia sobie z zadaniem.

Zaczynamy od oznaczenia punktów 0 i 1, a następne wybieramy po kolei, przesuwając się zawsze o najkrótszy dystans dotąd nie wykorzystany. Po odległości równej 1 – między 0 a 1 – kolej na dystans 2, czyli punkt 3, co równocześnie załatwi odległość 3 między 0 a 3. Następnym najbliższym punktem będzie 7 – w ten sposób „obskoczy się” dystanse 4 (7–3), 6 (7–1) i 7 (7–0). Teraz pora na najkrótszą z opuszczonych odległości, czyli 5, a więc oznaczamy punkt 12 itd. W rezultacie oznaczane punkty utworzą tzw. ciąg B2: 0, 1, 3, 7, 12, 20, 30, 44, 65, 80, 96, 122, 147, 181, 203, 251, 289, 360, 400,…, który z reguły definiowany jest rekurencyjnie nieco inaczej, niż wynikałoby to z powyższego sposobu jego tworzenia (różne są sumy par liczb, uwzględniając także pary utworzone z wziętej dwukrotnie tej samej liczby).

Opisany sposób jest bardzo prosty i wydaje się skuteczny. A jednak… czy zawsze mając n ziarenek (wracamy do ogródka, pozostając oczywiście przy liczbach całkowitych) potrzebujemy grządki o długości równej wartości n-tego wyrazu ciągu B2 (zakładamy, że końce grządki należą do grządki)? Czy grządka nie może być krótsza?
Albo inaczej: czy dysponując grządką o długości d zawsze umieścimy na niej najwyżej tyle ziarenek, ile wyrazów w ciągu jest nie większych od tego o wartości równej d? Czy nie da się upchnąć ich więcej?

Nie zachęcam Państwa do zmagania się z tym problemem – że tak powiem – w całej rozciągłości, bo zagadnienie jest benedyktyńskie nawet dla komputera. Należy prawdopodobnie do tzw. problemów NP-trudnych i przed laty było analizowane w ramach projektu obliczeń rozproszonych.
Proponuję natomiast zmierzyć się z jednym konkretnym zadaniem.

 

Które cztery nasionka należy usunąć, aby wszystkie odległości między pozostawionymi były różne?