Kolorowe kameleony

Matematyczne łamigłowki i zagadki...
Awatar użytkownika
Medea 2
Użytkownik
Użytkownik
Posty: 2491
Rejestracja: 30 lis 2014, o 11:03
Płeć: Kobieta
Podziękował: 23 razy
Pomógł: 479 razy

Kolorowe kameleony

Post autor: Medea 2 »

Na wyspie Bua żyją kameleony koloru czerwonego i zielonego. W momencie, gdy dowolne dwa z nich się spotykają, zmieniają kolor na przeciwny - z czerwonego na zielony i odwrotnie. Czyli dwa zielone kameleony staną się czerwone, natomiast para zielony-czerwony po prostu wymieni się kolorami. Kameleony nie są zbyt towarzyskie i naraz spotkają się najwyżej dwa. Na wyspie żyje 13 kameleonów zielonych i 19 czerwonych. Czy jest możliwe, że w pewnym momencie na wyspie będą kameleony tylko jednego koloru? Jeśli tak, jaka powinna być sekwencja spotkań? Jeśli nie, dlaczego?

Na wyspie Mua żyją trzy rodzaje kameleonów: błękitne, granatowe i purpurowe. Po spotkaniu się dwóch osobników tego samego koloru nie dzieje się nic. Za to spotkanie dwóch osobników różnych kolorów powoduje zmianę koloru na ten trzeci. Na wyspie żyje 56 kameleonów błękitnych, 34 granatowe i 66 purpurowych. Czy jest możliwe, że w pewnym momencie na wyspie będą kameleony tylko jednego koloru? Jeśli tak, jaka powinna być najkrótsza sekwencja spotkań? Jeśli nie, dlaczego?
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

Kolorowe kameleony

Post autor: »

Na wyspie Bua to niemożliwe, bo niezmiennikiem jest nieparzystość liczby kameleonów zielonych (tak samo dla czerwonych). Za każdym razem może albo przybyć dwa zielone, albo ubyć dwa zielone, albo nic się nie zmienić.

Natomiast na wyspie Mua to możliwe: wystarczy, że najpierw jedenaście razy spotka się para "błękitny-purpurowy", a potem czterdzieści pięć razy para "błękitny-granatowy" - po tych spotkaniach wszystkie kameleony będą purpurowe. Nie wystarczy do tego mniej spotkań, bo łatwo widać, że jeśli oznaczymy początkowe ilości kameleonów każdego koloru przez \(\displaystyle{ a,b,c}\), to do tego by został tylko kolor, który miało \(\displaystyle{ c}\) kameleonów potrzeba jest co najmniej \(\displaystyle{ \max (a,b)}\) spotkań, bo każdy kameleon pozostałych dwóch kolorów musi zmienić kolor.

Q.
Awatar użytkownika
Medea 2
Użytkownik
Użytkownik
Posty: 2491
Rejestracja: 30 lis 2014, o 11:03
Płeć: Kobieta
Podziękował: 23 razy
Pomógł: 479 razy

Kolorowe kameleony

Post autor: Medea 2 »

Pierwsze zadanie dobrze rozwiązane.

Drugie chyba nie. Na początku kameleonów jest 56, 34, 66. Po pierwszej serii spotkań będziemy mieli układ 45, 56, 55, a po drugiej: 0, 11, 145. I co teraz? Kameleony nie sklejają się przy spotkaniu.
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

Kolorowe kameleony

Post autor: »

Oczywiście, bredzę.

I oczywiście w drugim przypadku też się nie da - tym razem niezmiennikiem jest to, że reszty z dzielenia przez trzy liczb kameleonów poszczególnych kolorów to \(\displaystyle{ 0,1,2}\). A zatem nigdy nie dostaniemy sytuacji, że wszystkie \(\displaystyle{ 156}\) kameleonów jest jednego koloru, bo to oznacza zestaw reszt \(\displaystyle{ 0,0,0}\).

Q.
Awatar użytkownika
Medea 2
Użytkownik
Użytkownik
Posty: 2491
Rejestracja: 30 lis 2014, o 11:03
Płeć: Kobieta
Podziękował: 23 razy
Pomógł: 479 razy

Kolorowe kameleony

Post autor: Medea 2 »

Bardzo dobrze, takie też jest wzorcowe rozwiązanie: żadna z różnic pomiędzy liczebnością kameleonów nie jest podzielna przez 3, więc nie jest to możliwe.

Czas na ostatnie zadanie, wymagające trochę więcej sprytu. Na wyspie Wua żyją pomarańczowe, szare i turkusowe kameleony. Na wyspie znajduje również się Mroczna Jaskinia. Zaobserwowano, że:
- Gdy pomarańczowy kameleon zanurzy się w jaskini, po niedługim czasie wyjdą stamtąd kameleony szary i turkusowy
- Jeśli wkroczy tam turkusowy, wyjdą dwa kameleony pomarańczowe i jeden szary
- Jeśli wejdzie szary, wyjdą trzy kameleony pomarańczowe i jeden turkusowy
- Powyższe zamiany działają również w drugą stronę, czyli - na przykład - jeśli kameleon szary i turkusowy nieopatrznie zapałętają się w jaskini, wszelki ślad po nich zaginie, a na zewnątrz wyjdzie pomarańczowy
Na wyspie mieszka tylko jeden turkusowy kameleon. Czy jest możliwe, że na wyspie:
a) będzie więcej turkusowych kameleonów i żadnych innego koloru?
b) będą same pomarańczowe kameleony?
c) będą same szare kameleony?
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Kolorowe kameleony

Post autor: Dasio11 »

Niech \(\displaystyle{ \begin{pmatrix} a \\ b \\ c \end{pmatrix}}\) reprezentuje sytuację, w której na wyspie jest \(\displaystyle{ a}\) pomarańczowych kameleonów, \(\displaystyle{ b}\) turkusowych i \(\displaystyle{ c}\) szarych. Nazwijmy dozwolone operacje przez \(\displaystyle{ x, y, z}\), tj.

\(\displaystyle{ \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} \xrightarrow{x} \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix}, \quad
\begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} \xrightarrow{y} \begin{pmatrix} 2 \\ 0 \\ 1 \end{pmatrix}, \quad
\begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} \xrightarrow{z} \begin{pmatrix} 3 \\ 1 \\ 0 \end{pmatrix}}\)


a) Jest możliwe:

\(\displaystyle{ \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} \xrightarrow{y} \begin{pmatrix} 2 \\ 0 \\ 1 \end{pmatrix}
\xrightarrow{xxz} \begin{pmatrix} 3 \\ 3 \\ 2 \end{pmatrix}
\xrightarrow{x^3 z^2} \begin{pmatrix} 6 \\ 8 \\ 3 \end{pmatrix}
\xrightarrow{y^{-3}} \begin{pmatrix} 0 \\ 11 \\ 0 \end{pmatrix}}\)


b) Nie. Łatwo sprawdzić, że dozwolone operacje zachowują parzystość sumy \(\displaystyle{ b+c}\). Dla pojedynczego turkusowego kameleona suma jest nieparzysta, w sytuacji zaś, gdy wszystkie kameleony są pomarańczowe, suma jest parzysta.

c) Jest możliwe:

\(\displaystyle{ \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} \xrightarrow{y} \begin{pmatrix} 2 \\ 0 \\ 1 \end{pmatrix}
\xrightarrow{x} \begin{pmatrix} 1 \\ 1 \\ 2 \end{pmatrix}
\xrightarrow{yxyx} \begin{pmatrix} 3 \\ 1 \\ 6 \end{pmatrix}
\xrightarrow{z^{-1}} \begin{pmatrix} 0 \\ 0 \\ 7\end{pmatrix}}\)
ODPOWIEDZ