[MIX][Kombinatoryka] MIX dla szachistów

[mol_ksiazkowy]

1. Na szachownicy \(\displaystyle{ n \times n}\) szerzy się epidemia. Na początku zarażone jest \(\displaystyle{ k}\) pól - ognisk epidemii. Jeżeli co najmniej dwóch z czterech sąsiadów niezarażonego pola jest zarażonych, to ono rownież staje się zarażone. Znależć najmniejsze \(\displaystyle{ k}\) takie, że zarażona może zostać cała szachownica.
2. Na szachownicy \(\displaystyle{ 9 \times 9}\) ustawiono 9 wież, tak że żadne dwie się nie atakują; następnie każdą z nich, zgodnie z ruchem konika szachowego, przesunięto na inne pole. Wykazać, że wtedy będą istnieć dwie wieże które się atakują.
3.(Musztari) Na środku każdego pola szachownicy ustawiono jeden pionek. Czy za pomocą trzynastu prostych można podzielić szachownicę na części, tak by co najwyżej jeden pionek znajdował się we wnętrzu każdej z nich ?
4. W pewnym turnieju rozgrywanym systemem "każdy z każdym" nie odnotowano żadnego remisu. Udowodnić, że jeśli pewnych dwóch graczy wygrało tyle samo partii, to istnieje trójka \(\displaystyle{ A, B, C}\) taka, że \(\displaystyle{ A}\) wygrał z \(\displaystyle{ B}\), \(\displaystyle{ B}\) wygrał z \(\displaystyle{ C}\) oraz \(\displaystyle{ C}\) wygrał z \(\displaystyle{ A}\)
5. W turnieju (z regułami jak z poprzednim zadaniu) każdy zawodnik, który każdego innego pokonał bezpośrednio lub pośrednio, otrzymał nagrodę. (Gracz \(\displaystyle{ A}\) pokonał gracza \(\displaystyle{ C}\) pośrednio, jeśli pokonał pokonał pewnego zawodnika \(\displaystyle{ B}\), który wygrał z \(\displaystyle{ C}\)). Dowieść, że jeśeli przyznana została tylko jedna nagroda, to otrzymał ją zawodnik, który wszystkich innych pokonał bezpośrednio.
6.a) Na szachownicy \(\displaystyle{ 8 \times 8}\) ustawiono 17 wież. Wykazać, że istnieje wśród nich trójka wież, które wzajemnie się nie atakują.
b) Czy jesli tekst "wzajemnie się nie atakują" zamienić na "wzajemnie się atakują" teza pozostanie prawdziwa ?
7. (Musztari) W turnieju "każdy z każdym" i bez remisów wzięło udział \(\displaystyle{ n}\) zawodników. \(\displaystyle{ j}\) ty z nich wygrał \(\displaystyle{ x_j}\) partii, a przegrał \(\displaystyle{ y_j}\) partii (dla \(\displaystyle{ j=1, ..., n}\)). Udowodnić, że \(\displaystyle{ x_1^2+ ...+x_n^2=y_1^2+ ...+y_n^2}\)
8. Na nieskończoną szachownicę o boku \(\displaystyle{ a}\) rzuca się żeton o średnicy \(\displaystyle{ 2r < a}\). Jakie jest prawdopodobieństwo, że żeton spadnie na obszar trzech pól?
9. Istnieje \(\displaystyle{ 3612}\) sposobów ustawienia dwóch króli (białego i czarnego) na szachownicy \(\displaystyle{ 8 \times 8}\), które są "poprawne szachowo". Na ile różnych sposobów można na tej szachownicy ustawić trzy białe króle (tj. żadne dwa z nich nie mogą stać na polach mających wspólny bok bądż naroże) ?
10. \(\displaystyle{ n}\) graczy uczestniczy w turnieju szachowym, w którym każdy z każdym rozgrywa dokładnie jedną partię. Po turnieju okazało się, że dla każdej czwórki uczestników istnieje wsród niej jeden, który z kazdym pozostałym miał inny wynik meczu (wygrana, przegrana, remis). Udowodnić, że \(\displaystyle{ 6 \leq n \leq 9}\)

11. (Musztari) Na szachownicy \(\displaystyle{ 25 \times 25}\) ustawiono pionki symetrycznie względem przekątnej i tak, że w każdym poziomym rzędzie jest dokładnie 5 pionków (nie więcej niż jeden pionek na każdym polu). Udowodnić, że przynajmniej jeden pionek stoi na przekątnej. Podać przykłąd takiego ustawienia pionków.
12. (Musztari) Czy można całą szachownicę obejść ruchem konika szachowego, wstępując do każdego pola tylko raz, jeśli chcemy zacząć i skończyć w dwóch przeciwległych polach narożnych szachownicy ?
13. (Musztari) W turnieju szachowym każdy z uczestników rezegrał po jednej partii ze wszystkimi pozostałymi. Wykaż, że uczestników turnieju można tak ponumerować, że żaden z nich nie przegrał partii z graczem o numerze większym o 1 od jego numeru.
14. (Musztari) Czarny słonik porusza się po czarnych polach szachownicy, przesuwając się w jednym ruchu o jedno pole po przekątnej. Jaka jest najmniejsza liczba ruchów potrzebna do obejścia wszystkich czarnych pól szachownicy o wymiarach \(\displaystyle{ 8 \times 8}\) ?
15. Dać przykład ścieżki hetmana, która zaczyna się na c3 a kończy na f6. Hetman ma wykonać pewną ilość posunięć, tak by łamana uzyskana z połączenia środków kolejnych pól, po których się on poruszał pokryła całą szachownicę (tj. przecięła każde jej pole)
Uwaga: przez każde pole należy przejść dokładnie jeden raz!
16. (M. Gardner) Ustawić 20 hetmanów na szachownicy \(\displaystyle{ 8 \times 8}\) w taki sposób, aby każdy hetman mógł zbić (wykonując jeden ruch) dokładnie cztery z pozostałych 19 hetmanów
17. Na szachownicy \(\displaystyle{ 100 \times 100}\) stoi 20 figur (mogą być szachowe, ale niekoniecznie). Wiadomo, że każda z figur stojąc na dowolnym polu, bije nie więcej niż 20 pól. Udowodnić, że figury te można przestawić tak, aby wzajemnie sie nie biły.
18. Na szachownicy w sposób losowy ustawiono wieżę i gońca. Jakie jest prawdopodobeństwo tego że wieża może zbić gońca lub że goniec może zbić wieżę ?
19. Dana jest szachownica \(\displaystyle{ n \times n}\), gdzie \(\displaystyle{ n}\) jest nieparzyste. Dwóch graczy umieszcza na przemian na tej szachownicy klocki o wymiarach \(\displaystyle{ 1 \times 2}\). Klocki nie mogą na siebie nachodzić. Przegrywa ten, kto pierwszy nie będzie mógł umieścić na szachownicy klocka. Udowodnić, że drugi gracz zawsze wygra.
20. Udowodnić, że maksymalna liczba wież, które można rozstawić na szachownicy \(\displaystyle{ n \times n}\) tak, aby każda z nich była bita przez co najwyżej jedną z pozostałych, wynosi \(\displaystyle{ \left\lfloor \frac{4n}{3} \right\rfloor}\). Podać przykład takiego ustawienia dla \(\displaystyle{ n=8}\)

21. rozwiązane przez Lorek
Każde pole szachownicy \(\displaystyle{ n \times n}\) pomalowano na czarno lub biało. Okazało się, że żadne cztery pola, których środki są wierzchołkami prostokąta o bokach równoległych do krawędzi szachownicy, nie zostały pomalowane tym samym kolorem. Dla jakiej największej wartości \(\displaystyle{ n}\) jest to możliwe ?
22*. Na pewnym polu nieskończonej szachownicy stoją cztery pionki. W jednym kroku usuwamy pionek z wybranego pola \(\displaystyle{ P}\), stawiając jednocześnie po jednym pionku na dwa pola, które sąsiadują z góry i z prawej strony z polem \(\displaystyle{ P}\). Rozstrzygnąć, czy można po skończonej liczbie kroków doprowadzić do sytuacji, w której na każdym polu stoi co najwyżej jeden pionek.
23. Czy przekątna szachownicy \(\displaystyle{ m \times n}\) przecina dokładnie \(\displaystyle{ m+n - nwd(m,n)}\) jej pól ? (jeśli tak: znaleźć dowód; jeśli nie: kontrprzykład)
24. Ustawić na szachownicy \(\displaystyle{ 8 \times 8}\) wszystkie figury danego koloru (tj. króla, hetmana, dwa skoczki, dwa gońce i dwie wieże) w taki sposób, aby 60 pól było pod ich kontrolą (tj. tak by żadna z figur nie kontrolowała pól: c6, e1, f1, f3)
Uwaga: zakłada się, iż figura kontroluje też pole na którym stoi
25. rozwiązane przez Lorek
Na polu c1 stoi hetman. Gracze na przemian wykonują nim ruch, przesuwając go o dowolną liczbę pól w prawo, do góry albo po przekątnej w prawo i do góry. Wygrywa ten, który postawi hetmana na h8. Kto ma strategię wygrywającą i jaką ?

26. Dane są: jeden klocek \(\displaystyle{ 1 \times 1}\) i 21 klocków \(\displaystyle{ 3 \times 1}\). Uzasadnić, że tymi klockami pożna pokryć szachownicę \(\displaystyle{ 8 \times 8}\) (klocki \(\displaystyle{ 3 \times 1}\) można kłaść pionowo bądź poziomo) wtedy i tylko wtedy, gdy klocek \(\displaystyle{ 1 \times 1}\) położony jest na jedym z pól: c3, c6, f3, f6
Uwaga: na diagramie przykładowe ustawienie z małym klockiem na c3

27. Ile jest wszystkich układów z dwoma różnokolorowymi królami i jednym pionem, które są "szachowo poprawne" (tj. zielone pola są zabronione dla piona, a króle stoją tak, jak wolno im w szachach) ?

28. Figura zwana \(\displaystyle{ (m,n)}\) koniem w każdym swym ruchu przemieszcza sie o \(\displaystyle{ m}\) pól poziomo i \(\displaystyle{ n}\) pól pionowo - lub odwrotnie. (a więc \(\displaystyle{ (2,1)}\) koń jest zwykłym konikiem szachowym). W tym szachowym zoo ważne są m. in:
Antylopa (tj. \(\displaystyle{ (3, 4)}\) koń)
Zebra (tj. \(\displaystyle{ (2, 3)}\) koń)
Żyrafa (tj. \(\displaystyle{ (1, 4)}\) koń)
Wielbłąd (tj. \(\displaystyle{ (1, 3)}\) koń)
Podać (o ile jest to możliwe) ścieżkę każdej z tych figur z pola a1 do pola h8. Na diagramie poniżej ukazana została taka ścieżka dla "zwykłego" konia.

29. Problem: Rozmieścić \(\displaystyle{ n}\) hetmanów na szachownicy \(\displaystyle{ n \times n}\) w taki sposób, aby jak najwięcej pól nie było pod kontrolą żadnego z nich. Zaproponować rozwiązanie tego problemu dla \(\displaystyle{ n= 8}\) (im większe \(\displaystyle{ p}\) - tym lepiej)
Uwaga: Na diagramie poniżej przykład ustawienia gdzie \(\displaystyle{ p=6}\); ale nie jest to optymalna wartość \(\displaystyle{ p}\)


30**. (Musztari) Każde pole szachownicy zostało pomalowane na jeden z dwóch kolorów: niebieski lub czerwony. Wykaż, że przynajmniej jeden z tych kolorów ma tę własność, że hetman może obejść wszystkie pola pomalowane tym kolorem (na pola pomalowane tym kolorem może wstępować dowolną liczbę razy, na pola pomalowane drugim kolorem nie może wstępować, ale może przez nie skakać).
np. (diagram) pole h6 stanowi "wysepkę" w strukturze niebieskich pól, ale czerwone pola są "przejezdne".


31. Zadanie Guariniego (XVI wiek) Zamienić koniki miejscami, operując nimi jedynie w obrębie kwadratu \(\displaystyle{ 3 \times 3}\)
Uwaga: Kolejne ruchy należy podać używając zapisu np. 1. Sa1 - c2 (tj. skoczek wykonał ruch z a1 na c2) itd.

32. Arlekin jest figurą pseudoszachową która porusza się tak jak skoczek i król. Na ile sposobów można na szachownicy \(\displaystyle{ 8 \times 8}\) ustawić dwa arlekiny tak, aby się nie biły ?
Na diagramie poniżej pokazano jakie ruchy może wykonać arlekin z pola e4

33. W pewnej partii doszło do sytuacji pokazanej tu na diagramie; kto wykonał ostatnie posunięcie: białe czy czarne (i dlaczego) ?
.
34. rozwiązane przez HubSona
(Extra) Na szachownicy o rozmiarach \(\displaystyle{ 4 \times 5}\) stoją cztery białe gońce i cztery czarne. Należy zamienić je miejscami tak, by w trakcie przemieszczania ani razu żaden goniec nie atakował gońca przeciwnego koloru. Gońce ruszaja się na zmianę: tj. raz biały a raz czarny.

35.(HuBson)Mamy do dyspozycji szachownicę o wymiarach \(\displaystyle{ n \times n}\) i
\(\displaystyle{ k}\) hetmanów, \(\displaystyle{ k \le n^{2}}\) wykazać że nie da się ustawić tak tych hetmanów by
każdy z nich atakował dokładnie \(\displaystyle{ a}\) pozostałych z tym że \(\displaystyle{ a \in (4;8\rangle}\)[/quote]

[Mszak]

zad. 1

Ukryta treść:    

Łatwo zauważyć, że Obwód obszaru zarażonego wraz z wzrostem epidemii nie zmienia się. Czyli aby zająć całą szachownicę, to \(\displaystyle{ k=n}\) i pola te ustawimy po przekątnej szachownicy.

[Lorek]

25.:    

Gracz, który zaczyna ma strategię wygrywającą. Przykładowa strategia:

1. Gracz 1 przesuwa się na pole \(\displaystyle{ c5}\).
2a. Jeśli gracz 2 przesunie się na jedno z pól \(\displaystyle{ e5,h5,c8,f8}\), to gracz 1 przesuwa się na pole \(\displaystyle{ h8}\) i wygrywa.
2b. Jeśli gracz 2 przesunie się na jedno z pól \(\displaystyle{ d5,f5,c7,e7}\), to to gracz 1 przesuwa się na pole \(\displaystyle{ f7}\).
2c. Jeśli gracz 2 przesunie się na jedno z pól \(\displaystyle{ g5,c6,d6}\), to to gracz 1 przesuwa się na pole \(\displaystyle{ g6}\).
3. Jeśli gra się nie zakończyła, to gracz 2 jest na polu \(\displaystyle{ g6}\) lub \(\displaystyle{ f7}\). Obojętnie jaki ruch wykona, znajdzie się na przekątnej lub w ostatnim wierszu/kolumnie, ale nie na polu \(\displaystyle{ h8}\). Wtedy gracz 1 przesuwa się na pole \(\displaystyle{ h8}\) i wygrywa.


Ogólną sytuację można zilustrować rysunkiem:

Gracz startujący z pól ciemnozielonych wygrywa (może od razu przejść na \(\displaystyle{ h8}\)).
Gracz startujący z pól jasnozielonych jest w stanie dostać się na któreś z niebieskich pól. Gracz startujący z pól niebieskich musi ruszyć się na któreś z pól zielonych, dając tym samym przeciwnikowi wygraną lub możliwość przesunięcia się na kolejne niebieskie pole bliższe narożnikowi \(\displaystyle{ h8}\).

Edit:

21:    

Dla \(\displaystyle{ n=5}\): mamy 5 kolumn, w każdej z kolumn pewien kolor występuje przynajmniej 3 razy, powiedzmy, że ma "przewagę" w tej kolumnie. Kolumn jest 5, a kolorów 2, zatem istnieje kolor mający przewagę przynajmniej w 3 kolumnach. Wybierzmy te kolumny i załóżmy, że w każdej z nich są 3 pola koloru przeważającego.

Łatwo zauważyć, że obojętnie jak rozmieszczone są kolory, to musimy otrzymać prostokąt o "jednokolorowych wierzchołkach" - albo dwie pierwsze kolumny mają co najmniej dwa wspólne wiersze o tym samym kolorze, albo jak mają tylko jeden taki wiersz, to trzecia kolumna ma 2 wspólne wiersze (pod względem koloru) z którąś z dwóch pierwszych kolumn. Oczywiście jak w którejś kolumnie są więcej niż 3 pola koloru przeważającego, to tym bardziej jest to spełnione.

Zatem dla \(\displaystyle{ n\ge 5}\) się nie da.
Przykładowe ustawienie dla \(\displaystyle{ n=4:}\)

\(\displaystyle{ \begin{array}{cccc}{b&b&b&c\\b&c&c&c\\c&c&b&b\\c&b&c&b\end{array}}\)

(chyba jest ok)

[Swistak]

O nazwie tematu "Chess":    

OMGOMGOMGOMG TEMATY NIE MOGĄ BYĆ PO ANGIELSKU !!
OBOWIĄZUJĄCYM JĘZYKIEM FORUM MATEMATYKA.PL JEST JĘZYK POLSKI!!

Według Ciebie naprawdę "Teoria liczb. liczby pierwsze, liczby naturalne" wygląda lepiej od "The best of: Teoria liczb"? Przecież to jakaś paranoja, aby nie dopuszczać zwrotu "The best of:" !
Pozdrawiam
Swistak

Obowiązującym na forum językiem jest język polski.
Pozdrawiam

A żeby nie było takiego spamu no to

26:    

Najpierw pomalować co trzeci diagonal w tę stronę "" i policzyć, którego koloru jest o 1 za dużo, a potem w drugą stroną "/", policzyć to samo i wziąć przecięcie i wyjdą te 4 pola.

7:    

\(\displaystyle{ x_i+y_i=n-1}\) i \(\displaystyle{ \sum x_i = \frac{n(n-1)}{2}}\), co chyba kończyło to zadanie

[JakimPL]

23:    

Tak. Podzielmy szachownicę \(\displaystyle{ m-1}\) prostymi, a zerową i ostatnią niech będzie krawędź szachownicy. Dla każdego kroku od \(\displaystyle{ 1}\) do \(\displaystyle{ m}\) wyznaczymy prostokąt o polu równym liczbie przeciętych pól. Punkty przecięcia prostych z przekątnymi to nic innego jak punkty o współrzędnych \(\displaystyle{ \left(k,\frac{n}{m} \cdot k\right)}\), przy czym zerowy punkt to oczywiście \(\displaystyle{ (0,0)}\). Zakreślany prostokąt w każdym kroku wyznaczony jest jednoznacznie przez punkty:

\(\displaystyle{ \left(k-1,\left\lfloor\frac{n}{m} \cdot (k-1) \right\rfloor\right)}\) oraz \(\displaystyle{ \left(k,\left\lceil\frac{n}{m} \cdot k \right\rceil\right)}\). Pole będzie zatem różnicą:

\(\displaystyle{ \left\lceil\frac{n}{m} \cdot k \right\rceil-\left\lfloor\frac{n}{m} \cdot (k-1) \right\rfloor}\)

\(\displaystyle{ \sum_{k=1}^m \left(\left\lceil \frac{k n}{m}\right\rceil +\left\lceil \frac{n-k n}{m}\right\rceil\right)=n+m - {\rm NWD}(m,n)}\)

Dowód tej (albo podobnej) sumy chyba był w Matematyce konkretnej.

31:    

\(\displaystyle{ \begin{tabular}{lll}
1. & Sc2 & Sab1 \\
2. & Sb3 & Sa2 \\
3. & Sa3 & Sc1 \\
4. & Sa1 & Sc3 \\
5. & Sb1 & S3a2 \\
6. & Sc2 & Sb3 \\
7. & Sc3 & Sa1 \\
8. & Sa3 & Sc1 \end{tabular}}\)

33:    

Białe wykonały ostatni ruch, skoczki są ustawione "kolorowo-symetrycznie" (tj. oba są na tych samych kolorach, a więc ), a żadne inne figury nie mogły się ruszyć tak, by nie można było rozstrzygnąć o tym, kto wykonał ostatni ruch. Ruch pionkiem bądź skoczkiem znów na pole tego samego koloru wskazuje bezpośrednio na białych.

[HuBson]

33

Ukryta treść:    

Do zaistniałej sytuacji dojść nie mogło gdyż nie ma hetmana na szachownicy u białych a nie mógł on zostać zbity ani wyprowadzony bo pionki odległe od niego o jedno pole są nieruszane gońiec też nie mógł być wcześniej wyprowadzony zatem hetman nie miał się jak "wydostać" to też zadanie jest skopane

[JakimPL]

HuBson, Skoczki się poruszały, a gońce nie zostały wyprowadzone.

12:    

Staaare .

17:    

Coś odwrotnego do zasady szufladkowej, zadanie dosyć oczywiste.

28:    

Antylopa:
\(\displaystyle{ {\rm a1 \rightarrow d5/e4 \rightarrow h8}}\)
Zebra:
\(\displaystyle{ {\rm a1 \rightarrow d3 \rightarrow b6 \rightarrow e5 \rightarrow c7 \rightarrow f5 \rightarrow h8}}\)
Żyrafa:
\(\displaystyle{ {\rm a1 \rightarrow d6 \rightarrow h5 \rightarrow g1 \rightarrow c2 \rightarrow g3 \rightarrow f7 \rightarrow e3 \rightarrow e3 \rightarrow d7 \rightarrow h8}}\)
Wielbłąd:
\(\displaystyle{ {\rm a1 \rightarrow d2 \rightarrow e5 \rightarrow f8 \rightarrow g5 \rightarrow h8}}\)

32:    

Arlekin bije \(\displaystyle{ 16}\) pól i stoi na jednym. Jeżeli się znajduje w obszarze \(\displaystyle{ 4\times 4}\) na środku planszy, to można znaleźć dokładnie \(\displaystyle{ 64-17=47}\) miejsc, w których może stać drugi arlekin. Skoro pól centralnych jest \(\displaystyle{ 16}\), to mamy już \(\displaystyle{ 752}\) sposobów (póki co wyróżniamy figury). Dla pól z obrzeża centrum bez pól \(\displaystyle{ \rm b2}\) i symetrycznych mamy \(\displaystyle{ 15}\) niedostępnych pól, których jest \(\displaystyle{ 16}\), stąd mamy kolejne \(\displaystyle{ 784}\) sposoby. Z pól typu \(\displaystyle{ \rm b2}\) mamy \(\displaystyle{ 4(64 - 13)=204}\) sposobów, dla pól zewnętrznych nienależących do kwadratu \(\displaystyle{ 2\times 2}\) w rogu mamy \(\displaystyle{ 16(64-11)=848}\) możliwości; dodajemy do tego pozostałe \(\displaystyle{ 8(64 - 9)}\) oraz \(\displaystyle{ 4(64-6)}\) pozostałych sposobów. Jeżeli się nie pomyliłem i uwzględniłem wszystko, to otrzymamy \(\displaystyle{ 3260/2=1630}\) możliwości.

[mol_ksiazkowy]

ad 28

Ukryta treść:    

(tylko w uzupełnieniu diagram) wielbład nie zmienia koloru pól

ad 33

Ukryta treść:    

Do zaistniałej sytuacji dojść nie mogło gdyż nie ma hetmana na szachownicy u białych a nie mógł on zostać zbity ani wyprowadzony bo pionki odległe od niego o jedno pole są nieruszane gońiec też nie mógł być wcześniej wyprowadzony zatem hetman nie miał się jak "wydostać" to też zadanie jest skopane

A nawet i czarnego hetmana tez nie ma juz na szachownicy, hetmany musiały być zbite przez konie.

[porfirion]

Ważna uwaga: w szachach nie ma ani koni, ani koników... Są skoczki

[Panda]

W \(\displaystyle{ 19}\) dla pary \(\displaystyle{ (1,3)}\) twierdzenie chyba nie zachodzi.

[HuBson]

ad 28

Ukryta treść:    

(tylko w uzupełnieniu diagram) wielbład nie zmienia koloru pól

ad 33

Ukryta treść:    

Do zaistniałej sytuacji dojść nie mogło gdyż nie ma hetmana na szachownicy u białych a nie mógł on zostać zbity ani wyprowadzony bo pionki odległe od niego o jedno pole są nieruszane gońiec też nie mógł być wcześniej wyprowadzony zatem hetman nie miał się jak "wydostać" to też zadanie jest skopane

A nawet i czarnego hetmana tez nie ma juz na szachownicy, hetmany musiały być zbite przez konie.

Rzeczywiście sprytna uwaga co za nieudolni szachiści
Edit:
Teraz dopiero uświadomiłem sobie skąd wziął się cały ten temat...
czyżby to była mała spekulacja zadań do 64 OM (szachownica ma 64 pola)
bo autorzy zadań z OM często nawiązują do numeru edycji olimpiady pewnie będzie jeszcze trochę teorii liczb bo 64 jest kwadratem liczby naturalnej to pewnie dadzą jakieś zadanie na podzielność...
sprytne osoby są na tym forum

[Panda]

Jak najkrócej umiem, jak coś niezrozumiałe to proszę wołać.

2:    

Najpierw zauważmy, że figury się nie biją \(\displaystyle{ \Leftrightarrow}\) w każdym rzędzie i kolumnie stoi \(\displaystyle{ 1}\) figura.
Konik zawsze albo w pionie, albo w poziomie skacze do rzędu/kolumny o numerze o innej parzystości niż tego/tej, z której/ego skacze. Bez utraty ogólności załóżmy, że nieparzystą ilość razy miało to miejsce dla rzędów, a parzystą dla kolumn (innej opcji niż nieparzyste-parzyste nie ma, bo suma ilości to \(\displaystyle{ 9}\)). Na początku w każdym rzędzie stoi \(\displaystyle{ 1}\) wieża. Na początku różnica między ilością figur w nieparzystych a parzystych rzędach wynosi \(\displaystyle{ 1}\). Zmieniamy ją nieparzystą ilość razy, wykonując po kolei ruchy - każda zmiana to dodanie lub odjęcie \(\displaystyle{ 2}\). W efekcie dodamy inną ilość razy niż odejmiemy, czyli nie powrócimy do jedynki, co by było wymagane, aby zaszła własność.

4:    

Robimy z tego graf, krawędź skierowana to relacja wygrania, mamy tu graf turniejowy.
Założymy, że nie istnieje trójka \(\displaystyle{ (A,B,C); A \rightarrow B \rightarrow C \rightarrow A}\) (czyli cykl długości \(\displaystyle{ 3}\)) i pokażemy, że wtedy stopień wyjściowy każdego wierzchołka jest inny.

Najpierw lemat, że wtedy nie ma w naszym grafie w ogóle żadnych cykli.
Załóżmy nie wprost, że mamy jakieś cykle i weźmy najkrótszy z nich.
Niech \(\displaystyle{ A \rightarrow B \rightarrow C}\) będzie jego fragmentem. Nie jest prawdą że \(\displaystyle{ C \rightarrow A}\), więc \(\displaystyle{ A \rightarrow C}\), a to oznacza, że możemy skrócić nasz cykl o \(\displaystyle{ B}\), co jest sprzeczne z tym, ze jest najkrótszy.

Zatem nie ma cykli w naszym grafie. Czyli istnieje wierzchołek, z którego nie wychodzi żadna krawędź - gdyby nie istniał, moglibyśmy chodzić w nieskończoność, a to oznacza zatoczenie w końcu cyklu. Istnieje tylko jeden, bo od reszty odchodzą krawędzie do niego. Teraz możemy zrobić nowy graf przez wywalenie tego wierzchołka, tym samym obniżenie stopnia wychodzącego wszystkich innych wierzchołków o \(\displaystyle{ 1}\), co zachowa różnice między nimi. Tak można schodzić w nieskończoność, sukcesywnie pokazując, że kolejne odrzucane wierzchołki mają stopnie wychodzące inne niż pozostałe.
Tym samym, dowodzimy tezy (ew. rozpatrujemy jakąś małą ilość wierzcołków jeszcze).

5:    

Gdyby nie pokonał kogoś bezpośrednio, czyli ktoś pokonał jego, to by ten ktoś "podkradł" wszystkich pokonanych jemu, czyli też otrzymał nagrodę, co jest sprzeczne.

6:    

Z rozszerzonej zasady szufladkowej dirichleta, figury zajmują przynajmniej \(\displaystyle{ 3}\) rzędy i \(\displaystyle{ 3}\) kolumny. A w pewnym rzędzie są przynajmniej \(\displaystyle{ 3}\) figury. Wystarczy pokazać, że poza tym rzędem, figury są w przynajmniej \(\displaystyle{ 2}\) kolumnach. Jest tak, bo w przeciwnym razie ilość figur nie przekroczyłaby \(\displaystyle{ 15}\). To nam da, że jak weźmiemy pewne takie \(\displaystyle{ 2}\) figury z innego rzędu z różnych kolumn, to z szufladkowej, możemy z tego naszego rzędu dobrać trzecią, żeby było dobrze.

22:    

Żeby osiągnąć cel, musimy z pewnością \(\displaystyle{ 3}\) razy wykonać operację na startowym polu, potem \(\displaystyle{ 2}\) razy na tym wyżej i po prawej. W ten sposób \(\displaystyle{ 4}\) figury wylądują na polu odległym o \(\displaystyle{ 1}\) na północny-zachód. Zawsze tak będzie się robiło, bo otrzymana sytuacja jest analogiczna, i tym samym nigdy nie osiągniemy celu.

[mol_ksiazkowy]

12

Ukryta treść:    

Staaare

ale jare.... Odpowiedz: nie. Gdyby konik obszedł cała szachownice , to musiałby wykonac nieparzysta ilosc ruchów, tj. pola startowe i koncowe byłyby róznych kolorów

19

Ukryta treść:    

W 19 dla pary (1,3) twierdzenie chyba nie zachodzi.

ależ tak, gdyz był bład w tresci...

28

Ukryta treść:    

W uzupełnieniu diagram (Zebra jak jak koń w szesciu ruchach)

Ukryta treść:    

Teraz dopiero uświadomiłem sobie skąd wziął się cały ten temat...
czyżby to była mała spekulacja zadań do 64 OM (szachownica ma 64 pola)

ojej !

[Lorek]

11:    

Skoro pionki są ustawione symetrycznie to pod i nad przekątną jest ich tyle samo, czyli poza przekątną jest ich parzysta liczba. Wszystkich jest nieparzysta liczba, stąd jakieś muszą być na przekątnej.
Przykład rozmieszczenia: tworzymy bloki pionków \(\displaystyle{ 5\times 5}\) i ustawiamy na przekątnej.

i jeszcze parę pytań:
18. Normalna szachownica czy dowolna?
19. "drugi gracz zawsze wygra" czyli ma strategię zwycięską czy niezależnie od ruchów wygrywa?

[mol_ksiazkowy]

i jeszcze parę pytań:
18. Normalna szachownica czy dowolna?
19. "drugi gracz zawsze wygra" czyli ma strategię zwycięską czy niezależnie od ruchów wygrywa?

odp.
18. normalna
19. ma strategię