Odwieczny problem ważenia kul

Ważenie kul stało się współcześnie synonimem inteligencji i posiadania wysokich kwalifikacji zawodowych. Zadania o tej treści pojawiają się na testach dla kandydatów do pracy zarówno w wielkich korporacjach, jak i w firmach "Krzak". Studenci bywają molestowani kulami na egzaminach ustnych oraz w uczelnianych kawiarenkach. Pojawiające się właśnie masowo jak grzyby po deszczu Sztuczne Inteligencje raczą nas sprytnymi rozwiązaniami tego problemu, za które dałyby sobie obciąć rękę. I.... pewnie teraz chodziłyby już bez co najmniej jednej ręki.

Do napisania tego artykułu skłoniła mnie seria rozmów z ChatGPT-3, któremu poleciłem właśnie rozwiązanie problemu ważenia n kul, wśród których jest jedna lub dwie inne, w celu oszacowania zdolności logicznego myślenia Maszyny. Te maszynowe rozwiązania zawierały tak gigantyczny ładunek głupoty oraz bezmyślności, że aż mi wstyd się zrobiło. Zawstydziłem się z powodu mojego zauroczenia ową AI odpowiadającą na wszystkie pytania, bo w tym momencie jasnym dla mnie się stało, że większość z odpowiedzi może być stekiem bzdur skleconych na kolanie z kawałków śmieci przypominających poważne treści. Jasne również stało się to, że nie powinno się jeszcze wypuszczać AI na spacer po sieci bez solidnej bazy wiedzy w plecaku. Almanachu, w którym znajdą się użyteczne wskazówki co do sposobów rozwiązywania przynajmniej takich medialnych problemów "matematycznych" lub "logicznych" pokroju "cegła waży kilogram i połowę cegły", a także literalny zakaz otwierania buzi, gdy się na dany temat nie ma kompletnie nic do powiedzenia.

Ponieważ pani Edeldreda z Elly zaczęłą już podejrzewać moją skromną osobę o dawanie lekcji Sztucznej Inteligencji i uczenie jej matematyki, więc świadom skutków takiego skojarzenia, w obliczu faktów zmuszony zostałem do przeciwdziałania złośliwej plotce i przedstawienia jakichś dowodów na moją niewinność. Postanowiłem sam rozwiązać to arcyciekawe zadanie, nie czekając na to, aż Elon Musk dosypie do projektu jeszcze więcej kasy, by e-Wuch zaczął w końcu mówić trochę bardziej z sensem ;)

Kiedyś przedstawiłem taką oto małą listę problemów ważenia kul:

1. Problem ważenia n kul, ale 2 są cięższe i równe sobie wagą.
2. Problem ważenia n kul, ale 2 są cięższe i różnią się wagą.
3. Problem ważenia n kul, ale 2 są inne, jedna lżejsza, zaś druga cięższa i suma ich wag daje wagę dwóch zwykłych kul.
4. Problem ważenia n kul, ale 2 są inne, jedna lżejsza, zaś druga cięższa i suma ich wag nie daje wagi dwóch zwykłych kul.
5. Problem ważenia n kul, wśród których jest m cięższych, ale równych wagą między sobą.
6. Uogólnienie 5 na przypadki jak w 1,2,3,4 i ich wariacje. Wreszcie problem ważenia n kul, wśród których jest m innych, ale nie wiemy jakich.
7. Uogólnienie 1: Problem ważenia n kul, wśród których jest a1,a2,...,ak kul o wagach u1,u2,...,uk i ciągi {ai}, {ui} spełniają pewne reguły. Przykładowa reguła ai=aj, ui+1=2ui.

Dziś zajmę się tylko problemem pierwszym i napomknę o trzecim. Wprowadzę pewne oznaczenia, pokażę gdzie kryją się rekurencje i jak ze sobą korespondują, co może przyczyni się w przyszłości do napisania jakiegoś fragmentu kodu (snippet) w JavaScripcie lub Pythonie i będzie wtedy bardziej poglądowo.

Problem ważenia n kul z jedną kulą wyróżnioną

Rozwiązanie problemu ważenia n kul, wśród których jest jedna kula cięższa, polega nie tylko na tym, że podaje się pewną funkcję W(n) zwracającą dla każdej liczby naturalnej n liczbę koniecznych do wykonania ważeń przy użyciu wagi z szalkami, lecz także na opisaniu sposobu ważenia, czyli całego algorytmu, zgodnie z którym należy postępować. Nie zdołała tego do końca pojąć AI i na zadane pytanie potrafiła jedynie rzucić jakimś wzorem postaci floor(log2(n))+1 Funkcja "floor(x)" (podłoga) przypisuje dla x największą liczbę całkowitą c mniejszą bądź równą x. Rzecz jasna ten wzór jest do... czyli do niczego, jak zwykł mawiać niezapomniany Jan Kobuszewski w roli Majstra.

Postaram się w skrócie wyjaśnić dlaczego ten wzór jest zły. Otóż skupia się on na liczbach, które mają związek z potęgami dwójki. Tymczasem liczby, o które chodzi wiążą się z potęgami trójki. Różnica. Te dwójki AI wzięła prawdopodobnie z innego oszacowania dla jakiegoś przeszukiwania binarnego, ale tu wyraźnie widać, że zupełnie nie pasują.

Wyobraźmy sobie nasze zagadnienie w formie wiersza n jedynek 11...1. Chodzi o to, że nie ma znaczenia jak będziemy wybierać kule do ważeń, bo wszystkie wyglądają jednakowo. Żeby wizualizować ważenie można taki wiersz podzielić znakami "|" na trzy sekcje 1...1|1...1|1...1. To tylko wyobrażenie jakby ktoś miał problemy z czystą abstrakcją, do której teraz zmierzam. Możemy zatem robić to tak: bierzemy pierwszych 2k jedynek/kul (do ważenia k i drugie k), a pozostałe n-2k zostają "na stole". Rozbijamy liczbę n na trzy składowe k+k+(n-2k). Czyli interesuje nas na wstępie każdy rozkład liczby naturalnej n w postaci n=2k+r. Odpowiada to rozbiciu zbioru kul na podzbiory K+K'+R. Mogą być dwa przypadki: a) cięższa kula jest w K lub K' (przypadek symetryczny), albo b) cięższa jest w R. Dlaczego nie będzie to pełna rekurencja?

Możemy problem ważenia n kul oznaczyć następująco W(n), czyli kładziemy K i K' na szalkach wagi, a na stole R. Mamy dwa wyniki ważenia: a) jedna z szalek wagi opadnie, b) waga będzie jednakowa. Właśnie ten drugi przypadek wyklucza czystą rekurencję postaci powiedzmy W(n)=W(2k)+W(n-2k) (uwaga, wzór wzięty z sufitu!) jakby sugerowała rozmowa z AI powyżej. Jeśli bowiem wykonamy pierwsze ważenie, to już wiemy w którym ze zbiorów K,K',R znajduje się cięższa kula, a więc liczba ważeń będzie równa 1+W(X), gdzie X jest równe pewnemu elementowi {K,K',R}. Musimy wybrać największe 1+W(X). Tu zastosowałem ciche utożsamienie zbioru kul z jego mocą, ale chyba będzie to zrozumiałe. Oczywiście z W(X) postępujemy analogicznie, bo jest po podproblem ważenia kul. Liczba ważeń jest wtedy równa [n,W(n)]=[1,0], [2,1],[3,1], [4,2],[5,2],...,[9,2], [10,3],.... Widać, że liczba skacze o 1 dla n=2,4,10,....

Zbadajmy podziały n=2k+r, które z takich podziałów są najlepsze, czyli prowadzą do najmniejszej liczby koniecznych ważeń. Okazuje się, że dla dużych liczb kul skrajne podziały, gdzie k jest duże i r małe, albo odwrotnie, są złe. Liczy się tylko środek, czyli rozkład w pewien sposób zbalansowany. Może być rzecz jasna więcej niż jeden rozkład dający właściwą odpowiedź. W samym "środku" będą to liczby możliwie bliskie wartości n/3.

Zmiany liczby koniecznych ważeń następują dla n będących potęgą liczby 3 zwiększoną o 1. To właśnie daje ów tajemniczy ciąg 2,4,10,... czyli 1+1,3+1,9+1,.... Można podać dowód indukcyjny tego zdania. Niech n=3^k i W(n) oznacza liczbę koniecznych ważeń:

1. Przypadki szczególne: Zdanie jest prawdziwe dla k=0, bowiem jednej kuli nie musimy ważyć, czyli W(1)=0, zaś z dwóch kul wybierzemy cięższą po jednym ważeniu, W(2)=1.
2. Założenie indukcyjne: Załóżmy, że zdanie jest już prawdziwe dla wszystkich liczb s ≤ k. Oczywiście będziemy mieli W(3^k)=k, bowiem W(3^k)=1+W(3^{k-1}), czyli z każdą zabraną potęgą dostajemy jedno ważenie. Pokażemy, że jest to prawdą także dla k+1.
3. Teza i jej dowód: Musimy udowodnić, że W(3^{k+1}) < W(3^{k+1}+1) lub dokładniej W(3^{k+1})+1 = W(3^{k+1}+1):

• Zbiór n=3^{k+1}+1 kul podzielimy na trzy podzbiory. Dwa o liczności 3^k i jeden zawierający 3^k+1 kul. Na szalkach wagi kładziemy dwa pierwsze podzbiory.
• Jeśli waga wychyli się, to mamy zagadnienie W(3^k), którego rozwiązanie znamy i wiemy, że W(3^k) < W(3^k+1). Nie jest to jednak rozwiązanie problemu, bo zbiór trzeci jest większy o jedną kulę.
• Jeśli waga pozostanie w równowadze, to kula cięższa była na stole. Wtedy W(3^{k+1}+1) = 1+W(3^k+1). Ale W(3^k) < W(3^k+1), więc W(3^{k+1})=1+W(3^k) < W(3^{k+1}+1).
• Cnd.

Wniosek 1: Jeśli 3^{k-1} < n ≤ 3^k, to W(n)=k dla k>0.

Wniosek 2: Można to zapisać wzorem: W(n)=ceil(log3(n)).

Funkcja "ceil(x)" (sufit) przyporządkowuje dla x najmniejszą liczbę całkowitą c większą lub równą od x Nie wiem. Może tylko ja odnoszę takie wrażenie, że "kot jaki jest każdy widzi", lecz jeśli ktoś jeszcze ma problemy ze zrozumieniem powyższego rozumowania, to zapraszam do dyskusji pod artykułem.

Ważenie n kul z dwiema kulami wyróżnionymi

Problemy z dwiema innymi kulami są dużo dużo bardziej złożone niż problem z jedną kulą. W tym przypadku możemy jakoś sprowadzić zadanie do dwóch problemów z jedną kulą, ale nie jest to główną zasadą. Dochodzenie do problemów z jedną kulą wydaje się bardzo chaotyczne. Na początek zajmiemy się dwiema kulami jednakowej wagi, cięższymi lub lżejszymi od reszty.

Oznaczmy dla porządku problem ważenia n kul, wśród których są dwie cięższe i równej wagi, symbolem W(n,k,0), k < n. Zero po prostu oznaczać tu będzie taką pomocniczą etykietkę, że kule są równej wagi i są cięższe, abyśmy się nie pogubili w tych problemach. Inne warunki będę oznaczać innymi liczbami w zależności od zapotrzebowania.

Oczywiście W(2,2,0)=0, bo nic nie musimy ważyć (mamy te kule w ręce), oraz W(3,2,0)=1, bo po pierwszym ważeniu wiemy wszystko: 1) jeśli waga jest w równowadze, to na niej leżą obie kule cięższe, zaś jeśli nie, to 2) jedna kula cięższa jest na wadze, a druga na stole.

Oczywiście to samo mamy dla problemu dwóch kul lżejszych i równej wagi W(n,2,1) (1 mówi o tym, że wyróżnione kule są lżejsze i równej wagi). Zauważmy, że ten drugi przypadek wskazuje, iż przy dwóch wyróżnionych kulach równej wagi, lecz nie wiadomo czy cięższych czy lżejszych od reszty (etykietka 3), W(n,k,3) będzie przynajmniej o 1 większa. Będziemy tu musieli określić już w przypadku W(3,2,3) i przy wadze wychylonej w jedną stronę, czy kula leżąca na stole różni się wagą od którejś z kul na wadze. Wiemy już, że jest inna, więc ważąc ją powiedzmy z kulą cięższą dostaniemy dwie informacje: a) jeśli waga będzie w równowadze, to są to dwie kule cięższe; b) jeśli waga jest różna, to z pozostałą kulą znaleźliśmy dwie kule lżejsze. To daje w sumie dwa ważenia. Koniec dygresji.

Problem W(4,2,0) już nie jest taki prosty. Jeśli umieścimy na wadze po dwie kule i waga nie będzie w równowadze, to znaczy, że mamy obie kule cięższe na jednej szalce (jedno ważenie). Jeśli waga będzie w równowadze, to mamy po jednej kuli cięższej na każdej szalce wagi. Musimy więc wykonać dwa kolejne ważenia, żeby z obu par wybrać kule cięższe. Daje to razem trzy ważenia i to byłoby rozwiązanie problemu dla n=4, gdyby nie sposób ważenia opisany poniżej.

Drugi sposób ważenia zakłada podział kul na trzy zbiory, po jednej kuli na szalkach wagi i dwie na stole. Wtedy równa waga oznacza, że albo dwie kule cięższe (i równej wagi) są na szalkach, albo na stole. Wystarczy zważyć jedną kulę z szalki z jedną ze stołu żeby się przekonać które są które. Jeśli waga nie jest w równowadze, to znaczy, że znamy już jedną z cięższych kul, zaś druga leży na stole z normalną. Drugie ważenie kul ze stołu wskaże nam tę drugą cięższą. Czyli potrzebowaliśmy tylko dwóch ważeń.

Ostatecznie W(4,2,0)=2.

Uwaga: Obliczenie W(4,2,3) to przypadek szczególny. Czyli gdy nie wiemy czym dwie wyróżnione kule różnią się od zwykłych, ważenie nie da nam odpowiedzi na to pytanie. Wiadomo, że po dwóch ważeniach będziemy je mieli, tylko nie ma żadnej informacji która to będzie para.

Problem W(5,2,0) możemy rozwiązać tak. Ważymy po dwie kule i jeśli waga ich jest równa, to mamy po jednej kuli cięższej na każdej szali. Wtedy trzeba wykonać dodatkowe jedno ważenie dla każdej szali, czyli razem 3. Jeśli w pierwszym ważeniu waga się wychyli, to są dwa przypadki: a) obie kule cięższe są na tej szali, b) na szali jest jedna kula cięższa, a druga na stole. Jeśli zważymy teraz dwie kule z cięższej szali, to otrzymamy odpowiedź. Moglibyśmy także dokonać ważenia kuli ze stołu oraz jednej dowolnej kuli z wagi. Dlaczego?

Zatem mamy W(5,2,0)=3.

To co policzyliśmy do tej pory sugeruje, że wzór mógłby być następujący W(n,2,0)=n-2. Trzeba to tylko jakoś udowodnić. Jednakże już teraz mogę powiedzieć, że to tylko złudzenie. Widać też, że liczby otrzymywane w zadaniu ważenia W(n,1,0) nic nie mówią o liczbach w zadaniu W(n,2,0). Czyli nie będzie to jakieś proste "plus jedno/dwa dodatkowe ważenia".

Dla W(6,2,0) na wagę kładziemy po 2 kule i 2 zostają na stole. Wtedy dla wagi w równowadze 1) kule cięższe są na obu szalach, albo 2) obie na stole. Dla wagi wychylonej 3) obie kule wyróżnione są na cięższej szali, albo 4) jest tam tylko jedna kula cięższa, zaś druga na stole. Każdy z punktów 2,3,4 daje nam tyle informacji, że wystarczyłoby tylko jedno dodatkowe ważenie, czyli jeśli jakaś Wyrocznia powiedziałaby nam, że zachodzi powiedzmy przypadek 3, to wiemy jak postępować dalej. Jednak bez pomocy Wyroczni rozróżnienie przypadków 3 i 4 wymaga dwóch dodatkowych ważeń. Bierzemy np. do ważenia jedną kulę z cięższej szali i jedną ze stołu. Gdy ich waga jest jednakowa, to możemy zważyć jedną z nich z jedną kulą z lżejszej szalki i wszystko będzie wiadomo. Gdyby zaś któraś z kul okazała się cięższa, to bierzemy do ważenia ich partnerki. Tą drogą otrzymamy summa summarum 3 ważenia. Przypadki 1 i 2 można odróżnić podobną metodą. Najpierw zważymy parę kul z szalki, obojętne z której. Gdy ich waga będzie równa, to oczywiście obie cięższe kule są na stole. Jeśli nie, to podobnie ważymy kule z drugiej szalki. Tu mamy znów 2 lub 3 ważenia.

Stąd W(6,2,0)=3 i skończyło się rumakowanie. Oszacowanie n-2 okazuje się być błędne. Mógłbym tu prowadzić dalsze rozważania jak policzyć W(n,2,0) dla k=7,8,9,... lecz w końcu zabrakło by tu miejsca albo cierpliwości u szanownego Czytelnika. Dlatego podam teraz sam algorytm bez dalszych wyjaśnień co do postaci wzoru końcowego.

Dalsze obliczenia W(n,2,0)

Dla dowolnego n>1. Dzielimy kule tak n=k+k+(n-2k) i dwie pierwsze grupy idą na wagę. Przypadek równej wagi: 1) po jednej kuli cięższej na szalkę, 2) obie są na stole. Przypadek różnej wagi: 3) obie są na cięższej szalce, 4) jedna jest na szalce i druga na stole. Dalsze rozumowanie zasadza się na założeniu, że podzieliliśmy kule na grupy w miarę równomiernie, powiedzmy tak:

Jeśli n=3k, to dzielimy kule równo na trzy podzbiory

• 1,2: Ważę kule ze stołu i kule z dowolnej szalki. Waga nie może być w równowadze. Gdy stół jest cięższy, to mamy W(3k,2,0)=2+W(k,2,0); w p.p. W(3k,2,0)=2+2W(k,1,0) (osobno dla każdej szalki).
• 3,4: Ważę kule ze stołu i kule z lżejszej szalki. Jeśli waga jest równa, to mamy W(3k,2,0)=2+W(k,2,0); w p.p. W(3k,2,0)=2+2W(k,1,0) (dla stołu i dla szalki cięższej w pierwszym ważeniu).

Jeśli n=3k+1, to stosujemy podział k+k+(k+1)

• 1,2: Ważę k kul ze stołu (bez jednej) i kule z dowolnej szalki. Waga nie może być w równowadze. Gdy stół jest cięższy, to mamy W(3k+1,2,0)=2+W(k+1,2,0); w p.p. W(3k+1,2,0)=2+2W(k,1,0) (osobno dla każdej szalki).
• 3,4: Ważę k kul ze stołu (bez jednej) i kule z lżejszej szalki. Jeśli waga jest równa, to mamy W(3k+1,2,0)=2+W(k+1,2,0) (dołączamy pozostałą kulę ze stołu do cięższej szalki); w p.p. W(3k+1,2,0)=2+2W(k,1,0) (dla stołu bez kuli i dla szalki cięższej w pierwszym ważeniu).

Jeśli n=3k+2, to stosujemy podział (k+1)+(k+1)+k

• 1,2: Ważę k kul (bez jednej) z dowolnej szalki z kulami ze stołu. Waga może być w równowadze, gdy odłożyliśmy kulę cięższą z szalki! Jeśli stół jest cięższy, to mamy W(3k+2,2,0)=2+W(k,2,0). W p.p. wiemy, że na wadze są tylko normalne kule, odłożona jest cięższa i W(3k+2,2,0)=2+W(k+1,1,0) (druga szalka z pierwszego ważenia).
• 3,4: Ważę k kul ze stołu i kule z lżejszej szalki (bez jednej, normalnej). Jeśli waga jest równa, to mamy W(3k+2,2,0)=2+W(k+1,2,0) (dla cięższej szalki); w p.p. W(3k+2,2,0)=2+W(k,1,0)+W(k+1,1,0) (dla stołu i dla szalki cięższej w pierwszym ważeniu).

Liczby tego ciągu rosną szybciej niż liczby dla problemu z jedną kulą, więc szacunkowy wzór może mieć postać W(3k+e,2,0)=2+W(k,2,0), gdzie e=0,1,2. Oczywiście może się zdarzyć, że ktoś w jakimś przypadku znajdzie lepszą metodę ważenia i zmniejszy te oszacowania, na przykład gdzieś 2W(k,1,0) przekroczy W(k+1,2,0),  ale na razie wydaje się to mało prawdopodobne. Intensywne prace trwają ;)

Inne problemy

Jak widać do rozwiązania problemu ważenia kul kluczowe jest właściwe rozpoznanie wszystkich możliwych przypadków i wyciągnięcie z nich maksimum informacji o kulach. Problem ważenia n kul, wśród których są dwie inne o wagach odpowiednio w±e jest jeszcze bardziej skomplikowany, żeby nie rzec bazylny. Jedną z szykan jest tu przypadek dwóch wyróżnionych kul w jednym podzbiorze, czyli w którymś momencie mogą znaleźć się na jednej szali wagi, lecz ich zachowanie przypominać wtedy będzie dwie normalne kule. Albo będziemy mieli szczęście i odkryjemy jedną z nich, albo do samego końca będziemy podejrzewać każdą niezważoną jeszcze parę kul o niecnotę.

Problem z dwiema innymi kulami, których wagi nie sumują się do wagi dwóch normalnych kul, wydaje się być trochę łatwiejszy.

Problem ważenia n>3 kul z trzema lub więcej kulami wyróżnionymi siłą rzeczy musi być trudniejszy od poprzednich. Jednak przy założeniu, że kule wyróżnione są jednakowe, pewnie dałoby się znaleźć jakiś zadowalający wzór na liczbę koniecznych ważeń. Jak to często bywa na polskich uczelniach, w tym momencie pan profesor kończąc wykład powiedziałby, że dalsze obliczenia pozostawia studentom jako zadanie domowe, lecz ja nie będę aż tak okrutny :).

Nadal uważam, że rozwiązanie tego problemu jest doskonałym wyznacznikiem siły rozumowania Sztucznej Inteligencji. Jeśli kiedykolwiek powstanie AI zdolna przerosnąć Człowieka, to właśnie pojawiające się znikąd w infosferze rozwiązania takich "głupich" problemów będą sygnałem, że coś się anomalnego dzieje. Chwilowo możemy jeszcze spać spokojnie, bo to co jest nazywane AI sadzi babola za babolem, a nie podaje użyteczne rozwiązania.