XXXVIII OM - III etap

III etap XXXVIII Olimpiady Matematycznej

XXXVIII OM - III - Zadanie 1

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

III

W kwadracie o boku 1 znajduje się $n$ punktów ( $n > 2$ ). Dowieść, że można je ponumerować $P_1, P_2, ..., P_n$ tak, by \sum_{i=1}^n |P_{i-1}P_i|^2 \leq 4 (przyjmujemy $P_0=P_n$ ).

Rozwiązanie

Dowód oprzemy na następującym lemacie:
Lemat. W trójkącie prostokątnym $ABC$ , w którym $|AB| = |BC| = a$ , $|\measuredangle ABC| = 90^\circ$ , znajduje się $k$ punktów ( $k \geq 1$ ). Można je wówczas ponumerować $P_1, \ldots , P_k$ tak, że

$ \sum_{i=1}^{k+1}|P_{i-1}P_i|^2 \leq 2 a^2 $

(przyjmujemy $P_0 = A$ , $P_{k+1} = C$ ).

Dowód. Stosujemy indukcję. Gdy $k = 1$ , mamy jeden punkt $P$ i do udowodnienia nierówność $|AP|^2+|PC|^2 \leq 2a^2$ , która wynika z tego, że $2a^2 = |AC|^2$ , a kąt $APC$ jest nieostry.

Ustalmy liczbę naturalną $m \geq 2$ i załóżmy, że teza lematu zachodzi dla dowolnego trójkąta prostokątnego równoramiennego i dowolnego zawartego w nim zbioru Uczącego k punktów, gdzie $k$ jest dowolną liczbą naturalną mniejszą niż $m$ .

Niech będzie dany trójkąt $ABC$ ( $|AB| = |BC| = a$ , $|\measuredangle B| = 90^\circ$ ), a w nim zbiór $Z$ złożony z $m$ punktów. Niech $A_0B_0C_0$ będzie najmniejszym trójkątem o bokach równoległych do odpowiednich boków trójkąta $ABC$ , zawierającym zbiór $Z$ . (,,Konstrukcja'': każdą z trzech prostych zawierających boki trójkąta $ABC$ przesuwamy równolegle aż do napotkania pierwszego z punktów zbioru $Z$ ; przesunięte proste utworzą trójkąt $A_0B_0C_0$ , o którym mowa.)

Oznaczmy przez $E_O$ spodek wysokości opuszczonej z wierzchołka $B_0$ na przeciwprostokątną $A_0C_0$ . Oczywiście

$ |B_0E_0| = \frac{1}{2} |A_0C_0| \leq \frac{1}{2} |AC| = \frac{1}{2} \sqrt{2a}. $

Oznaczmy trójkąty (domknięte) $A_0E_0B_0$ i $B_0E_0C_0$ odpowiednio przez $\Delta'$ i $\Delta''$ , a ich część wspólną, czyli odcinek $B_0E_0$ , przez $I$ . Każdy z trójkątów $\Delta'$ i $\Delta''$ zawiera punkty zbioru $Z$ ; inaczej trójkąt $A_0B_0C_0$ nie byłby minimalny. Dzielimy teraz zbiór $Z$ na dwa niepuste podzbiory $Z'$ i $Z''$ zawarte odpowiednio w $\Delta'$ i $\Delta''$ : punkty zbioru $Z_n \cap \Delta' \setminus I$ zaliczamy do $Z'$ , punkty zbioru $Z_n \cap \Delta' \setminus I$ zaliczamy do $Z''$ , a punkty zbioru $Z \cap l$ rozdzielamy między zbiory $Z'$ i $Z''$ w dowolny sposób, z jedynym zastrzeżeniem, by powstałe zbiory $Z'$ i $Z"$ były niepuste; jest to możliwe, gdyż w myśl poprzedniej konkluzji $Z \cap \Delta' \neq\emptyset$ , $Z_n \cap \Delta'' \neq \emptyset$ , a $m \geq 2$ .

Niech $k$ będzie liczbą elementów zbioru $Z'$ , a $m-k$ liczbą elementów zbioru $Z''$ ( $0 < k < m$ ). Na mocy przesłanki indukcyjnej zastosowanej do trójkątów $\Delta'$ i $\Delta'$ oraz zawartych w nich zbiorów $Z'$ i $Z"$ można ponumerować punkty tych zbiorów odpowiednio: $P_1, \ldots, P_k$ oraz $P_{k+1}, \ldots, P_m$ tak, by

$ (1) \qquad |A_0P_1l^2+|P_1P_2|^2+\ldots+|P_kB_0|^2 \leq 2|B_0E_0|^2 \leq a^2, $

$ (2) \qquad |B_0P_{k+1}|^2+|P_{k+1}P_{k+2}^2+ \ldots +|P_mC_0| \leq 2|B_0E_0|^2 < a^2. $

Zauważmy teraz, że

$ |P_kB_0|^2+|B_0P_{k+1}|^2 \geq |P_kP_{k+1}|^2 $

(bo $|\measuredangle P_kB_0P_{k+1}| \leq 90^\circ$ ), a ponadto

$ |AP_1| \geq |A_0P_1|, \quad |P_mC| \geq |P_mC_0|| $

(rysunek 17). Wobec tego

$ \begin{split} &|AP_1|^2 \ldots +|P_kP_{k+1}|^2+ \ldots +|P_mC|^2 \leq\\ &\qquad \leq \mathrm{(suma lewych stron nierówności (1) i (2))} \leq 2a^2. \end{split} $

Znaczy to, że ponumerowanie $P_1, \ldots, P_m$ punktów zbioru $Z$ spełnia postawiony warunek. Indukcyjny dowód lematu jest tym samym zakończony.

Aby wydedukować z lematu tezę zadania, dzielimy dany kwadrat $ABCD$ (o boku długości 1) na dwa trójkąty prostokątne przekątną $AC$ . Dany zbiór $n$ punktów dzielimy na dwa podzbiory, zawarte odpowiednio w jednym i drugim trójkącie i liczące odpowiednio $k$ i $n-k$ punktów ( $0 \leq k \leq n$ ); punkty leżące na przekątnej zaliczamy do któregokolwiek z tych zbiorów.

Rozpatrzymy dwa przypadki:

1. $0 < k < n$ . Z lematu wynika możliwość ponumerowania punktów w każdym z tych zbiorów: $P_1, \ldots, P_k$ oraz $P_{k+1}, \ldots, P_k$ tak, żeby były spełnione warunki:

$ (3) \qquad |AP_1|^2+ \ldots +|P_kC|^2 \leq 2, $

$ (4) \qquad |CP_{k+1}|^2+ \ldots +|P_nAl^2\leq 2. $

Podobnie, jak w dowodzie lematu, skorzystamy z nierówności

$ |P_kC|^2+|CP_{k+1}|^2 \geq |P_kP_{k+1}|^2 \quad |P_nA|^2 + |AP_1|^2 \geq |P_nP_1|^2, $

wynikających z tego, że $|\measuredangle P_kCP_{k+1}| \leq 90^\circ$ , $|\measuredangle P_nAP_1| \leq 90^\circ$ (rysunek 18). Dostajemy nierówność

$ \begin{split} &|P_1P_2|^2 \ldots +|P_kP_{k+1}|^2+ \ldots +|P_nP_1|^2 \leq\\ &\qquad \leq \mathrm{(suma lewych stron nierówności (3) i (4))} \leq 4. \end{split} $

Zatem numeracja $P_1,\ldots, P_n$ czyni zadość warunkowi zadania.

2. $k = 0$ lub $k = n$ . Wszystkie dane punkty leżą wówczas w jednym z trójkątów $ABC$ , $CDA$ i zgodnie z lematem możemy je ponumerować $P_1, \ldots, P_n$ , tak że

$ |AP_1|^2+|P_1P_2|+ \ldots +|P_{n-1}P_n|^2+|P_nC|^2 \leq 2. $

Tym bardziej więc

$ |P_1P_2|+ \ldots +|P_{n-1}P_n|^2 \leq 2. $

co w połączeniu z oczywistą nierównością $|P_nP_1l^2 \leq 2$ daje żądany warunek

$ |P_1P_2|+ \ldots +|P_{n-1}P_n|^2+|P_nP_1|^2 \leq 4. $

XXXVIII OM - III - Zadanie 2

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

III

W okrąg o długości 1 wpisano $n$ -kąt foremny. Spośród łuków okręgu mających końce w wierzchołkach tego wielokąta losujemy ze zwracaniem pięć łuków $L_1, \ldots, L_5$ , przy czym dla wszystkich łuków prawdopodobieństwo wylosowania jest jednakowe. Wykazać, że wartość oczekiwana długości części wspólnej $L_1\cap L_2 \cap L_3 \cap L_4 \cap L_5$ nie zależy od $n$ .

Rozwiązanie

Wierzchołki wielokąta dzielą okrąg na $n$ łuków długości $1/n$ . Ponumerujmy te łuki: $J_1, \ldots, J_n$ . Oznaczmy przez $\mathcal{L}$ zbiór, z którego dokonuje się losowania. Elementami zbioru $\mathcal{L}$ są łuki danego okręgu, z których każdy ma dwa końce, będące różnymi wierzchołkami rozważanego wielokąta (patrz: Uwaga). Innymi słowy: łuk $L$ danego okręgu jest elementem zbioru $\mathcal{L}$ wtedy i tylko wtedy, gdy jest sumą m łuków $J_i$ gdzie $0 < m < n$ .

Ustalmy numer $i \in \{1, \ldots,n\}$ . Wybierzmy losowo jeden łuk $L \in \mathcal{L}$ . Prawdopodobieństwo tego, że łuk $L$ zawiera ustalony łuk $J_i$ równa się $1/2$ :

$ (1) \qquad P(L \supset J_i) = \frac{1}{2}. $

Wynika to stąd, że każda para wierzchołków wielokąta wyznacza dwa różne łuki, z których dokładnie jeden zawiera $J_i$ , a zatem te łuki $K \in \mathcal{L}$ , które zawierają nasz łuk stanowią dokładnie połowę w zbiorze $\mathcal{L}$ .

Rozważane w zadaniu doświadczenie polega na wylosowaniu pięciu łuków $L_1, L_2, L_3, L_4, L_5 \in \mathcal{L}$ , z dopuszczeniem powtórzeń. Przyjmujemy, że losowania są niezależne: prawdopodobieństwo tego, że część wspólna wylosowanych łuków zawiera ustalony łuk $J_i$ równa się iloczynowi prawdopodobieństw (1), branych kolejno dla $L = L_1, \ldots, L_5$ :

$ (2) \qquad \begin{split} &P((L_1 \cap L_2 \cap L_3 \cap L_4 \cap L5) \cap J_i) =\\ &=P((L_1 \supset J_i) \vee(L_2 \supset J_i) \vee(L_3 \supset J_i) \vee(L_4 \supset J_i) \vee(L_5 \supset J_i) ) = \left( \frac{1}{2} \right)^5 \end{split} $

Dla $i \in \{1, \ldots,n\}$ niech $X_i$ oznacza zmienną losową określoną następująco:

$ X =\left\{ \begin{array}{ll} 1& \textrm{gdy } (L_1 \cap L_2 \cap L_3 \cap L_4 \cap L5) \cap J_i\\ 0& \textrm {w przeciwnym razie} \end{array} \right. $

Wobec równości (2) wartość oczekiwana tej zmiennej wynosi

$ (3) \qquad E(X_i) = \left(\frac{1}{2}\right)^5\quad \textrm{dla } i = 1,\ldots, n. $

Część wspólna $L_1 \cap L_2 \cap L_3 \cap L_4 \cap L5$ może być zbiorem pustym, zbiorem jednopunktowym lub sumą pewnej liczby łuków $J_i$ . Jej długość - czyli badana zmienna losowa $X$ - równa się liczbie zawartych w owej sumie łuków $J_i$ , pomnożonej przez $1/n$ (wspólną długość wszystkich $J_i$ )- Zatem $X$ przyjmuje wartość $k/n$ wtedy i tylko wtedy, gdy dokładnie $k$ spośród zmiennych losowych $X_1, \ldots, X_n$ ma wartość $1$ , a reszta $0$ . Wobec tego
$X = \frac{1}{2} (X_1+ \ldots +X_n)$ i w konsekwencji wartość oczekiwana zmiennej $X$ równa się średniej arytmetycznej wartości (3), czyli

$ E(X) = \frac{1}{n}(E(X_1)+ \ldots +E(X_n)) = \left(\frac{1}{2}\right)^5. $

Otrzymana liczba, jak widać, nie zależy od $n$ .

Uwaga. Ze sformułowania treści zadania nie wynika jednoznacznie, czy słowo ,,końce'' użyte w liczbie mnogiej niesie w sobie informację, że każdy z rozważanych łuków $L$ ma dwa różne końce - a więc, czy nie są dopuszczone do rozważań łuki ,,niewłaściwe'', o końcach pokrywających się, a tym samym redukujące się do pojedynczego punktu, lub przeciwnie, będące całym okręgiem. Na pytania uczestników zawodów w tej sprawie udzielano odpowiedzi, że łuki ,,niewłaściwe'' nie są brane pod uwagę - czyli tak, jak w podanym wyżej rozwiązaniu. Warto jednak zauważyć, że wynik i całe rozumowanie nie zmieni się, gdy włączymy do zbioru $\mathcal{L}$ . łuki ,,niewłaściwe'', pod warunkiem, że przyjmiemy istnienie $n$ łuków jednopunktowych i także w łuków otrzymanych przez obieg całego okręgu (początek i koniec w którymkolwiek wierzchołku). Nadal bowiem każdy z łuków $\mathcal{L}$ , będzie zawarty dokładnie w połowie łuków z $L$ , dzięki czemu pozostanie w mocy wzór (1).

Zaznaczmy jeszcze, że również założenie niezależności kolejnych pięciu losowań jest tu przyjmowane milcząco.

XXXVIII OM - III - Zadanie 3

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

III

Dany jest wielomian $W$ o współczynnikach całkowitych nieujemnych. Określamy ciąg liczb $(p_n)$ , gdzie $p_n$ jest sumą cyfr liczby $W(n)$ . Dowieść, że pewna liczba występuje w ciągu $(p_n)$ nieskończenie wiele razy.

Rozwiązanie

Niech $W(x) = a_mx^m + \ldots +a_1x+a_0$ ( $a_i$ - całkowite nieujemne) i niech $q$ będzie liczbą cyfr w zapisie dziesiętnym największej z liczb $a_0, \ldots, a_m$ . Niech $\overline{a_i}$ oznacza $q$ -cyfrowy zapis dziesiętny liczby $a_i$ ; gdy $a_i$ ma mniej niż $q$ cyfr, piszemy na początku zera. Wówczas dla $r > q$ przedstawienie dziesiętne liczby $W(10^r)$ ma postać

$ \overline{a_m\vphantom{b}}\, \overline{b}\, \overline{a_{m-1}\vphantom{b}}\,\overline{b}\ldots \overline{b} \overline{a_1\vphantom{b}}\,\overline{b}\,\overline{a_0\vphantom{b}}, $

gdzie $\bar{b}$ jest blokiem złożonym z $r-q$ zer. Suma cyfr każdej z tych liczb równa się sumie cyfr wszystkich współczynników wielomianu $W$ . Jest to więc wspólna wartość wszystkich wyrazów ciągu $(p_n)$ o numerach $n = 10^r$ , $r \leq q$ .

XXXVIII OM - III - Zadanie 4

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

III

W zbiorze czworościanów o polu podstawy 1, polu powierzchni całkowitej 4 i mających równe kąty nachylenia ścian bocznych do podstawy znaleźć czworościan o maksymalnej objętości.

Rozwiązanie

Niech $ABCD$ będzie dowolnym czworościanem spełniającym podane warunki:

$ (1) \qquad \mathrm{pole} (ABC) = 1,\ \mathrm{pole} (BCD)+\mathrm{pole} (CDA)+\mathrm{pole}(DAB) = 3; $

$ (2) \qquad \textrm{ściana $ABC$ tworzy równe kąty dwuścienne z pozostałymi ścianami.} $

Z warunku (2) wynika, że punkt $D'$ będący rzutem punktu $D$ na płaszczyznę $ABC$ znajduje się w jednakowej odległości od prostych $BC$ , $CA$ , $AB$ (równej $r = h \ctg \phi$ , gdzie $h = |DD'|$ , a $\phi$ jest rozwartością rozważanych kątów dwu-ściennych). Ponadto, punkt $D'$ leży w obrębie trójkąta $ABC$ ; gdyby bowiem leżał na zewnątrz tego trójkąta, to wśród kątów dwuściennych, o których mowa w (2), znalazłby się co najmniej jeden kąt ostry i co najmniej jeden rozwarty - wbrew ich postulowanej równości. $A$ wobec tego punkt $D'$ jest środkiem koła wpisanego w trójkąt $ABC$ . Promień tego koła ma długość $r$ .

Wysokość każdej ze ścian bocznych opuszczona z wierzchołka $D$ ma długość $w = \sqrt{h^2+r^2}$ . Oznaczając przez p połowę obwodu trójkąta $ABC$ otrzymujemy z równości (1):

$ 1 = \mathrm{pole} (ABC) = pr \quad \textrm{więc } r = \frac{1}{p} $

oraz

$ \begin{split} 3 &=\frac{1}{2} |BC| \cdot w+ \frac{1}{2} |CA| \cdot w+ \frac{1}{2} |AB| \cdot w = pw = \\ &=p \sqrt{h^2+r^2}=p \sqrt{h^2+\frac{1}{p+2}}=\sqrt{p^2h^2+1}. \end{split} $

Stąd $p^2h^2 = 8$ , czyli $h = 2\sqrt{2} p$ . Objętość czworościanu $ABCD$ równa się zatem

$ (3) \qquad V = \frac{1}{3} h \cdot \mathrm{pole}(ABC) = \frac{1}{3} h =\frac{2\sqrt{2}}{3p}. $

Spośród wszystkich trójkątów o polu $1$ najmniejszy obwód ma trójkąt równoboczny (patrz: Uwaga 2). Na mocy (3) minimalna wartość $p$ daje maksymalną wartość $V$ . Tak więc w rozpatrywanej klasie czworościanów największą objętość ma czworościan $ABCD$ o następujących własnościach: podstawa $ABC$ jest trójkątem foremnym o polu $1$ ; spodek wysokości z $D$ pokrywa się ze środkiem koła wpisanego w trójkąt $ABC$ ; powierzchnia boczna ma pole $3$ .

Jedynym (z dokładnością do izometrii) czworościanem o tych własnościach jest czworościan foremny mający ściany o polu $1$ . Stanowi on rozwiązanie zadania.

Uwaga 1. Gdyby podany w treści zadania warunek rozumieć jako równość nachylenia ścian bocznych do płaszczyzny podstawy (a niekoniecznie do samej ściany $ABC$ ), rozumowanie wymagałoby następującej modyfikacji: punkt $D'$ , jako leżący w jednakowej odległości $r$ od prostych $BC$ , $CA$ , $AB$ , musi być środkiem koła wpisanego w trójkąt $ABC$ lub jednego z kół dopisanych. Równości $3 = p \sqrt{h^2+r^2}$ oraz $V = h/3$ zachowują moc. Dla ustalonego trójkąta $ABC$ maksymalną wartość $V$ otrzymamy więc obierając minimalną (z czterech możliwych) wartość $r$ - czyli długość promienia koła wpisanego. To znaczy, że inne możliwości można zaniedbać.

Uwaga 2. W końcowym fragmencie rozwiązania powołaliśmy się na znane twierdzenie, które mówi, że wśród wszystkich trójkątów o polu $1$ najmniejszy obwód ma trójkąt foremny. Dla kompletności podamy dowód tego faktu.

Niech $a$ , $b$ , $c$ będą długościami boków trójkąta o polu $1$ i niech $p = (a+b+c)/2$ . Mamy dowieść, że $p\geq \sqrt[4]{27}$ (połowa obwodu trójkąta foremnego o polu $1$ ). Z wzoru Herona i z nierówności między średnimi mamy

$ \frac{1}{p}=(p-a(p-b)(p-c)\leq \left(\frac{p-a+p-b+p-c}{3}\right)^3 = \left(\frac{p}{3}\right)^3 $

czyli $p^4 \geq 27$ , o co chodziło.

XXXVIII OM - III - Zadanie 5

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

III

Wyznaczyć najmniejszą liczbę naturalną $n$ , dla której liczba $n^2-n+11$ jest iloczynem czterech liczb pierwszych (niekoniecznie różnych).

Rozwiązanie

Niech $f(x) = x^2-x+11$ . Wartości przyjmowane przez funkcję $f$ dla argumentów całkowitych są liczbami całkowitymi niepodzielnymi przez $2$ , $3$ , $5$ , $7$ . Przekonujemy się o tym badając reszty z dzielenia $n$ i $f(n)$ przez te cztery początkowe liczby pierwsze:

\begin{tabular}{lllll}
&\multicolumn{4}{l}{Reszty z dzielenia:}\\
&przez 2&przez 3&przez 5&przez 7\\
$n$ &0 1&0 1 2 &0 1 2 3 4&0 1 2 3 4 5 6\\
$f(n)$ &1 1&2 2 1&1 1 3 2 3& 4 4 6 3 2 3 6
\end{tabular}

Zatem dowolna liczba $N$ będąca wartością $f$ dla argumentu naturalnego i spełniająca podany w zadaniu warunek musi mieć postać $N = p_1p_2p_3p_4$ , gdzie czynniki $p_i$ są liczbami pierwszymi $\geq 11$ .

Najmniejsza z takich liczb $N= 11^4$ prowadzi do równania kwadratowego $x^2-x+11=11^4$ o pierwiastkach niewymiernych. Ale już druga z kolei $N = 11^3 \cdot 13$ jest równa wartości $f(132)$ . Funkcja $f$ jest ściśle rosnąca w przedziale $\langle 1/2; \infty)$ wobec czego znaleziona minimalna możliwa wartość $N$ wyznacza minimalną możliwą wartość $n$ . Stąd odpowiedź: $n = 132$ .

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$ .