Algebra liniowaTrudneZadanie nr 1361
Układy lampek osiągalne na planszy 4 × 4 przy przełączaniu sąsiadów
Na każdym polu planszy \(4\times4\) stoi lampka; początkowo wszystkie są zgaszone. Naciśnięcie dowolnego pola zmienia stan lampki na tym polu oraz na wszystkich polach mających z nim wspólny bok (zapalone gasną, zgaszone się zapalają). Ile różnych układów lampek (zapalonych i zgaszonych) można otrzymać, wykonując dowolnie wiele naciśnięć? Układ początkowy też liczymy.
Świetnie.
Jak rozwiązać to zadanie?
Potrzebujesz pomocy? Pokaż wskazówkę
Pracuj modulo 2: wynik zależy tylko od zbioru pól naciśniętych nieparzyście wiele razy, a przyporządkowanie „zbiór naciśnięć → układ lampek” jest liniowe. Policz zbiory naciśnięć, które niczego nie zmieniają; zauważ, że wyznacza je ich pierwszy wiersz.
Chcesz poznać sposób? Rozwiązanie krok po kroku
- Kolejność naciśnięć nie gra roli, a dwukrotne naciśnięcie pola nic nie zmienia. Wynik zależy więc tylko od zbioru \(X\) pól naciśniętych nieparzyście wiele razy. Utożsamiając zbiory pól i układy lampek z wektorami z \(\mathbb{Z}_2^{16}\), dostajemy odwzorowanie liniowe \(T\) (wynik dla \(X\) to suma wyników pojedynczych naciśnięć).
- Liczba osiągalnych układów to \(|\operatorname{im}T|=\frac{2^{16}}{|\ker T|}\), gdzie \(\ker T\) składa się ze zbiorów naciśnięć, po których każda lampka zmienia stan parzyście wiele razy.
- Dla \(X\in\ker T\) pierwszy wiersz wyznacza drugi: lampka \((1,j)\) jest przełączana przez pola \((1,j-1),(1,j),(1,j+1)\) oraz \((2,j)\), więc o tym, czy \((2,j)\in X\), decyduje parzystość. Tak samo wiersze 1 i 2 wyznaczają wiersz 3, a wiersze 2 i 3 — wiersz 4; pozostają warunki dla lampek wiersza 4. Zatem \(|\ker T|\le2^4\), a ponieważ wszystkie warunki są liniowe, wystarczy sprawdzić je dla czterech wektorów bazowych pierwszego wiersza.
- Pierwszy wiersz \(1000\): kolejne wiersze to \(1100\), \(1010\), \(0111\), a lampki wiersza 4 są przełączane odpowiednio \(2,2,4,2\) razy. Pierwszy wiersz \(0100\): kolejne wiersze \(1110\), \(0001\), \(1101\), przełączenia w wierszu 4: \(2,2,2,2\). Przypadki \(0010\) i \(0001\) wynikają z symetrii planszy. Zatem każdy z 16 pierwszych wierszy daje element jądra i \(|\ker T|=16\).
- Liczba osiągalnych układów: \(\frac{2^{16}}{2^4}=2^{12}=4096\).
Odpowiedź: \(4096\)
Czego warto się nauczyć?
Algebra liniowa to język geometrii i fizyki kwantowej: wektory, macierze i przekształcenia. W zadaniach mnożysz macierze, liczysz wyznaczniki i wartości własne, rozwiązujesz układy równań i opisujesz obroty, rzuty i symetrie.
Podobne zadania
- Wyznacznik macierzy 6×6 złożonej z cyklicznych przesunięć ciągu 1, 2, …, 6
- Cykliczny układ z sumami trzech sąsiednich niewiadomych: dla ilu n rozwiązanie jest jedyne
- Ranking pięciu szachistów wektorem Perrona przy dwóch remisach w tabeli punktowej
- Ile baz ortonormalnych R⁴ składa się wyłącznie z wektorów postaci (±1, ±1, ±1, ±1)/2