Raz-dwa

10 listopada 2013
Marek Penszko

Jeśli chodzi o stopień złożoności, zadania matematyczno-rozrywkowe można z grubsza podzielić, jak problemy obliczeniowe, na dwa rodzaje: jedne rozwiązuje się głową, drugie komputerem (pomijam to, że głowa potrzebna jest do napisania programu). Podział jest nieostry, bo – przynajmniej teoretycznie – z wieloma zadaniami można uporać się i tak, i tak. Wszystko zależy od tego, czy komuś starczy chęci, cierpliwości i ambicji, aby pokonać przeszkodę „na piechotę”, czy też dojdzie do wniosku, że gra jest niewarta świeczki i lepiej zatrudnić sztuczny mózg. Są też oczywiście takie zadania, o których z góry można powiedzieć, że komputer ich nie ruszy, a człowiek da sobie radę albo takie, o których od razu wiadomo, że zabierać się do nich nie ma sensu bez komputerowego wsparcia. Te drugie pojawiają się na stronach z wyzwaniami dla programistów – najciekawszą jest zapewne Project Euler.

Tak sobie mędrkuję w związku z dwoma zadaniami.
Jednym jest to zamieszczone w poprzednim wpisie – ni takie, ni siakie, bo z jednej strony szukanie maksa na piechotę wydaje się ciekawe, ale nie ma pewności, że cel się osiągnie, więc kuszące jest napisanie programu; z drugiej strony, gdyby maks był podany, to do odpowiadającego mu rozmieszczenia cyfr w diagramie nie tak trudno byłoby dotrzeć – praktycznie wystarczy pół godziny dłubaniny.
Drugie zadanie, które pochopnie zamieściłem w październikowym Świecie Nauki, jest – wbrew pozorom – nie do ruszenia na piechotę. Nawet napisanie programu nie wydaje się proste, ale tu mogę się mylić, bo nie jestem mocny w te klocki. Przedstawię w skrócie w czym rzecz.

Oto rzadka linijka optymalna „raz-dwa” k|d dla k=1 i d=8:

k=1 ponieważ jest na niej tylko jedna kreska (dlatego też jest rzadka); d=8 ponieważ można nią odmierzyć każdą całkowitą liczbę centymetrów od 1 do 8 cm (zakładając, że 1 cm stanowi na niej jednostkę, czyli cała ma długość 4 cm), przykładając linijkę w czasie pomiaru jedno– lub dwukrotnie (dlatego jest „raz-dwa„). Na przykład:
2 cm – przykładamy dwukrotnie odcinek 0_1;
3 cm – przykładamy 1_4;
7 cm – 0_4 i 1_4.

Linijka jest optymalna, ponieważ z jednej strony 8 jest największym d, gdy kreska jest tylko jedna, a z drugiej dla d=8 kresek nie może być mniej.

Wspomniane zadanie w Świecie nauki polegało na skonstruowaniu rzadkiej linijki minimalnej „raz-dwa” 4|d – takiej, aby d było jak największe. Inaczej mówiąc, na linijce powinny znaleźć się cztery kreski podziałki umieszczone w takich miejscach, aby można nią było odmierzyć każdą całkowitą liczbę centymetrów od 1 do maksymalnego d, przykładając linijkę raz lub dwa razy.
Bardziej abstrakcyjnie zadanie można sformułować tak:
Wybieramy pięć liczb całkowitych dodatnich i uzupełniamy ten zbiór dziesięcioma liczbami – dodatnimi różnicami między każdą parą wybranych liczb. W ten sposób tworzymy zbiór A złożony z piętnastu liczb. Jakie pięć liczb należałoby wybrać na początku, aby dodając parami liczby ze zbioru A (w grę wchodzą także dwukrotności każdej z nich), można było utworzyć każdą liczbę całkowitą od 1 do największego możliwego d.

Osobom, które, jak ja, nie są mocne w programowaniu, proponuję utworzyć na piechotę linijkę „raz-dwa” o dwa oczka mniejszą, czyli 2|d z największym d. Nawet wówczas zadanie nie jest proste.