XL OM - III - Zadanie 3

Zawody matematyczne:

XL OM, 1988-1989

Etap:

III

Numerujemy krawędzie sześcianu liczbami od 1 do 12.
(a) Dowieść, że dla dowolnego ponumerowania istnieje co najmniej osiem trójek liczb całkowitych $(i,j,k)$ , gdzie $1\leq i< j < k\leq 12$ , takich, że krawędzie o numerach $i,j,k$ są kolejnymi bokami łamanej.
(b) Podać przykład ponumerowania, dla którego nie istnieje dziewięć trójek o własnościach wymienionych w (a).

Rozwiązanie

(a) Niech $V$ będzie dowolnym wierzchołkiem sześcianu i niech $p$ , $q$ , $r$ będą numerami krawędzi wychodzących z tego wierzchołka, przy czym $p < q < r$ . Pokażemy, że

$ \begin{split} (1) \qquad q \textrm{ jest środkowym wyrazem dwóch różnych trójek } (i,j,k) & \\ \textrm{o własnościach podanych w zadaniu}. & \end{split} $

Oznaczmy przez $W$ drugi koniec krawędzi o numerze $q$ . Numery pozostałych dwóch krawędzi wychodzących z $W$ oznaczmy przez $x$ i $y$ ; przyjmujmy, że $x < y$ .

Jeżeli $q < x$ , podane warunki spełniają trójki $(p,q,x)$ , $(p,q,y)$ .

Jeżeli $q > y$ , podane warunki spełniają trójki $(x, q, r)$ , $(y, q, r)$ .

Jeśli $x < q < y$ , dane warunki spełniają trójki $(p, q, y)$ , $(x, q, r)$ .

To dowodzi słuszności stwierdzenia (1).

Przyporządkujmy teraz każdemu z ośmiu wierzchołków sześcianu średni z trzech numerów krawędzi wychodzących z tego wierzchołka. Jedna liczba może być przyporządkowana co najwyżej dwóm wierzchołkom. Wśród przyporządkowanych liczb są więc co najmniej cztery różne. Każda z nich jest - zgodnie z (1) - środkowym wyrazem dwóch różnych trójek o żądanych własnościach. Istnieje zatem co najmniej osiem takich trójek.

(b) Cztery równoległe krawędzie numerujemy (w dowolny sposób) liczbami od $1$ do $4$ . Dalsze cztery równolegle krawędzie numerujemy liczbami od $5$ do $8$ . Wreszcie pozostałe cztery równoległe krawędzie numerujemy liczbami od $9$ do $12$ . Jeżeli trójka $(i,j,k)$ , $i < j < k$ , spełnia warunek podany w (a), to odcinki o numerach $i$ , $j$ , $k$ nie mogą leżeć w jednej płaszczyźnie (bo wówczas skrajne odcinki byłyby równoległe; ich numery byłyby oba większe albo oba mniejsze od numeru środkowej krawędzi). Muszą więc te odcinki reprezentować wszystkie trzy kierunki, a to znaczy, że $i \in \{1,2, 3,4\}$ , $j \in \{5,6, 7, 8\}$ , $k \in \{9,10,11,12\}$ . Przy tym każdy z odcinków o numerach $5$ , $6$ , $7$ , $8$ jest środkowym wyrazem dokładnie dwóch interesujących nas trójek.

Jest więc dokładnie osiem takich trójek.