Pięć drzew

Ułożyć zadanie i nie potrafić go rozwiązać. Tak czasem bywa, ale częściej zdarza mi się znajdywać rozwiązanie, które – jak się później okazuje – albo nie jest najlepsze, albo nie jedyne. Co ciekawe, konsultanci też czasem zawodzą i dopiero niektórzy czytelnicy wyłapują potknięcia. Ostatnio taki przypadek miał miejsce w marcowym Świecie Nauki.

Artykuł nawiązywał do tzw. problemu sadzenia drzew, który w ogólnym ujęciu polega na posadzeniu n drzew w r rzędach tak, aby w każdym rzędzie rosło dokładnie k drzew. Bardziej konkretnie, chodzi o znalezienie maksymalnego r dla ustalonych n i k. Na przykład, jeśli n = 8 i k = 3, to rzędów r może być najwyżej 7, a drzewa należy posadzić tak:

Jedno z zadań konkursowych było nieco zakręcone, bo drzewa znajdowały się w węzłach siatki kwadratowej, a ponadto występowały dwie wartości r i k.

W sadzie rośnie 169 drzew. Na rysunku odpowiadają im węzły siatki kwadratowej. Osiem drzew przeznaczono do wykarczowania – trzy z nich (oznaczone na rysunku) znajdują się w rogach sadu, czyli w punktach a1, a13 i m1. Gdzie rośnie pięć pozostałych, jeśli wszystkie osiem tworzy siedem rzędów: sześć rzędów po trzy drzewa w każdym (nie więcej) oraz jeden rząd z czterema drzewami?

Na zmaganie się z tym zadaniem, podobnie jak na cały problem sadzenia drzew, nie ma uniwersalnej metody. Trzeba próbować i kombinować, co też czyniłem i znalazłem następujące rozwiązanie: pięć drzew tkwi w punktach a7, d4, e1, e5, g1. Graficznie, z zaznaczonymi siedmioma rzędami, wygląda to tak:

Co ciekawe, konsultant też wpadł na takie rozwiązanie, a na żadne inne nie, co utwierdziło mnie w podejrzeniu, że innego nie ma. Jakież więc było moje zdziwienie, gdy okazało się, że żadna z blisko setki osób, uczestniczących w konkursie, nie nadesłała takiego rozwiązania.

Ile różnych rozwiązań ma to zadanie – nie wiem, a ile różnych nadesłali czytelnicy – na razie nie ujawnię. Być może niektórzy z Państwa spróbują znaleźć i nadesłać choć jedno – oczywiście inne niż podane wyżej – i może będzie wśród nich takie, którego nie znam. Wszystkie staro- i nowoodkryte podam za kilka dni, o ile ktoś z Państwa wcześniej do cna nie rozgryzie tego zadania.

Komentarze z prawidłowymi rozwiązaniami uwalniane są wieczorem w przeddzień kolejnego wpisu. Wpisy pojawiają się co kilka dni.