Sekrety OLG

4 grudnia 2009
Marek Penszko

Od ponad roku trwają poszukiwania optymalnej linijki Golomba (OLG) 26. rzędu. Uczestniczą w nich tysiące internautów, ofiarnie zatrudniających swoje komputery w ramach tzw. projektu obliczeń rozproszonych. Czego szukają? Czegoś mniej więcej takiego, tylko znacznie dłuższego:

To jest OLG szóstego rzędu. Szóstego – ponieważ jest na niej 6 kresek podziałki. Golomba – ponieważ odległość między każdą parą kresek (nie tylko kolejnych) jest inna. Optymalna – ponieważ najkrótsza danego rzędu. Nawiasem mówiąc, znane są jeszcze cztery inne (niektóre kreski w innych miejscach) OLGi 6. rzędu, czyli o długości 17.

Przed rokiem „padła” linijka 25. rzędu – po 8 latach eksploracji. Jeśli komputery nie przyspieszą, to następnych rzędów nie doczekam. Proszę więc o zintensyfikowanie poszukiwań, abym mógł na łożu śmierci poznać tę z 28 kreskami, bo 28 to moja szczęśliwa liczba 🙂 . Pocieszające jest to, że znamy następną kandydatkę. Wygląda tak:

0_1_33_83_104_110_124_163_185_200_203_249_251_

_258_314_318_343_356_386_430_440_456_464_475_

487_492.

Trzeba tylko sprawdzić, czy jakaś krótsza niż sięgająca do 492 się przed nią nie ukrywa.

Po co te poszukiwania? To jest tak zwane dobre pytanie, po którym prosi się o następne. Z najkrótszych OLG można wprawdzie wycisnąć praktyczne zastosowania (urządzenia oparte na tzw. technologii układu sfazowanego, anteny przekaźnikowe, badania krystalograficzne), ale z dłuższych nie ma pożytku, a pogoń za ekstremalnymi, to – przynajmniej na razie – „czyste szaleństwo”. Można z nich natomiast spróbować wycisnąć zadania do główkowania. Spróbowałem w formie konkursu w listopadowym Świecie Nauki. Konkurs dobiegł końca, więc zadanie może trafić do Łamiblogu, gwoli kontroli i ku rozerwaniu tych z Państwa, którzy go z wersji papierowej nie znają.

Optymalną linijkę Golomba można zdefiniować jako ciąg skończony liczb całkowitych, spełniający podane wyżej warunki. Wszystkie takie ciągi, jeśli składają się z co najmniej pięciu wyrazów, czyli stanowią OLG-i rzędu większego niż 4 – są „wybrakowane” w tym sensie, że choć to linijki – do mierzenia się nie nadają. Po prostu nie ma na nich niektórych odległości, czemu zresztą trudno się dziwić, bo liczba wszystkich możliwych dystansów między kreskami jest zawsze mniejsza niż długość linijki Golomba.

Oto jedyna znana OLG 9. rzędu:

0_1_5_12_25_27_35_41_44.

Łatwo zauważyć, że brak na niej dystansów: 18, 21, 28, 31, 33, 37, 38, 42.
Zadanie polega na przekształceniu jej w narzędzie miernicze, czyli tak, aby występowała na nim między kreskami każda odległość mniejsza od długości linijki d. Przekształcenie powinno polegać wyłącznie na zmianach położenia niektórych kresek podziałki. Inaczej mówiąc, z ciągu należy usunąć n liczb, a następnie dodać n innych liczb tak, aby:
– zmian było jak najmniej, czyli n = min.;
– ciąg nadal składał się z 9 wyrazów – od a1 = 0 do a9 = d;
– wśród różnic między dwoma dowolnymi wyrazami ciągu nie brakowało żadnej mniejszej od d;
– ciąg był jak najdłuższy, czyli a9 = max.
Po utworzeniu miarki zniknie oczywiście optymalna linijka Golomba – zmieni się (zmniejszy) jej długość d, a niektóre odległości będą się powtarzać.