XXXVIII OM - III - Zadanie 6

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

III

Płaszczyznę pokryto siatką sześciokątów foremnych o boku 1. Za drogę na siatce uważamy taki ciąg boków sześciokątów siatki, że każde dwa kolejne mają wspólny koniec. Drogę na siatce nazwiemy najkrótszą, jeżeli jej końców nie można połączyć drogą krótszą. Znaleźć liczbę najkrótszych dróg na siatce o ustalonym początku i długości 60.

Rozwiązanie

Uwaga. Użyte w treści sformułowanie: ,,kolejne boki mają wspólny koniec'' należy rozumieć w ten sposób, że rozważa się odcinki skierowane i koniec poprzedniego jest początkiem następnego (tak więc nie tworzy drogi na przykład pęk odcinków o jednym wspólnym końcu). Mimo braku precyzji, tak właśnie było to sformułowanie rozumiane przez wszystkich rozwiązujących, zgodnie z intuicyjnym sensem słowa ,,droga''.

Ustalmy na płaszczyźnie jeden z kierunków boków rozważanej siatki sześciokątów ( $\Sigma_6$ ), nazwijmy go poziomym i wyróżnijmy na nim zwroty: lewo, prawo. Z każdego węzła siatki $\Sigma_6$ wybiega dokładnie jeden bok poziomy. Oznaczmy przez $W$ zbiór tych węzłów, z których bok poziomy wybiega w prawo, a przez $W'$ zbiór pozostałych węzłów, to jest tych, z których bok poziomy biegnie w lewo. Każdy bok siatki łączy punkt zbioru $W$ z punktem zbioru $W'$ .

Niech $O$ będzie wybranym ustalonym węzłem, punktem początkowym rozpatrywanych dróg. Możemy przyjąć, że $O\in W$ . Startując z punktu $O$ , po parzystej liczbie kroków znajdziemy się w punkcie zbioru $W$ , a po nieparzystej - w punkcie zbioru $W$ . Zatem dwie drogi o wspólnym początku i końcu mają długości jednakowej parzystości; jeśli droga daje się skrócić - to co najmniej o $2$ .

Dwa różne punkty zbioru $W$ nazwiemy sąsiednimi, jeśli łączy je droga długości $2$ ; droga ta jest wówczas jedyna. Połączmy każdą parę sąsiednich punktów zbioru $W$ odcinkiem. Powstanie w ten sposób siatka $\Sigma_3$ trójkątów foremnych o boku $\sqrt{3}$ ; węzłami siatki $\Sigma_3$ są punkty zbioru $W$ . Określamy pojęcie drogi na siatce $\Sigma_3$ , długości drogi oraz pojęcie drogi najkrótszej analogicznie do odpowiednich pojęć dla siatki $\Sigma_6$ , z tym, że za jednostkę długości przyjmujemy bok siatki $\Sigma_3$ .

W dalszym ciągu będziemy rozpatrywać na siatce $\Sigma_6$ tylko drogi długości parzystej, rozpoczynające się w punkcie $O$ i spełniające następujący warunek: jeśli $OP_1P_2 \ldots P_{2k-1}P_{2k}$ jest rozpatrywaną drogą, to $P_{2i-2} \neq P_{2i}$ dla $i = 1, \ldots, k$ (przyjmujemy $P_0 = O$ ); innymi słowy, żaden bok siatki nie jest przebiegany ,,tam i z powrotem,, w dwóch kolejnych krokach, z których pierwszy ma numer nieparzysty, a drugi parzysty (oczywiście każda najkrótsza droga ten warunek spełnia). Idąc taką drogą, w każdej kolejnej parze kroków przechodzi się z punktu zbioru $W$ do sąsiedniego punktu zbioru $W$ . Zatem każda droga na siatce $\Sigma_6$ spełniająca ten warunek i mająca długość $2k$ wyznacza drogę długości $k$ na siatce $\Sigma_3$ . Jest to odpowiedniość wzajemnie jednoznaczna, bo końce każdego boku siatki $\Sigma_3$ łączy dokładnie jedna droga długości $2$ na siatce $\Sigma_6$ . Drogom najkrótszym na jednej siatce odpowiadają drogi najkrótsze na drugiej siatce.

Spróbujemy policzyć najkrótsze drogi długości $k$ na siatce $\Sigma_3$ (o początku $O$ ).

Weźmy pod uwagę sześć dróg (na siatce $\Sigma_3$ ) długości $k$ wychodzących z $O$ i biegnących po półprostych. Ich końce są wierzchołkami sześciokąta foremnego, który oznaczymy przez $H_k$ . Wychodząc z punktu $O$ i wykonując $k$ ruchów (na siatce $\Sigma_3$ ) nie wyjdziemy z pasa ograniczonego prostymi zawierającymi dowolne dwa równoległe boki sześciokąta $H_k$ - a więc nie wyjdziemy poza obręb tego sześciokąta. Możemy natomiast osiągnąć każdy punkt leżący na jego obwodzie. Przy tym każdy węzeł siatki $\Sigma_3$ leżący we wnętrzu $H_k$ należy do pewnego sześciokąta $H_j$ , gdzie $j< k$ , a więc jest osiągalny drogą długości Zatem jedynie do punktów na obwodzie $H_k$ prowadzą drogi najkrótsze długości $k$ (na siatce $\Sigma_3$ ).

Ile jest takich dróg? Dowolny bok $AB$ sześciokąta $H_k$ zawiera $k+1$ punktów zbioru $W$ , a gdy je ponumerujemy $Q_0, \ldots,Q_k$ ( $Q_0 = A$ , $Q_k = B$ ), zauważymy, że do punktu $Q_r$ prowadzi $\binom{k}{r}$ najkrótszych dróg z punktu $O$ ; wynika to przez łatwą indukcję ze spostrzeżenia, że najkrótsze drogi do dowolnego z punktów $Q_0, \ldots,Q_{k-1}$ są przedłużeniami najkrótszych dróg do dwóch sąsiednich węzłów na obwodzie sześciokąta $H_{k-1}$ zaś do punktów $A$ i $B$ prowadzi po jednej drodze długości $k$ . (Innymi słowy: pisząc w każdym węźle siatki $\Sigma_3$ liczbę najkrótszych dróg z punktu $O$ do danego węzła otrzymujemy sześć kopii trójkąta Pascala, po jednej w każdym z sześciu sektorów płaszczyzny o wierzchołku $O$ , wyznaczonych przez kierunki boków siatki $\Sigma_3$ ). Jest więc $2^k$ najkrótszych dróg łączących $O$ z punktami boku $AB$ .

Sześciokąt $H_k$ ma sześć boków. Mamy zatem $6 \cdot 2^k-6$ najkrótszych dróg do punktów na obwodzie $H_k$ ; składnik $-6$ zapobiega dwukrotnemu policzeniu dróg prowadzących do wierzchołków $H_k$ .

W zadaniu chodzi o wyznaczenie liczby najkrótszych dróg (o początku $O$ ) długości $60$ na siatce $\Sigma_6$ , czyli liczby najkrótszych dróg (o początku $O$ ) długości $30$ na siatce $\Sigma_3$ . W myśl powyższych rozważań, liczba ta wynosi $6 \cdot 2^{30}-6$ .