, który prenumeruję znalazłem łamigłówkę z którą nie mogli sobie poradzić autorzy czasopisma. Może ktoś z was potrafi ją rozwiązać? Nawet, jeżeli sami nie jesteście w stanie jej rozwiązać, to pokażcie ją swoim nauczycielom lub wykładowcom matematyki, albo znajomym, którzy lubią łamigłówki.
A oto skan łamigłówki (wrzuciłem na 2 różne serwery, do wyboru):
[url=http://img185.imageshack.us/my.php?image=lamiglowkasirarthuraqh9.jpg][/url]
Jeżeli ją rozwiążecie, a interesują was nagrody, to najpierw [url=http://swiatmatematyki.pl/index.php?p=7]wyślijcie odpowiedź do "Świata Matematyki"[/url], a dopiero później opublikujcie ją na forum.
Tak na marginesie: [url=http://swiatmatematyki.pl/]"Świat Matematyki"[/url] czytam od samego początku (czyli od 3 numerów i jednego numeru specjalnego na temat kongruencji) i uważam, że to bardzo ciekawa i warta swojej ceny (9 zł za numer, koszty przesyłki wliczone w cenę) gazeta, zwłaszcza dla uczniów gimnazjów, a nawet dla osób posiadających braki w swojej wiedzy matematycznej, gdyż wyjaśnia wszystko po kolei, bez żadnych luk w rozumowaniu.
Edit: Wygląda na to, że jeden z serwerów przestał działać, więc plik znajduje się teraz na drugim z nich.
Ostatnio zmieniony 22 sie 2008, o 13:19 przez loonatic, łącznie zmieniany 2 razy.
salda_fadla pisze:Wrzucanie do wora z zagadkami kazdego problemu matematycznego jest bez sensu.
W takim razie zasugeruj lepszy dział, a poproszę moderatorów o przeniesienie tematu. Wydawało mi się, że "Łamigłówki i zagadki logiczne" to odpowiednie miejsce dla tego typu problemu...
A, tak przy okazji. W nazwie działu jest literówka. Jest: "Łamigłowki", powinno być: "Łamigłówki". Dobrze byłoby poprawić.
salda_fadla pisze:I czemu dziewczynki sir Eddingtona sa tak wyzute z kobiecej intuicji, ze ani jedna nie trafila ani jednego zwierzaka?
Musiałbyś udać się za Styks lub cofnąć się do 1944 roku, aby się tego dowiedzieć .
marcell, jak już pisałem na PW chodzi o sposób rozwiązania, a nie samą odpowiedź, która, jak powiedziałeś, jest wynikiem użycia metody brute force.
Może jednak pozwoli to komuś opracować rozwiązanie...
Numerujemy zwierzęta od 1 do 8, tak że samice mają parzyste numery,
a samce z tego samego gatunku mają numer o jeden mniejszy.
Propozycja każdego dziecka może być przedstawiona jako permutacja.
Używamy standardowego oznaczenia permutacji jako układu orbit.
Np: (1 3 5)(6 8) oznacza 1->3, 3->5, 5->1, 6->8, 8->6 a 2, 4, 7 są niezmienione.
[1] Niech P będzie propozycjami jakiegoś dziecka. Wtedy P(partner(i)) = partner(P(i)).
[2] Jeśli Q jest propozycjami następnego dziecka, wtedy [P,Q] = T, gdzie [P,Q] jest komutatorem
P i Q (P zestawiony z P odwrotnym zestawiony z Q odwrotnym) i T jest szczególną permutacją
(1 2) (3 4) (5 6) (7 8) która po prostu zamienia każde zwierzę z jego partnerem.
[3] Jeśli P reprezentuje chłopca, wtedy P*P = I (używamy * dla kompozycji, oraz I dla permutacji
tożsamości: (1)(2)(3)(4)(5)(6)(7)(8))
[4] Jeśli P reprezentuje dziewczynkę, wtedy P*P = T.
[1] oraz [4] razem oznaczają, że wszystkie propozycje dziewczynek muszą mieć formę:
(A B C D) (E F G H) gdzie A oraz C są partnerami, podobnie B i D, E i G oraz F i H.
Więc w ogólnej postaci niech Marysia = (1 3 2 4) (5 7 6 8)
Widzimy, że jedyne możliwości dla pozostałych dziewczynek „zgodne” z Marysią
(przez "zgodne" rozumiemy relacje wyrażone w [2]) to:
d1: (1 5 2 6) (3 8 4 7)
d2: (1 6 2 5) (3 7 4 8)
d3: (1 7 2 8) (3 5 4 6)
d4: (1 8 2 7) (3 6 4 5)
Należy zauważyć że d1 jest niekompatybilne z d2, a d3 z d4.
Zatem każde 4 Marysi i d1 nie są wzajemnie zgodne.
A więc są najwyżej 3 dziewczynki:
Marysia, d1 i d3 (w ogólnej postaci)
Według [1] oraz [3], każdy chłopiec musi być reprezentowany jako wynik transpozycji
oraz/lub zbiory jednoelementowe np: (1 3) (2 4) (5) (6) (7) (8) lub (1) (2) (3 4) (5 8) (6 7).
Niech J przedstawia próbę Jasia i rozważamy J(1).
Jeśli J(1) = 1, wtedy J(2) = 2 (przez [1]) używając [2] i Marysia J(3) = 4, J(4) = 3,
oraz d1 i J => J(5) = 6, J(6) = 5, oraz d3 i J => J(8) = 7 J(7) = 8
tzn. J = (1)(2)(3 4)(5 6)(7 8). Ale [J, Marysia] T.
Zatem widzimy, że J nie może mieć stałych (ustalonych) punktów, J(i) i dla wszystkich i,
skoro nie ma nic szczególnego w i = 1.
Jeśli J(1) = 2, wtedy dostajemy od Marysi, że J(3) = 3 - sprzeczność.
Jeśli J(1) = 3, wtedy J(2) = 4, J(3) = 1, J(4) = 2 (Marysi) =>
J(5) = 7, J(6) = 8, J(7) = 5, J(8) = 6 => J = (1 3)(2 4)(5 7)(6 8) (od d1)
Ale wtedy J jest niezgodny z d3.
Podobna analiza pokazuje że J(1) nie może być 4,5,6,7 ani 8; tzn. żadne J
może być zgodne z wszystkimi 3 dziewczynkami. A więc nie tracąc „ogólności”,
eliminujemy d3.
Zauważmy że C1 i C2 są niezgodne, podobnie jak C3 i C4, C5 i C6, więc najwyżej 3 z nich
jest wzajemnie zgodnych. A właściwie, Marysia, d1, C1, C3 oraz
C5 są wszystkie wzajemnie zgodne (podobnie jak wszystkie inne możliwości które mamy
wybierając C1 lub C2, C3 lub C4, C5 lub C6). Więc jeśli są 2 dziewczynki, może być 3 chłopców,
ale nie więcej, a już wyeliminowaliśmy przypadek z 3 dziewczynkami i 1 chłopcem.
Jedynym innym przypadkiem do rozważenia jest 4 chłopców i 1 dziewczynka. Załóżmy że jest
Marysia i 4 chłopców. Każdy chłopiec musi odwzorować 1 do innej cyfry, inaczej nie będzie
wzajemnej zgodności. Np. jeśli c1 i c2 odwzorowują 1 do 3, wtedy obaj odwzorowują 3 do 1
(skoro odwzorowanie chłopców składa się z transpozycji), więc obaj
c1*c2 oraz c2*c1 odwzorowują 1 do 1. Ponadto, c1 i c2 nie mogą odwzorować 1 na
partnerach. Np. jeśli c1(1) = a oraz c jest partnerem a, wtedy
c1(2) = c. Jeśli c2(1) = c, wtedy c2(2) = a. Wtedy c1*c2(1) = c1(c) = 2
i c2*c1(1) = c2(a) = 2 (pamiętając, że chłopcy są wszyscy transpozycjami).
Zatem 4 chłopcy muszą być:
C1: (1)(2)... or (1 2)....
C2: (1 3)... or (1 4) ...
C3: (1 5) ... or (1 6) ...
C4: (1 7) ... or (1 8) ...
Rozważmy C4.
Jedyną permutacją formy (1 7)... która jest zgodna z Marysią ( (1 3 2 4) (5 7 6 8) ) jest:
(1 7)(2 8)(3 5)(4 6)
Jedyną (1 8)... możliwością jest:
(1 8)(2 7)(3 6)(4 5)
Załóżmy C4 = (1 7)(2 8)(3 5)(4 6)
Jeśli C3 zaczyna się (1 5), to musi być (1 5)(2 6)(3 8)(4 7) aby było zgodne z C4.
Więc jest też zgodne z Marysią.
Biorąc to pod uwagę, oraz że C2 zaczyna się (1 3) dostajemy C2 = (1 3)(2 4)(5 8)(6 7)
aby było zgodne z C4. Ale wtedy C2*C3 i C3*C2 odwzorowują 1 do 8.
Tzn. żadne C2 jest wzajemnie zgodne z C3 i C4.
Podobnie jeśli C2 zaczyna się (1 4) to musi być (1 4)(2 3)(5 7)(6 8) aby pasowało C4, ale to
nie pasuje do C3.
Również C3 zaczynające się (1 6) uniemożliwia C2 i z tego samego powodu eliminuje C4 = (1 8)...
Więc C4 jest niemożliwe.
Tzn. najwyżej 3 chłopców jest wzajemnie zgodnych z Marysią, więc 2 dziewczynki i 3
chłopców to rozwiązanie optymalne.
Zatem:
jest optymalnym rozwiązaniem, gdzie Jaś jest zwycięzcą (4 prawidłowe: 1 2 7 i 8)
Inny sposób:
Można użyć programu typu “brute force”.
Mamy 24 permutacje 4 gatunków i 2 płci, które tworzą 2*2*2*2 możliwości dla każdej permutacji.
Wstępnie daje to 444 prawdopodobnych układów.
W treści podane są warunki, jakie spełniają propozycje podane przez wszystkich chłopców i dziewczynki.
Program przyporządkowuje te warunki do wszystkich możliwych propozycji.
Wstępnie redukuje je do 76 dla chłopców i 12 dla dziewczynek.
Następnie program redukuje możliwości przez dodanie warunku z ostatniego zdania dozorcy i stosuje je dla grup 4, 5 i 6 osobowych.
(zakładamy, że są co najmniej 2 dziewczynki i 2 chłopców – żeby było szybciej :>).
Okazuje się że nie ma rozwiązania dla więcej niż 2 dziewczynek w grupach 4, 5 i 6 osobowych.
Więc do dziewczynek dodajemy 2 i więcej chłopców.
Program znajduje kilka grup 5 osobowych i żadnej 4 i 6 osobowej.
W każdej grupie z 2 dziewczynkami i 3 chłopcami zawsze wygrywa chłopiec opisując prawidłowo 4 zwierzaki.
Nie wiem, czy mi się będzie chciało całe rozwiązanie wypisywać, więc naszkicuję:
Wystarczy, że będziemy rozpoznawać po jednym reprezentancie każdej pary, więc nazywamy tych reprezentantów \(\displaystyle{ a,b,c,d}\). Zgadnięcie odbywa się w dwóch krokach:
1. Ustalenie gatunków poszczególnych reprezentantów - to jest permutacja zbioru \(\displaystyle{ \{a,b,c,d\}}\)
2. Ustalenie płci reprezentanta - kładziemy \(\displaystyle{ 1}\) dla samic \(\displaystyle{ -1}\) dla samców.
Permutacji odpowiada macierz \(\displaystyle{ 4\times 4}\) mająca w każdym wierszu w każdej kolumnie po jednej jedynce, a na pozostałych miejscach zera.
Rozważając macierze takie, że w każdym wierszu i każdej kolumnie jest jeden niezerowy wyraz i jest to \(\displaystyle{ 1}\) lub \(\displaystyle{ -1}\) mamy zgrabną reprezentację dzieci macierzami.
Na przykład macierz: \(\displaystyle{ \begin{pmatrix}0&-1&0&0\\-1&0&0&0\\0&0&1&0\\0&0&0&-1\end{pmatrix}}\) działając na wektorze \(\displaystyle{ \begin{pmatrix}a\\b\\c\\d\end{pmatrix}}\) daje \(\displaystyle{ \begin{pmatrix}-b\\-a\\c\\-d\end{pmatrix}}\)
co interpretujemy tak, że w przypadku ai b ta macierz nie zgaduje ani gatunku, ani płci, w przypadku c zgaduje i gatunek i płeć a w przypadku d tylko gatunek. Oznaczmy grupe takich macierzy \(\displaystyle{ M}\).
Jeśli teraz macierz dowolnego dziecka oznaczymy \(\displaystyle{ C_*}\) dowolnej dziewczynki \(\displaystyle{ G_*}\), a chłopca \(\displaystyle{ B_*}\), to treść zagadki daje następujące reguły:
\(\displaystyle{ C(-x)=-C(x)}\) (czyli rzeczywiście są to te macierze \(\displaystyle{ 4\times 4}\) powyżej, a nie dowolne elementy \(\displaystyle{ S_8}\))
\(\displaystyle{ [C_1,C_2]=-1}\) (czyli macierze odpowiadające różnym dzieciom są antyprzemienne)
\(\displaystyle{ B^2=1}\) (chłopcy są rzedu 2)
\(\displaystyle{ G^2=-1}\) (dziewczynki są rzędu 4)
Stąd już niedaleko do rozwiązania. Dopiszę w wolnej chwili.
Przy okazji. Zagadka o trzech bóstwach jest nieporównywalnie trudniejsza. W zagadce o ZOO jedyny kłopot, to przebrnięcie przez treść. Dalej to automat. W zagadce o bóstwach treść jest prosta, za to rozwiązanie zawiera fantastycznie sprytny trik - ten z ustaleniem, że ze jedno z bóstw nie jest Losem. Zagadka o ZOO to zwykłe zadanko z algebry na poziomie pracy domowej - podobne zadania rozwiązuje się na kursie topologii algebraicznej.
xiikzodz, skoro znasz też zagadkę o trzech bóstwach, to pewnie też czytujesz Świat Matematyki i zapewne wiesz, że autorzy gazety prosili o jakiekolwiek rozwiązanie tego problemu, aby mogli później spróbować ułożyć jak najprostsze rozwiązanie zadania.
Myślę, że dobrze by było, gdybyś się z nimi skontaktował i przesłał swój sposób rozwiązania:
Dopiszę nieco więcej z tego rozwiązania. Niestety nie mam pomysłu, jak to zapisać przystępnie, mimo, że techniki, które użyję są bardzo proste. Może ktoś przetłumaczy na ludzki...
Pamiętamy grupę M, macierzy \(\displaystyle{ 4\times 4}\) o tej własności, że w każdym wierszu i w każdej kolumnie jest dokładnie jeden niezerowy element równy \(\displaystyle{ \pm 1}\).
Tę grupę łatwo zrozumieć. Mamy diagram dokładny (z dokładnością do izomorfizmu grup): \(\displaystyle{ \begin{array}{ccccc}Z_2^4&\longrightarrow&M&\stackrel{\pi}{\longrightarrow}&S_4\end{array}}\)
Dokładniej \(\displaystyle{ Z_2^4}\) to podgrupa w macierzach składająca się z macierzy diagonalnyc mających \(\displaystyle{ \pm 1}\) na przekątnej, zaś \(\displaystyle{ \pi}\) polega na zredukowaniu współczynników macierzy modulo 2.
Zauważmy, że dzieci siedzą w pogrupie \(\displaystyle{ C}\) grupy \(\displaystyle{ M}\), którą widać w poniższym diagramie:
gdzie strzałki w górę to włożenia stosowne, zaś \(\displaystyle{ Z_2\times Z_2}\) to podgrupa w permutacjach zbioru \(\displaystyle{ a,b,c,d}\) generowana symetriami kwadratu \(\displaystyle{ a,b,c,d}\) wzdłuż przekątnych.
Tak naprawdę wiersze są rozszczepialne (mamy oczywiste włożenie macierzy po prawej w macierze po środku), więc w szczególności \(\displaystyle{ C=Z_2^4\ltimes (Z_2\times Z_2)}\) Gdzie działanie grupy Kleina na macierzy \(\displaystyle{ \mbox{diag}(a,b,c,d)}\) polega na zastosowaniu symetrii środkowej lub względem jednej z przekątnych kwadratu o wierzchołkach \(\displaystyle{ a,b,c,d}\).
Przekładając to na ludzki każde dziecko to macierz postaci \(\displaystyle{ A\cdot B}\), gdzie \(\displaystyle{ A}\) to macierz diagonalna z \(\displaystyle{ \pm 1}\) na przekątnej zaś \(\displaystyle{ B}\) to macierz permutacji rzędu \(\displaystyle{ 2}\). Co więcej chłopcy są rzutowaniami na współrzędne tej sumy półprostej.
Ta ostatnia grupa jest już mała. Z maksymalności układu wspomnianego w zagadce ławto otrzymujemy, że chłopców może być co najwyżej trzech, bo iloczyn chłopców odwiedzających ZOO musi być dziewczynką. Wszystkich możliwych chłopców jest 19, więc wszystko łatwo na piechote posprawdzać... To powyżej to w zasadzie rozwiązanie zagadki - dysponując stosownym językiem można je w kilku linijkach zapisać.
Gdyby kogoś interesował argument, to wypiszę ogólną postać chłopca i ogólną postać dziewczynki.
Chłopców można podzielić na 3 grupy:
\(\displaystyle{ B_0}\) Macierz jednostkowa. \(\displaystyle{ B_1}\) Macierze diagonalne mające na przekątnej \(\displaystyle{ \pm 1}\) i przynajmniej jeden różny od \(\displaystyle{ 1}\). \(\displaystyle{ B_2}\) Macierze: \(\displaystyle{ \begin{pmatrix}
1&0&0&0\\
0&1&0&0\\
0&0&0&1\\
0&0&1&0\\
\end{pmatrix}}\), \(\displaystyle{ \begin{pmatrix}
0&1&0&0\\
1&0&0&0\\
0&0&1&0\\
0&0&0&1\\
\end{pmatrix}}\), \(\displaystyle{ \begin{pmatrix}
0&1&0&0\\
1&0&0&0\\
0&0&0&1\\
0&0&1&0\\
\end{pmatrix}}\)
Każda dziewczynka natiomiast jest iloczynem elemntu z \(\displaystyle{ B_1}\) przez element z \(\displaystyle{ B_2}\).
Nie wiem, czy to trzy bóstwa czy zagadka Eddingtona jest trudniejsza, ale chyba wystarczy znać się na macierzach, żeby to zadziałało jak kładka wiodąca na drugi brzeg rzeki. Bardziej mi to podchodziło pod udowodnienie stwierdzenia niż pod zagadkę, ale niech. Nie można czegoś ustanawiać najtrudniejszą zagadką wszech czasów, tak jak to Amerykanie mają w zwyczaju czynić wszystko "naj-", kiedy sami nie potrafią tego ogarnąć lub myślą, że są ostatnimi, którzy nie potrafiliby temu czemuś sprostać. Powaga żadnego towarzystwa filozoficznego nie usprawiedliwia beznadziejności tego stwierdzenia. A po n-te to nie jest filozofia, tylko matematyka!
