Winogrona

7 sierpnia 2009
Marek Penszko

Wyobrażam sobie, że Ci z Państwa, którzy nadsyłają rozwiązania zadań, stanowią grupę nieoficjalnych przedstawicieli licznego grona rozwiązujących, oddelegowaną do ożywiania Łamibloga, czyli ku pokrzepieniu serca autora. Wielkie dzięki dla wszystkich „chwalących się” rozwiązaniami. Cieszą także dołączane do rozwiązań komentarze – wszystkie, ale zwłaszcza te skłaniające do refleksji lub do rozwinięcia tematu.
Michał napisał, że zadanie z poprzedniego wpisu nie podobało się, bo mało w nim do myślenia, głównie „guess-and-check”. Polemizowałbym, że jednak nie tak mało, a nawet przynajmniej pół na pół, jeśli nie zabierać się zbyt szybko za próbowanie i błądzenie, które wcześniej można elegancko ograniczyć i zaplanować. Wystarczy zauważyć, że do wpisania zostało sześć liczb nieparzystych (N) i sześć parzystych (P), a to pozwala ustalić tylko trzy możliwe schematy rozmieszczenia liczb:

W pierwszym i drugim trzeci rząd jest taki sam, więc oba można sprawdzać w tym samym „podejściu” i dość szybko wyeliminować. Pozostaje krótkie błądzenie w trzecim schemacie; warto przy tym pamiętać, że liczba 15 musi znaleźć się w podstawie trójkąta.
Rozwiązanie jest jedno, a zatem w trójkącie różnicowym piątego rzędu (5-liczbowy bok), czyli utworzonym z liczb od 1 do n = 15, rozmieszczenie liczb jest unikatowe (z dokładnością do symetrii). Dla żadnego n > 15 takiego trójkąta nie sposób utworzyć, choć niełatwo tego dowieść. Dla n = 21 można to zrobić w „toporny” sposób, rozpisując wszystkie ogólne schematy N-P (analogiczne jak każdy  z trzech powyżej); potem wystarczy zauważyć, że żaden z nich nie składa się z jedenastu N i dziesięciu P.
Jest jednak znany bardziej ogólny i elegancki dowód niemożności utworzenia trójkątów różnicowych rzędu 2^k – 2 (k > 1). Polega on na wykazaniu, że suma liczb w takim trójkącie powinna być parzysta, co prowadzi do sprzeczności, bo dla rzędów określonych podanym wzorem wartości n są nieparzyste (3, 21, 105, 465, 1953, 8001…), a więc suma liczb od 1 do n także musi być nieparzysta. Istnieje wreszcie bardzo pomysłowy, ale trudny dowód, że trójkąty różnicowe rzędu nie mniejszego niż 9 w ogóle nie mogą istnieć. Dla rzędów 6, 7 i 8 ten dowód się nie sprawdza, ale trzy krnąbrne przypadki nietrudno wykluczyć, pisząc odpowiedni program na komputer (nie wspominając o podanych wyżej sposobach dla szóstego rzędu).

Jeżeli z liczb od 1 do 21 usunąć jakąś nieparzystą (ale nie dowolną), zastępując ją kolejną liczbą, czyli 22, to wówczas utworzenie trójkąta różnicowego będzie możliwe, jednak to łamigłówka iście benedyktyńska, niemal wyłącznie guess-and-check. Zdziwiłem się, znajdując takie zadanie (z usuniętą piętnastką) w szkolnym konkursie. Jeśli ktoś zna metodę rozgryzienia tego orzecha na logikę, wdzięczny będę za informację.

Łamigłówki bliskie trójkątom różnicowym, ale zwłaszcza trójkątowi Pascala, były przed laty w modzie. Pojawiły się między innymi jako Winogrona na Łamigłówkowych Mistrzostwach Świata w Brnie w 2001 roku. Zapraszam do posmakowania lekkostrawnych „owoców” z Mistrzostw, lecz w formie indugadki, czyli reguły zabawy należy samemu wyindukować na podstawie przykładu  z rozwiązaniem.

Nietrudno zauważyć, co wspólnego mają Winogrona z trójkątem różnicowym. Wystarczy obrócić kiść z przykładowym rozwiązaniem o 60 stopni zgodnie z ruchem wskazówek zegara.