LVIII OM - II - Zadanie 3

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.

Komentarze

Dodaj nową odpowiedź