XL OM - III - Zadanie 3

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

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

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.

Komentarze

Dodaj nową odpowiedź