LVIII OM - II - Zadanie 3

Zawody matematyczne:

LVIII OM, 2006-2007

Etap:

Z $n^2$ płytek w kształcie trójkąta równobocznego o boku $1$ ułożono trójkąt równoboczny o boku $n$ . Każda płytka jest z jednej strony biała, a z drugiej czarna. Ruch polega na wykonaniu następujących czynności: Wybieramy płytkę $P$ mającą wspólne boki z co najmniej dwiema płytkami, których widoczne strony mają kolor inny niż widoczna strona płytki $P$ . Następnie odwracamy płytkę $P$ na drugą stronę.

Dla każdego $n\ge 2$ rozstrzygnąć, czy istnieje początkowe ułożenie płytek, pozwalające wykonać nieskończony ciąg ruchów.

Rozwiązanie

Nazwijmy odcinkiem granicznym wspólny bok dwóch płytek, których widoczne strony mają różne kolory. Oczywiście liczba odcinków granicznych jest nieujemna i nie przekracza liczby $m$ wszystkich odcinków będących wspólnym bokiem dwóch płytek. Zbadamy, jak zmienia się liczba odcinków granicznych w wyniku wykonania dozwolonego ruchu.

Każda z $n^2$ płytek ma wspólne boki z co najwyżej trzema innymi płytkami. Odwrócenie płytki jest dopuszczalne, jeżeli co najmniej dwa z takich boków są odcinkami granicznymi. Przypuśćmy, że odwracamy płytkę $P$ . Wówczas odcinki graniczne mogą pojawić się albo zniknąć jedynie na bokach płytki $P$ . Ponadto bok płytki $P$ jest po odwróceniu odcinkiem granicznym wtedy i tylko wtedy, gdy przed odwróceniem nie był on odcinkiem granicznym. Wynika stąd, że w wyniku wykonania dozwolonego ruchu liczba odcinków granicznych zmniejsza się.

Udowodniliśmy w ten sposób, że z dowolnego początkowego ułożenia płytek można wykonać nie więcej niż $m$ ruchów.

Odpowiedź: Dla żadnego $n\ge 2$ nie istnieje ułożenie pozwalające wykonać nieskończony ciąg ruchów.