Delta mi!

Odp. Tak!
Liczbę  kolorujemy na kolor o numerze  Załóżmy, że  dla pewnych liczb nieujemnych  i przyjmijmy, że  Załóżmy, że  i   mają ten sam kolor. Niech  czyli  dla pewnej liczby całkowitej  Wówczas  dla pewnej liczby całkowitej  Zatem  więc  Ponieważ  więc liczba  ma w opisanym przez nas kolorowaniu inny kolor niż liczby  i 

Pokażemy, że nie istnieje żądane kolorowanie liczb całkowitych, więc w szczególności nie da się pokolorować liczb rzeczywistych. (Jest to bardzo szczególny przypadek twierdzenia van der Waerdena o kolorowaniu.)

Załóżmy, że pokolorowaliśmy liczby całkowite nieujemne i liczba   jest biała. Jedna z liczb  też musi być biała. Nazwijmy ją   Wówczas liczby  i   muszą być czarne. Zatem ich średnia  musi być biała. Dostaliśmy więc trzy białe liczby  co daje sprzeczność.

Uczeń na wycieczce spotyka się z  innymi uczniami, więc aby spotkać się ze wszystkimi kolegami ze szkoły, musi wziąć udział w przynajmniej  wycieczkach. Stąd liczba biletów wynosi co najmniej  więc minęło co najmniej  tygodni.

Najkrótsze drogi prowadzą na północ lub na wschód. Wszystkie są długości  gdyż każda ma łącznie  kratek na wschód i   na północ.

Każdą taką drogę można utożsamić z jej opisem – ciągiem zawierającym  znaków  oraz  znaków  kodującym, czy na kolejnym skrzyżowaniu należy iść na północ  czy na wschód  Najkrótszych dróg jest więc tyle, ile takich ciągów, czyli  bo na tyle sposobów można wybrać, na których  spośród wszystkich  miejsc ciągu ma być znak

Z zadania 1 wiemy, że liczba najkrótszych dróg „po kratkach” z lewego dolnego do prawego górnego rogu kwadratu  równa jest

Wyznaczmy tę samą liczbę inaczej. Każda z takich dróg musi przejść przez dokładnie jeden z   kolorowych punktów  z rysunku.  Liczba najkrótszych dróg z   do  przechodzących przez  jest iloczynem liczby najkrótszych dróg z   do  i liczby najkrótszych dróg z   do  czyli – z zadania 1 – równa jest

Stąd liczba wszystkich najkrótszych dróg z   do  równa jest

co kończy dowód na mocy początkowej obserwacji, że dróg tych jest

Uwaga. bo wybór elementów z równoważny jest odrzuceniu pozostałych elementów.

Punkt – kasjer dostał już banknotów po 10 zł i po 20 zł.

Zilustrujmy kolejkę jako pewną drogę o   krokach: w danym kroku idziemy w prawo, jeśli klient ma 10 zł, lub w górę, jeśli ma 20 zł. Aby kasjerowi nie zabrakło reszty, liczba wręczonych mu banknotów 20 zł nigdy nie może przekroczyć liczby banknotów 10 zł, które do tego momentu dostał. Innymi słowy, droga jest dobra, jeśli nie dotyka kolorowej prostej  z rysunku obok. Policzmy, ile jest złych dróg.

Niech dana zła droga pierwszy raz dotyka prostej  w punkcie  Jej część od punktu  do punktu  odbijmy symetrycznie względem prostej  uzyskując półodbicie złej drogi – nową drogę prowadzącą tylko w prawo lub w górę od punktu  do punktu  Każda zła droga ma inne półodbicie. Ponadto każda najkrótsza droga z   do  przecina prostą  więc jest półodbiciem pewnej złej drogi. Stąd złych dróg jest tyle, ile ich półodbić, czyli najkrótszych dróg z   do  a więc, na mocy zadania 1,

Wszystkich najkrótszych dróg z   do  jest  więc liczba dobrych dróg to

a prawdopodobieństwo, że kasjerowi nie zabraknie reszty, równe jest

Niech będzie grafem o wierzchołkach oznaczających wiersze i kolumny planszy. Krawędź pomiędzy wierszem a kolumną jest w wtedy i tylko wtedy, gdy punkt o współrzędnych jest zamalowany. Graf ma więc krawędzi. Jak wiadomo, jeśli graf o wierzchołkach nie ma cyklu, to ma co najwyżej krawędzi. Zatem zawiera cykl. Z definicji krawędzi w wynika, że będzie on parzystej długości i wyznaczone przez niego krawędzie to szukane punkty

Potraktujmy zaczernione kwadraty jako wierzchołki skończonego grafu; para wierzchołków jest połączona krawędzią grafu, gdy odpowiadające im kwadraty sąsiadują (mają wspólny bok). Zgodnie z treścią zadania, z każdego wierzchołka wychodzą dokładnie dwie krawędzie. Graf rozpada się zatem na rozłączne cykle – to znany fakt (i łatwy do wykazania: z dowolnego wierzchołka rozpoczynamy wędrówkę po krawędziach grafu, nie powtarzając żadnej krawędzi; musimy wrócić do punktu wyjścia; odrzucamy powstały cykl i powtarzamy postępowanie, do wyczerpania wszystkich krawędzi).

Każdy cykl ma długość parzystą. Aby to zobaczyć, wystarczy sobie wyobrazić, że (niezależnie od zaczernień rozważanych w zadaniu) cała płaszczyzna jest „w tle” pomalowana dwoma odcieniami, jak szachownica, a sąsiadujące kwadraty mają różne odcienie; zamknięcie cyklu wymaga parzystej liczby kroków.

Tak więc liczba czarnych kwadratów jest parzysta. Jasne, że nie może ona być równa 2 i że może być równa 4. Czy może być równa 6? Musiałby to być pojedynczy cykl; znalazłby się w nim czarny kwadrat narożny   sąsiadujący np. od wschodu i od północy z dwoma czarnymi kwadratami,  i   Kwadrat   różny od   i sąsiadujący z     nie może być zaczerniony (zamknąłby on cykl długości 4). Każda droga, łącząca  z   i omijająca kwadraty    wymaga zaczernienia więcej niż 3 kwadratów. Nie jest więc możliwe, by liczba czarnych kwadratów wyniosła 6.

Może to być wszelako każda większa liczba parzysta   Wystarczy wziąć prostokąt o wymiarach  i zaczernić wszystkie jego pola brzegowe. Jest ich dokładnie   i tworzą cykl o wymaganej własności.

Dostajemy odpowiedź: liczba czarnych kwadratów może być dowolną dodatnią liczbą parzystą z wyjątkiem 2 oraz 6.

Rozważamy pola brzegowe (przylegające co najmniej jednym bokiem do brzegu szachownicy). Zliczamy pary sąsiadujących pól brzegowych, mających różne kolory. Na starcie liczba takich par wynosi ; w stanie docelowym wynosi 0. Jeden ruch może zmniejszyć liczbę takich par co najwyżej o 4. Zatem liczba ruchów, po których plansza może stać się jednokolorowa, jest nie mniejsza niż

Pola narożne mają na starcie różne kolory, więc w którymś ruchu musimy użyć prostokąta, zawierającego jakieś pole narożne. Wszelako taki ruch zmniejszy rozważaną wielkość co najwyżej o 2. W takim razie  ruchów nie wystarczy do uzyskania żądanego celu, potrzeba co najmniej  ruchów.

Pozostaje zauważyć, że  ruchów faktycznie już wystarczy: w początkowych  ruchach zmieniamy kolory w co drugim wierszu, wszystkie kolumny stają się jednokolorowe (plansza „w zebrę”). W kolejnych  ruchach zmieniamy kolory w co drugiej kolumnie i gotowe.

Niech  oznacza liczbę wrogów -tego rycerza, którzy zasiadają z nim przy stole. W kroku 0 posadźmy wszystkich rycerzy przy pierwszym stole. Będziemy w kolejnych krokach przesadzać rycerzy, rozważając liczbę

Jeśli po wykonaniu kroku przy pierwszym stole pewien rycerz siedzi wraz z przynajmniej dwoma swoimi wrogami, wykonujemy kolejny krok, w którym przesadzamy go do drugiego stołu. Zauważmy, że jeśli siedział on przy stole wraz z trzema wrogami, to  zmienia się na  Jeśli zaś siedział on przy stole wraz z dwoma wrogami, to  zmienia się na liczbę niewiększą niż  Skoro po wykonaniu każdego kroku  maleje, to wykonamy ich skończenie wiele. Oczywiście, po wykonaniu ostatniego kroku  dla każdego  co kończy dowód.

Będziemy zaznaczać liczby w kilku krokach. W kroku 1. w każdym wierszu zaznaczamy najmniejszą liczbę. Jeśli wówczas w każdej kolumnie jest zaznaczona dokładnie jedna liczba, to kończymy. W przeciwnym razie, w kolejnym kroku w każdej kolumnie, w której znajdują się co najmniej dwie zaznaczone liczby, odznaczamy je wszystkie (czyli usuwamy zaznaczenie) oprócz największej. W ten sposób powstały wiersze, w których nie zaznaczono żadnej liczby – nazwijmy je wierszami wolnymi. Następnie zaznaczamy w każdym wolnym wierszu najmniejszą liczbę spośród tych, które nigdy wcześniej nie były zaznaczane ani odznaczane. W następnym kroku znowu patrzymy na kolumny, w których są zaznaczone co najmniej dwie liczby, i powtarzamy opisane rozumowanie, aż uzyskamy odpowiednie zaznaczenie lub nie będzie można wykonać kolejnego kroku.

Każdy wiersz może stać się wolny co najwyżej  razy, więc wykonamy co najwyżej  kroków. Po ostatnim kroku w każdej kolumnie będzie zaznaczony dokładnie jeden element.

Dla ustalenia uwagi przyjmijmy, że w tej procedurze zaznaczono elementy z przekątnej (możemy tak założyć, ewentualnie przestawiając kolumny). Spójrzmy na -ty wiersz. Jeśli  dla pewnego  to znaczy, że w pewnym kroku liczba  była odznaczona, a zatem

Wierzchołek, sąsiadujący z dwoma wierzchołkami innego koloru niż on sam, nazwijmy izolowanym. Wierzchołki, które są (w danym momencie gry) izolowane, i tylko one, zmieniają kolor w najbliższym ruchu. Wierzchołki nieizolowane tworzą bloki (długości co najmniej 2); ich kolor już się nie zmienia – do końca pozostają nieizolowane.

Przypuśćmy, że w jakimś momencie są zarówno wierzchołki izolowane, jak i nieizolowane. Pewien wierzchołek izolowany musi sąsiadować z nieizolowanym. W kolejnym ruchu przejmuje kolor sąsiada i staje się nieizolowanym. Zatem w każdym ruchu liczba wierzchołków izolowanych zmniejsza się. Gdy zejdzie do zera, kolory się ustabilizują.

Proces może więc trwać nieskończenie tylko wtedy, gdy na starcie wszystkie wierzchołki są izolowane – czyli gdy są pokolorowane na przemian (co jest możliwe tylko dla  parzystych). Wówczas po pierwszym ruchu wszystkie kolory zmienią się, po drugim powróci sytuacja początkowa, i ten cykl stale będzie się powtarzał. To jest ta konfiguracja początkowa, o jaką pyta zadanie.

W każdym wierszu numerujemy pola od lewej strony kolejno od 1 do  Podany warunek (nieparzyste sumy w kwadratach ) oznacza, że w dowolnych dwóch sąsiednich wierszach pola o numerach parzystych są wypełnione jednakowo, a pola o numerach nieparzystych są wypełnione różnie – lub że jest odwrotnie. Pomalujmy linię poziomą, która te wiersze rozdziela, na szaro w pierwszym przypadku, a na żółto w drugim.

Jeżeli istnieją dwie kolejne linie pomalowane tym samym kolorem, to zawarty pomiędzy nimi wiersz rozdziela dwa wiersze, które są wypełnione identycznie. Stąd wynika, że jeśli chcemy mieć wierszy parami różnych,  to jednakowo pomalowane linie nie mogą sąsiadować. Linie szare i żółte występują wówczas na przemian, więc każde dwa wiersze o numerach różniących się o 2 są wypełnione dokładnie przeciwnie (w kolumnach, gdzie górny ma zera, dolny ma jedynki, i na odwrót). Wobec tego wiersze o numerach różniących się o 4 są już wypełnione identycznie.

Wniosek: niezależnie od  maksymalna liczba parami nieidentycznych wierszy nie przekracza 4. Przy tym łatwo wskazać przykład takiej macierzy z dokładnie 4 wierszami:

Zatem liczby  o które pyta zadanie – to 2, 3, 4.

Wynik uzyskany przez uczestnika jest liczbą postaci (dowolny układ znaków). Wszystkie takie liczby są jednakowej parzystości. Zatem zbiór możliwych wyników zawiera się w zbiorze

Ten ostatni zbiór liczy  elementów. Wykażemy, że każdy element jest możliwym wynikiem.

Uczestnik z przynajmniej jedną dobrą odpowiedzią uzyskał wynik  gdzie  i nie wszystkie  są równe  Zamieniamy ciąg  na ciąg  określony następująco:

• gdy  bierzemy  pozostałe
• gdy  znajdujemy najmniejszy numer  dla którego (więc ); przyjmujemy  pozostałe

Uczestnik z „wektorem odpowiedzi”  ma wynik  Startując od prymusa z wektorem  czyli z wynikiem  możemy w opisany sposób wygenerować kolejno wyniki  itd., aż do  łącznie  wyników.

Warunek zadania żąda, by każdy wynik pojawił się co najwyżej dwukrotnie. Gdy pojawi się dokładnie dwukrotnie, da to szukane maksimum, równe

Zauważmy, że po każdym spotkaniu się dwóch kameleonów różnych kolorów reszta z dzielenia przez 3 liczebności kameleonów każdego z kolorów rośnie o 2 modulo 3. Ponieważ na początku reszty te były parami różne, to tak będzie również po każdym spotkaniu. Nigdy więc nie będzie tak, że na wyspie wszystkie kameleony będą tego samego koloru, bo wówczas wszystkie te reszty byłyby równe zeru.

Odpowiedź: Pokrycie istnieje wtedy i tylko wtedy, gdy  jest podzielne przez

Przyjmijmy, że kwadrat  udało się pokryć dostępnymi płytkami. Skoro pole płytki wynosi  to  musi być parzyste, powiedzmy  Rozważmy kolorowanie naszego kwadratu w pasy jak na rysunku. Zauważmy, że każda płytka jest jednego z dwóch rodzajów: zawiera  czarne pola lub  czarne pole. Niech liczba płytek pierwszego rodzaju wynosi  a drugiego  Zliczając czarne i białe pola, otrzymujemy  oraz  (dzięki temu, że  jest parzyste, mamy po równo pól czarnych i białych!). Stąd w szczególności  więc  zatem  jest parzyste, a   – podzielne przez

Z drugiej strony, dwie płytki dają pokrycie prostokąta  zatem łatwo można znaleźć pokrycie kwadratu  więc także dowolnego kwadratu  dla  będącego wielokrotnością

Uwaga. Rozwiązanie tego zadania różni się od rozwiązania podobnego zadania z poprzedniego numeru jedynie sposobem pokolorowania szachownicy.

Bez trudu da się ustawić  wież w żądany sposób; wystarczy zapełnić nimi prostokąt  Pokażemy, że więcej się nie da.

Przyjmijmy, że na szachownicy stoi  wież. Niech  będzie największą liczbą wież, jakie można wybrać spośród nich, by żadne dwie się nie atakowały. Należy dowieść, że jeśli  to  Wystarczy wykazać, że

Ustalmy więc układ  wież, z których żadne dwie nie stoją w jednym wierszu ani jednej kolumnie. Permutując wiersze i kolumny, można przyjąć, że te wieże stoją na polach  Podzielmy szachownicę na cztery obszary  gdzie  jest kwadratem (na jego przekątnej stoją wybrane wieże),  i   to prostokąty  oraz  zaś  to kwadrat  Wobec maksymalności  żadna wieża nie znajduje się w obrębie kwadratu

Weźmy teraz dowolne pole  w prostokącie  i symetryczne do niego pole  w prostokącie  Gdyby na obu tych polach stały wieże, to usuwając z poprzednio ustalonego układu wieżę z pola  oraz dołączając wieże z pól  otrzymalibyśmy układ  wież, stojących w różnych wierszach i kolumnach – wbrew maksymalności  Zatem co najwyżej połowa pól w sumie prostokątów  i   jest zajęta, czyli nie więcej niż  pól. Uwzględniając  pól kwadratu  uzyskujemy oczekiwane oszacowanie:

Odpowiedź: Pokrycie istnieje wtedy i tylko wtedy, gdy  jest podzielne przez
Przyjmijmy, że kwadrat  udało się pokryć dostępnymi płytkami. Skoro pole płytki wynosi  to  musi być parzyste, powiedzmy  Rozważmy kolorowanie naszego kwadratu jak standardowej szachownicy i zauważmy, że każda płytka jest jednego z dwóch rodzajów: zawiera  czarne pola lub  czarne pole. Niech liczba płytek pierwszego rodzaju wynosi  a drugiego  Zliczając czarne i białe pola, otrzymujemy  oraz  (dzięki temu, że  jest parzyste, mamy po równo pól czarnych i białych!). Stąd w szczególności  więc  zatem  jest parzyste, a  – podzielne przez

Z drugiej strony, łatwo znaleźć pokrycie kwadratu  spełniające warunki zadania, więc także dowolnego kwadratu  dla  będącego wielokrotnością

Oznaczmy przez  liczbę osób w rozważanej grupie. Wówczas każda z nich może znać  lub wszystkich  spośród pozostałych; łącznie jest  możliwości – tyle, ile osób. Gdyby każdy miał inną liczbę znajomych, to w rozważanym gronie byłaby osoba  która nie zna nikogo, oraz osoba  która zna wszystkich. To prowadzi do sprzeczności, bo czy wtedy  i  się znają, czy nie? Wobec tego nie jest możliwe, by każdy miał inną liczbę znajomych.

Skoro jest  podszachownic wymiaru  i   podszachownic wymiaru  to istnieje  pojedynczych ruchów możliwych do wykonania. Zauważmy, że wykonanie ruchu  a następnie ruchu  prowadzi do tego samego kolorowania szachownicy, co wykonanie najpierw ruchu  a potem ruchu  Ponadto wykonanie tego samego ruchu parzystą liczbę razy nie zmienia kolorowania szachownicy. Zatem każda sekwencja ruchów jest jednoznacznie opisana przez podanie ruchów występujących w niej nieparzystą liczbę razy. Jest więc nie więcej niż  nierównoważnych sekwencji ruchów (sekwencje uznajemy za równoważne, jeśli dają ten sam efekt). Startując z ustalonego kolorowania szachownicy, otrzymamy zatem co najwyżej  innych kolorowań. Ale wszystkich możliwych pokolorowań szachownicy jest  Znajdzie się więc takie, którego nie otrzymamy żadną sekwencją ruchów z całej białej szachownicy. Równoważnie, znajdzie się takie pokolorowanie, którego żadną sekwencją ruchów nie sprowadzimy do całej białej szachownicy.

Rozpisujemy symbole dwumianowe po obu stronach:

skracamy, co się da, i otrzymujemy równanie

Wprowadzamy oznaczenie  i przepisujemy równanie jako

W zbiorze liczb dodatnich wielomian  jest funkcją rosnącą; stąd równoważne równanie

Gdy  lub lewa strona ostatniego równania nie dzieli się przez 4; brak rozwiązań. Natomiast każda liczba  spełniająca warunek  lub wraz z liczbą  daje parę, spełniającą ostatnie równanie – więc i równoważne mu równanie wyjściowe.

Wykażemy najpierw, że

Rozważmy w tym celu -elementowe podzbiory zbioru  dla których  Wtedy  Zatem elementy  i   możemy wybrać na  sposobów. Sumując te możliwości po dozwolonych wartościach  dostajemy żądany wzór.

Rozważmy teraz -elementowe podzbiory zbioru  Takich podzbiorów, dla których  jest  gdzie  Zatem średnia arytmetyczna liczb  wynosi

Ale  więc ta średnia jest równa

Podzbiory  zbioru  łączymy w nieuporządkowane pary postaci  Takich par jest  Wobec założenia z treści zadania każdego studenta możemy utożsamiać jednoznacznie ze zbiorem pytań, na które zna odpowiedź. Gdyby studentów było więcej niż  to znalazłoby się dwóch, którym odpowiadałyby zbiory  i   To jednak przeczyłoby założeniu, że na egzaminie było pytanie, na które obaj znali odpowiedź.

Liczby wewnątrz kwadratów oznaczają długości ich boków.

Pewną liczbę kwadratów o bokach równych początkowym wyrazom ciągu Fibonacciego ustawmy jak na rysunku , po kolei dobudowując kwadraty na przemian po prawej stronie i na dole. Na każdym etapie tej konstrukcji powstaje prostokąt, bo   – następny kwadrat „pasuje” do dwóch poprzednich.

(a)

Jeśli ostatni kwadrat dobudowano na dole i ma on bok długości  to cały prostokąt ma taką właśnie szerokość, a wysokość równą następnemu wyrazowi ciągu, czyli  Jednocześnie wysokość ta jest równa

(b)

Analogicznie, jeśli ostatni kwadrat ustawiono po prawej i ma bok długości  to prostokąt ma szerokość równą  i zarazem równą

(c)

Jeśli jako ostatni ustawiono kwadrat o boku długości  to prostokąt ma taką właśnie szerokość lub wysokość, a drugi z wymiarów równy  więc ma pole  Jednocześnie pole to jest równe

Uwaga: Oznaczenia pochodzą z artykułu źródłowego.

Zmodyfikujmy rysunek z poprzedniego zadania, ustawiając kwadraty o bokach równych  kolejno po prawej, na dole, po lewej, na górze, znów po prawej itd., jak na rysunku . Żądany podział płaszczyzny uzyskamy, dzieląc jeden z dwóch kwadratów o boku długości 1 tak, jak w zadaniu 3.

Możliwe początki chodnika długości n.

Oznaczmy tę liczbę sposobów przez  Dla  na początku chodnika możemy położyć płytę a następnie na  sposobów ułożyć resztę (chodnik o długości ); możemy też zacząć od płyty  i wtedy na  sposobów ułożyć resztę. Stąd  dla  Otrzymany wzór jest taki sam, jak dla ciągu Fibonacciego. Nietrudno sprawdzić, że  oraz  uzyskujemy więc wniosek, że

Cięcie chodnika długości n + k - 1 na części o długościach n oraz k - 1.

Ile spośród chodników o długości  takich jak opisano w poprzednim zadaniu, można rozciąć na chodnik o długości  (od lewej strony) oraz chodnik o długości  (po prawej stronie) bez rozcinania poszczególnych płyt (Rys. (a))? Takich chodników jest tyle, na ile sposobów można ułożyć po lewej stronie chodnik długości  a po prawej chodnik długości   Z poprzedniego zadania wiemy, że możliwości tych jest po lewej  po prawej  więc łącznie  Cięcie chodnika wymaga rozcinania płyty, gdy w miejscu podziału leży płyta  (Rys. (b)).

Takich chodników jest : układamy od lewej kolejno chodnik długości  następnie płytę  a po prawej chodnik długości   Wszystkich chodników, jak wiemy z poprzedniego zadania, jest  i każdy z nich da się rozciąć w opisany sposób lub nie, stąd

Na rysunku (a) pokazano, jak zamalować 16 pól.

Aby wykazać, że więcej niż 16 pól nie można zamalować, rozważmy ułożenie trzech kopii każdej z liter  na serwetce, pokazane na rysunku (b). Zgodnie z treścią zadania nie można zamalować trzech pól z tą samą literą, więc można zamalować co najwyżej  pól.