Drzeworzędy

Przywiązałem się do drzew, więc jeszcze przez chwilę na ten temat.
Drzewo jakie jest, każdy widzi. Przynajmniej trzy drzewa na jednej prostej to rząd. A drzeworząd? To dziwne określenie wiąże się z zadaniem, z którym nie mogę się rozstać od dwóch wpisów. Drzeworząd to drzewo-w-rzędzie, ale – drzewo na przecięciu dwóch rzędów, to dwa drzeworzędy, na przecięciu trzech – trzy itd. Jeśli więc posadzimy np. 8 drzew w 6 rzędach – tak, jak poniżej – i obok każdego wpiszemy liczbę równą liczbie rzędów, w których dane drzewo się znajduje,

to suma wszystkich liczb będzie równa liczbie drzeworzędów danego układu, czyli w tym przypadku 19.

W tzw. problemie sadzenia drzew, „wyrosłym” na pograniczu geometrii dyskretnej i kombinatorycznej, chodzi o posadzenie n drzew w jak największej liczbie rzędów r po k drzewa w każdym rzędzie. Poniżej rozwiązania dla k = 3 i n = 6, 7, 8, 9 i 10.

Liczba drzeworzędów d w każdym z tych rozwiązań równa jest k*r.
Czy jeśli pominiemy k i zapytamy o maksymalną wartość d dla danego n, to wynik będzie zawsze taki sam, jak w problemie sadzenia drzew? Z zadania goszczącego w dwóch poprzednich wpisach wynika, że nie, bowiem dla n = 8 wartość d może być o jeden większa, niż to wynika ze wzoru k*r, a więc równa 22 – w jednym rzędzie mogą znaleźć się 4 drzewa:

Jest to najmniejsza wartość d większa od tej, która wynika z problemu sadzenia drzew – czyli dla danego n, ale z pominięciem warunku, że liczba drzew k w każdym rzędzie powinna być jednakowa. Co ciekawe, jest to, jak dotąd, jedyny znany mi taki przypadek. Inaczej mówiąc, nie udało mi się zwiększyć liczby drzeworzędów w rozwiązaniu problemu sadzenia drzew dla żadnej innej wartości n i k. Gdyby ktoś z Państwa bliżej zainteresował się tym zagadnieniem i przeskoczył o jedno oczko jakieś inne d (dla danego n) wynikające ze wzoru k*r, to wdzięczny będę za informację.

A dla wszystkich znacznie prostsze zadanie, będące jakby odwrotnością problemu sadzenia drzew.

Na planie sadu drzewa znajdują się tylko w 12 węzłach siatki kwadratowej 5×7. Proszę oznaczyć trzy węzły, w których należy posadzić jeszcze 3 drzewa tak, aby po tej czynności żadne 4 z 15 drzew nie rosły w jednym rzędzie. Należy jednak zrobić to tak, aby zachowany był następujący warunek: od każdego drzewa do każdego innego powinno być możliwe dojście po liniach siatki bez konieczności przechodzenia przez „bezdrzewny” węzeł. Inaczej mówiąc, układ drzew powinien być spójny.

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