Lampki i węzły

[mol_ksiazkowy]

Płaszczyznę podzielono na trójkąty równoboczne w ten sposób, że w każdym wierzchołku (będziemy dalej nazywać je węzłami) spotyka się sześć trójkątów. W każdym węźle znajduje się lampka, natomiast na każdym trójkącie jest włącznik, który zmienia stan lampek znajdujących się w węzłach będących wierzchołkami tego trójkąta (zgaszone zapalają się, a zapalone gasną). Rozstrzygnąć, czy zaczynając od sytuacji w której wszystkie lampki są zgaszone, możemy doprowadzić to tego, by paliła się dokładnie jedna lampka.

Ukryta treść:    

źródło: Wielkopolska Liga Matematyczna

[kerajs]

Każdemu z węzłów przypisuję nazwę (lub kolor lampki) A, B lub C, tak aby każdy najmniejszy trójkąt równoboczny w siatce miał wierzchołki A, B, C (Jeśli odległość między węzłami wynosi \(\displaystyle{ p}\), to najbliższe węzły A (podobnie jak B i C) są odległe o \(\displaystyle{ p\sqrt{3}}\)) . Możliwych jest osiem rodzajów ruchów: \(\displaystyle{ \left[ 1,1,1\right], \left[ 1,1,-1\right], \left[ 1,-1,1\right], \left[ -1,1,1\right], \left[ 1,-1,-1\right], \left[ -1,1,-1\right], \left[ -1,-1,1\right], \left[ -1,-1,-1\right] }\) , gdzie 1 oznacza włączenie zgaszonej lampki, a -1 zgaszenie świecącej się lampki z pozycji [A,B,C].
Zakładam, że istnieje sekwencja ruchów po której pozostanie zapalona tylko jedna żarówka, i będzie to żarówka A (czyli z pozycji startowej [0,0,0] przejdzie się do [1,0,0]). Musi się ona składać z naturalnej ilości powyższych ruchów i spełniać równanie:
\(\displaystyle{ \left[ 0,0,0\right]+a\left[ 1,1,1\right]+b \left[ 1,1,-1\right]+c \left[ 1,-1,1\right]+d \left[ -1,1,1\right]+\\+e\left[ 1,-1,-1\right]+f \left[ -1,1,-1\right]+g \left[ -1,-1,1\right]+h \left[ -1,-1,-1\right] =\left[ 1,0,0\right]}\)
równoważne układowi:
\(\displaystyle{ \begin{cases} a+b+c-d+e-f-g-h=1 \\ a+b-c+d-e+f-g-h=0 \\ a-b+c+d-e-f+g-h=0 \end{cases} }\)
Każda próba uproszczenia układu przez wyliczenie jednej z niewiadomych z trzeciego równania i podstawieniu jej do dwóch pierwszych wskazuje na sprzeczność układu, gdyż daje sprzeczne równanie pierwsze (bo liczby parzyste nie zsumują się do 1).
Przykład: wyliczam h z ostatniego równania:
\(\displaystyle{ \begin{cases} 2b-2d+2e-2g=1 \\ 2b-2c+2f-2g=0 \\ h=a-b+c+d-e-f+g\end{cases} }\)
Wniosek: Nie istnieje sekwencja pozostawiająca dokładnie jedną zapaloną żarówkę.

Wnioski wtórne:
Nie istnieje sekwencja pozostawiająca nieparzystą liczbę włączonych żarówek A (B lub C)
Nie istnieje sekwencja pozostawiająca włączone żarówki A i B ((B i C) lub (A i C)) , gdzie liczba żarówek przynajmniej jednego rodzaju jest nieparzysta.
Nie istnieje sekwencja pozostawiająca włączone żarówki A, B i C gdzie liczba żarówek jednego rodzaju jest nieparzysta a innego parzysta.

[a4karo]

Lampki leżą na przecięciach trzech rodzin równoległych prostych nachylonych do poziomu pod kątem `0^\circ, 60^\circ` i `120^\circ`.

Pokażemy najpierw ja wygasić trzy lampki sąsiadujące ze sobą poziomo `\times`-lampka zgaszona, o-lampka zapalona

\(\displaystyle{
\ \times\ \times\ \times\\
\circ\ \ \circ\ \ \circ}\)
Klikamy przełącznik w lewym trókącie i dostajemy
\(\displaystyle{
\ \circ\ \times\ \times\\
\times\ \times\ \circ}\)
Teraz klikamy środkowy trójkąt
\(\displaystyle{
\ \times\ \circ\ \ \times\\
\times\ \circ\ \ \circ}\)
i kliknięcie zapalpnego trójkąta gasi wszystko.

Ustalimy teraz jeden trójkąt - nazwijmy go `T`.
Klikamy `T` oraz wszystkie trójkąty na prawo od niego (tzn opierające sie jednym bokiem na tej samej prostej co `T`).
Po takiej operacji zapalony zostanie lewy dolny wierzchołek `T` oraz wszystkie górne wierzchołki klikniętych trójkątów. Te wierzchołki sąsiadują za sobą na jednej prostej i możemy je wszystkie wygasić grupując w trójki i używając wskazanego wyżej sposobu.
W ten sposób pozostanie zapalony jedynie lewy dolny wierzchołek `T`

[kerajs]

Ustalimy teraz jeden trójkąt - nazwijmy go `T`.
Klikamy `T` oraz wszystkie trójkąty na prawo od niego (tzn opierające sie jednym bokiem na tej samej prostej co `T`).
Po takiej operacji zapalony zostanie lewy dolny wierzchołek `T` oraz wszystkie górne wierzchołki klikniętych trójkątów.

O ile prawidłowo odczytuję ten przepis, to powinno być:
Po takiej operacji zapalony zostanie lewy dolny wierzchołek `T` oraz wszystkie górne wierzchołki klikniętych trójkątów i prawy dolny wierzchołek ostatniego z klikniętych trójkątów.

górne (...) wierzchołki sąsiadują za sobą na jednej prostej i możemy je wszystkie wygasić grupując w trójki i używając wskazanego wyżej sposobu.

Na linii przechodzącej przez dolne wierzchołki przełączanych trójkątów, węzły tego samego rodzaju są co trzecim wierzchołkiem. Skoro liczba przełączonych trójkątów jest wielokrotnością trójki, to zapalony lewy dolny wierzchołek `T` i prawy dolny wierzchołek ostatniego z klikniętych trójkątów są węzłem tego samego rodzaju (np: A).

[a4karo]

Ale tego jest nieskończenie wiele. Nie ma prawego dolnego wierzchołka

Dodano po 1 godzinie 27 sekundach:
Można jeszcze prościej :
Weźmy trzy trójkąty tworzące trapez o podstawach 2 i 1. Ma on trzy lampki w podstawie dolnej i dwie w podstawie górnej. Kliknięcie każdego z tych trójkątów zmienia stan wszystkich lampek w dolnej podstawie. Możemy więc puścić "kombajn" zapalający po trzy lampki na półprostej, a jednocześnie - z pewnym opóźnieniem - drugi kombajn gaszący kolejne lampki poczynając np od 117-tej. W ten sposób zostawimy 116 zapalonych lampek.

Przepyszna zabawa z nieskończonością.

Dodano po 2 godzinach 39 minutach 36 sekundach:
Można też zrobić tak, żeby po każdym kroku liczba zapalonych lampek była coraz większa, a po wszystkich krokach zostanie tylko jedna zapalona.

Albo tak, że zgaszone będą wszystkie oprócz trzech, ale o nich nie będziemy w stanie powiedzieć czy się palą, czy nie ,

[kerajs]

No dobra. Pośmiałem się, lecz czas na konkrety.
1. Moim zdaniem, nie istnieje skończona sekwencja przełączeń po której pozostanie jedna zapalona żarówka. I tego dotyczy moje rozwiązanie.
2. Rozwiązanie dla sekwencji nieskończonej jakoś mnie nie przekonuje. Pewnie dlatego, iż szkoda mi biednych kombajnów, które pracowicie wciąż zapalają i gaszą żarówki wykonując całkowicie bezsensowną pracę, skoro źle wybrały punkt startu.

[a4karo]

Dlaczego źle wybrały punkt startu?

Dodano po 17 godzinach 7 minutach 9 sekundach:
No to objaśniam:
ponumerujmy lampki leżące na prawej półprostej zawierającej podstawę wybranego trójkąta kolejno `0,1,2,3,4,...`
Przy pomocy trapezu-kombajnu wykonujemy taki ciąg:
zapalamy `0,1,2`
zapalamy `3,4,5`
gasimy `1,2,3`
zapalamy `6,7,8`
gasimy `4,5,6`
....

Po wykonaniu niekończenie wielu takich kroków pozostanie zapalona lampka `0`.

W zadaniu nie było wymagania skończonej sekwencji

[FasolkaBernoulliego]

Pozwolę sobie jeszcze wtrącić trzy grosze w sprawie tego "nieskończonego" rozwiązania. Rozważmy ciąg \(\displaystyle{ A_n}\) numerowany kolejnymi krokami algorytmu oznaczający liczbę zapalonych lampek po n-tym kroku. Czy jest to ciąg zbieżny (do 1)?

[a4karo]

Oczywiście że nie. Ilość lampek w każdym kroku będzie większa od jeden. Ale jeżeli ustalisz sobie jakąkolwiek lampkę różną od zerowej, to znajdziesz dla niej takie `N` że pozostanie ona zgaszona w każdym kroku o numerze większym niż `N`