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?
Kolorowe kameleony
-
- 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
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.
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.
- Medea 2
- Użytkownik
- Posty: 2491
- Rejestracja: 30 lis 2014, o 11:03
- Płeć: Kobieta
- Podziękował: 23 razy
- Pomógł: 479 razy
Kolorowe kameleony
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.
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
- 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
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.
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.
- Medea 2
- Użytkownik
- Posty: 2491
- Rejestracja: 30 lis 2014, o 11:03
- Płeć: Kobieta
- Podziękował: 23 razy
- Pomógł: 479 razy
Kolorowe kameleony
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?
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?
- Dasio11
- 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
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}}\)
\(\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}}\)