Przykładowe zadania

Trójwymiarowa szachownica
Pokaż rozwiązanie
Pokaż odpowiedź

Mamy klatkę przestrzenną, która jest trójwymiarową szachownica. Zwykła szachownica ma 82 = 64 pól kwadratowych, szachownica przestrzenna ma 83 = 512 "klatek".

Tematem zadania jest umieszczenie 64 wież w 64 klatkach spośród 512 tak, żeby żadna wieża nie biła innej. Ruch wieży jest taki sam jak na normalnej szachownicy ale dodatkowo w dodatkowej osi (góra-dół). Wieże umieść tak aby niemożliwe było umieszczenie 65-ej wieży bez narażenia jej na bicie ze strony ustawionych wież.

W każdej warstwie można ustawić 8 wież. Z tego wynika, że w ośmiu warstwach sześcianu można maksymalnie ułożyć 64 wieże tak, żeby żadne dwie się nie atakowały. Dodatkowo na każdej warstwie wieża musi być w innym miejscu.

Poniższy rzut przedstawia przykładowe rozmieszczenie figur, liczba napisana na polu wskazuje warstwę na której jest figura z tego pola.

Odpowiedź znajduje się w rozwiazaniu.
Zasięg konia w 3 ruchach
Pokaż rozwiązanie
Pokaż odpowiedź

Ustawiamy skoczka w rogu szachownicy 3x3 tak jak na obrazku. Jak dużo różnych pól jest w stanie odwiedzić skoczek w 3 ruchach.

Źródło Poziom trudności: Łatwe

Oznaczamy pola które są w zasięgu konia strzałką:

Z Podanych miejsc prowadzimy następne strzałki do pól na których jeszcze nie był skoczek:

Powtarzamy poprzedni krok i sprawdzamy do ilu pól są strzłki.

Odp: Koń w 3 ruchach odwiedzi 7 pól.
Maksymalna ilość wież
Pokaż rozwiązanie
Pokaż odpowiedź

Znając zasady poruszania się wieży po szachownicy, oblicz ile maksymalnie wież może być równocześnie na planszy żeby żadna z nich się nie atakowała.

Źródło Poziom trudności: Łatwe

Wiedząc, że wieża może poruszać się w pionie i poziomie zauważamy, że w każdym rzędzie i kolumnie może być maksymalnie jedna wieża. Ustawiając figury po przekątnej ominiemy obszar zbicia.

Odp: Na szachownicy może być równocześnie ustawione maksymalnie 8 wież by spełniały temat zadania.
Kolorowanie szachownicy
Pokaż rozwiązanie
Pokaż odpowiedź

Dana jest szachownica 8x8, której pola pokolorowane są w tradycyjny sposób. W jednym ruchu zmieniamy kolory pól w wybranym wierszu lub kolumnie: czarne kola zmieniają kolor na biały, a białe na czarny. Udowodnij, że nie istnieje taka liczba ruchów która doprowadziłaby do stanu w którym szachownica ma tylko jedno pole czarne.

Niech a oznacza liczbę pól czarnych w ustalonym wierszu lub kolumnie. Wówczas po wykonaniu ruchu liczba pól czarnych w tym wierszu (lub kolumnie) wynosi 8-a. Wobec tego po ruchu nie zmienia się parzystość liczby pól czarnych na szachownicy. Nie jest możliwe doprowadzenie do tylko jednego pola czarnego z 32.

Odp: Dowód znajduje się w zakładce "Rozwiązanie" zadania.
Liczby pierwsze na szachownicy
Pokaż rozwiązanie
Pokaż odpowiedź

Na każdym polu szachownicy 10x10 napisano jedną z liczb 1,2, ... ,10. Okazało się, że każde dwie liczby napisane na polach mających wspólny bok lub wspólny wierzchołek są względnie pierwsze. Wykaż, że pewna liczba występuje na szachownicy co najmniej 17 razy.

Daną szachownice 10x10 dzielimy na 25 kwadratów K1, K2, ... , K25 o wymiarach 2x2.

Liczby pierwsze względem siebie to takie które nie mają wspólnego dzielnika. Zaznaczamy na utworzonym kwadracie Ki, podane zależności.

W kwadracie umieszczamy co najwyżej jedną liczbę parzystą i jedną liczbę podzielną przez 3. Zostają nam dwa wolne miejsca i 3 możliwe liczby do rozstawienia - {1,5,7}. Wiedząc, że na szachownicy jest 25 kwadratów z dwoma wolnymi miejscami i 3 liczby do rozstawienia zauważamy, że przynajmniej jednej z nich musi powtarzać się przynajmniej 17 razy, ponieważ: 50/3 < 17

Zadanie o ziarnkach pszenicy
Pokaż rozwiązanie
Pokaż odpowiedź

Według legendy, mędrzec który wynalazł szachy tak zachwycił grą swojego władcę, że mógł sobie wybrać nagrodę. Ten niemyśląc długo poprosił o liczbę ziaren pszenicy, którą wyznaczy szachownica w następujący sposób:

Na pierwszym polu położono 1 ziarno i na każdym kolejnym polu podwajając liczbę z poprzedniego. Oblicz ile ziaren pszenicy był winny władca swojemu poddanemu, jeżeli szachownica ma 64 pola.

Źródło Poziom trudności: Łatwe

Sumę ziaren na szachownicy możemy wyrazić wzorem na ciąg geometryczny. $$ S_n = 1 \cdot {1-2^{64} \over 1-2} = {-18\,446\,744\,073\,709\,551\,615 \over -1} = $$ $$ = 18\,446\,744\,073\,709\,551\,615 $$

Aby zgromadzić taką ilość pszenicy królewski spichlerz o wysokości 4 i szerokości 10 metrów, musiałby mieć długość aż 300 milionów kilometrów.

Odp: Ilość wszystkich ziaren to \(18\,446\,744\,073\,709\,551\,615\).
9 wież
Pokaż rozwiązanie
Pokaż odpowiedź

Na szachownicy 9x9 ustawiono 9 wież w taki sposób, że żadne dwie figury się nie atakują. Następnie każdą wieżę przestawiono na inne pole ruchem skoczka. Wykaż, że po tym ruchu będzie przynajmniej jedna para wież które się będą atakować.

Każde pole na którym stoi wieża możemy zapisać jako dwie współrzędne (x,y), gdzie x jest numerem wiersza a y kolumny. Kluczową obserwacją do rozwiązania tego zadania jest zauważenie, że suma współrzędnych 9 nie bijących się wież będzie zawsze równa 90.

Przykładowe możliwe ruchy wież

Przestawienie wieży ruchem skoczka wpłynie na sumę współrzędnych w następujący sposób: ±1 lub ±3. Co przy nieparzystej ilości wież wskazuje na konieczność zmiany sumy współrzędnych. Wobec tego po przestawieniu wszystkich wież pewne dwie będą się biły.

Odp: Dowód znajduje się w zakładce "Rozwiązanie" zadania.
Iloczyn wierszów i kolumn
Pokaż rozwiązanie
Pokaż odpowiedź

W każde pole tablicy o wymiarach 25x25 wpisano liczbę 1 lub -1. Następnie dla każdego wiersza i każdej kolumny obliczono iloczyn wszystkich liczb stojących w danym wierszu lub danej kolumnie. Wykaż, że suma 50 uzyskanych iloczynów jest różna od 0.

Niech ai oznacza iloczyn liczb stojących w i-tym wierszu, natomiast niech bj będzie iloczynem liczb stojących w j-tej kolumnie.

Przyjmijmy, że dokładnie n spośród a1,a2, ...,a25 jest równych -1. Wtedy iloczyn wszystkich liczb z tablicy jest równy (-1)n.

Teraz udowodnimy problem metodą negacji. Przypuśćmy, że suma wszystkich 50 iloczynów jest rowna 0. Wtedy dokładnie 25-n liczb spośród b1,b2, ...,b25 równa się -1. To z kolei oznacza, że iloczyn wszystkich liczb stojących w tablicy wynosi (-1)25-n.

Otrzymaliśmy sprzeczność, ponieważ liczby n i 25-n są różnej parzystości (wynika z tego że suma tych liczb jest nieparzyste - 25).

Odp: Dowód znajduje się w zakładce "Rozwiązanie" zadania.
Zadanie z prawdopodobieństwa
Pokaż rozwiązanie
Pokaż odpowiedź

Grasz rozgrywkę szachową z doświadczonym przeciwnikiem. W każdej grze masz 75% szany, że gra zakończy się remisem. W pozostałych grach jest \({2 \over 3}\) szansy, że wygrasz i \({1 \over 3}\), że przegrasz.

Pierwszy zawodnik który wygra dwie gry z rzędu jest nazywany zwycięzcą. Jakie jest prawdopodobieństwo, że to ty wygrasz rozgrywkę?

Źródło Poziom trudności: Trudne
Obliczamy prawdopodobieństwo wygranej jednej partii: $$ P(wygrana) = {1 \over 4} \cdot {2 \over 3} = {1 \over 6} $$ Obliczamy prawdopodobieństwo przegrania jednej partii: $$ P(przegrana) = {1 \over 4} \cdot {1 \over 3} = {1 \over 12} $$ W zadaniu trzeba wygrać 2 razy z rzędu. Ustalamy 3 zmienne:
d - prawdopodobieństwo wygranej rozgrywki, jeżeli poprzednia gra była remisem
w - prawdopodobieństwo wygranej rozgrywki, jeżeli poprzednia gra była wygraną
l - prawdopodobieństwo wygranej rozgrywki, jeżeli poprzednia gra była przegraną
Interesuje nas obliczenie zdarzenia A ponieważ "grę 0" można uznać za remis. $$ d = {3 \over 4}\cdot d + {1 \over 6} \cdot w + {1 \over 12} \cdot l $$ Jeżeli poprzednia gra została wygrana: $$ w = {3 \over 4}\cdot d + {1 \over 6} + {1 \over 12} \cdot l $$ Jeżeli poprzednia gra była przegrana: $$ l = {3 \over 4}\cdot d + {1 \over 6} \cdot w + {1 \over 12} \cdot (0) $$ Ponieważ jest to układ równań możemy podstawić trzeci wzór do drugiego: $$ w = {3 \over 4}\cdot d + {1 \over 6} + {1 \over 12} \cdot ({3 \over 4}\cdot d + {1 \over 6} \cdot w) $$ $$ w = {117 \over 142}\cdot d + {12 \over 71} $$ Teraz podstawiamy trzeci wzór do pierwszego: $$ d = {3 \over 4}\cdot d + {1 \over 6} \cdot w + {1 \over 12} \cdot ({3 \over 4}\cdot d + {1 \over 6} \cdot w) $$ $$ d = {26 \over 27}\cdot w $$ Łączymy ze sobą te dwa równania: $$ d = {26 \over 27}\cdot ({117 \over 142}\cdot d + {12 \over 71}) $$ $$ d = {26 \over 33} $$
Odp: Prawdopodobieństwo, że wygrasz rozgrywkę wynosi około 78.8%.