Delta mi!

Udowodnimy, że

Zauważmy, że jeżeli i wszystkie połączenia są realizowane między rozłącznymi parami miast, to każda podróż może być złożona z tylko jednego lotu. Stąd

Rozważmy następujące doświadczenie trwające dni. W każdym z miast umieśćmy na początku jednego turystę. Pierwszego dnia zaplanujmy loty pary turystów, którzy znajdują się w miastach, między którymi kursuje najtańszy lot; drugiego dnia - pary turystów, którzy znajdują się w miastach, między którymi jest drugi najtańszy lot itd.

Po dniach każdy turysta będzie już po podróży mającej tę własność, że każdy kolejny lot był droższy od poprzedniego. Ponadto łącznie wszyscy turyści wykonają w sumie lotów, gdyż każdego dnia dokładnie dwóch wsiadło do samolotu. Stąd wniosek, że średnia długość podróży wśród wszystkich turystów jest równa lotów. W związku z tym istnieje turysta, którego wycieczka jest złożona z co najmniej tylu lotów, a zatem

(a) Stos z wybraną kartą (25) składamy jako środkowy i rozdajemy trafi do środkowej trójki w swoim nowym stosie.
(b) Stos z kartą 25 składamy jako dolny i rozdajemy trafi jako środkowa karta ostatniej trójki swojego nowego stosu.
(c) Stos z 25 składamy jako górny - przed 25 jest 0 dziewiątek, 2 trójki i 1 jedynka (czyli 7 kart).

Przypuśćmy, że przed wybraną kartą ma być 7 innych; w systemie trójkowym 7 to 021 (i dowolną liczbę od 0 do 26 też można zapisać jako 3-cyfrową). Trzykrotnie rozdajemy karty na 3 stosy i kolejno składamy je tak, by za pierwszym razem wskazany stos był w środku, za drugim na dole, a za trzecim - na górze (cyfry 021 czytamy od końca: 1 oznacza środek, 2 - dół, 0 - górę;

Dlaczego ta metoda działa? Przy ostatnim składaniu stosów kart, wybrana karta trafia do odpowiedniej z trzech dziewiątek (u nas do górnej), gdyż pierwsza cyfra zapisu trójkowego koduje, ile dziewiątek kart ma być przed wybraną (u nas zero).

We wcześniejszym ruchu, w ramach tejże dziewiątki wybrana karta trafiła do odpowiedniej z trzech trójek, gdyż środkowa cyfra zapisu trójkowego właśnie to koduje. Podobnie w pierwszym ruchu karta została ustawiona na odpowiednim z trzech miejsc w ramach swojej trójki, zgodnie z trzecią cyfrą zapisu.

Odpowiedź:

Przypuśćmy, że pola tablicy pokolorowano tak, że każdy kwadrat zawiera co najwyżej dwa czarne pola. Wówczas każdy z białych kwadratów oraz każda z szarych figur o polu na pierwszym rysunku zawiera co najwyżej czarne pola, a ponadto każdy z kolorowych kwadratów jednostkowych może być czarny. To oznacza, że łącznie w tablicy jest co najwyżej czarnych pól.

Z kolei kolorowanie 28 pól przedstawione na drugim rysunku ma tę własność, że każdy kwadrat zawiera dokładnie dwa czarne pola. To oznacza, że szukana najmniejsza wartość jest równa 29.

Macierz (tabelkę) o wymaganej własności, rozmiaru można utworzyć dla każdej liczby parzystej (więc i dla 8, i dla 14). Przykładowa konstrukcja:

Niech i niech oznacza macierz złożoną z samych jedynek, zaś - macierz mającą jedynki na głównej przekątnej i nad nią, a poniżej przekątnej zera. Tworzymy macierz rozmiaru (o wyrazach ):

Nietrudno sprawdzić, że sumy liczb w kolejnych kolumnach macierzy tworzą ciąg rosnący wszystkich liczb całkowitych od do natomiast sumy liczb w kolejnych wierszach tworzą ciąg malejący wszystkich liczb całkowitych od do z pominięciem tych uzyskanych już jako sumy kolumn. Macierz ma więc żądaną własność.

Rozważmy dowolny łuk danego okręgu zawierający wszystkie wyróżnione punkty i oznaczmy kolejne liczby przyporządkowane wyróżnionym punktom tego łuku przez Dla każdej liczby zdefiniujmy -wyrazowy ciąg binarny następująco: jeżeli pośród liczb wartość występuje parzystą liczbę razy oraz w przeciwnym przypadku.

Ponieważ jest tylko binarnych ciągów długości więc albo ciągi są parami różne i dla pewnego albo dla pewnych W pierwszym przypadku iloczyn liczb jest kwadratem liczby całkowitej, w drugim zaś - iloczyn liczb jest kwadratem liczby całkowitej.

Każdy ciąg dodatnich liczb całkowitych

których suma jest równa nazwiemy kompozycją liczby

Zauważmy, że -elementowe kompozycje liczby pozostają we wzajemnie jednoznacznej odpowiedniości z -elementowymi podzbiorami zbioru Każdej takiej kompozycji możemy przypisać zbiór

i odwrotnie: każdy podzbiór, którego elementy są wypisane w porządku rosnącym, wyznacza w powyższy sposób pewną kompozycję. Zatem liczba wszystkich kompozycji liczby jest równa liczbie podzbiorów zbioru -elementowego, czyli

Określmy funkcję która przyporządkowuje każdej kompozycji liczby pewną kompozycję następująco: jeżeli to

a jeżeli to

Zauważmy, że dla każdej kompozycji więc zadaje podział zbioru wszystkich kompozycji liczby na pary. Wprost z definicji wynika, że kompozycje w obrębie każdej pary różnią się parzystością liczby parzystych wyrazów. To oznacza, że liczba kompozycji zawierających parzystą liczbę liczb parzystych jest równa połowie liczby wszystkich kompozycji, czyli

Boki oznaczone tym samym kolorem sklejono zgodnie ze strzałkami. Konik może teraz skoczyć np. z pola 1 na pole 12.

Rozważmy wszystkie trójki zer i jedynek oznaczających kolejno położenie wilka, kozy i kapusty: 0 - na pierwszym brzegu rzeki, 1 - na drugim. W przestrzeni trójki te to współrzędne wierzchołków sześcianu, przy czym wierzchołek to położenie początkowe dobytku farmera, a - docelowe.

Ponieważ łódką można wozić najwyżej jedno stworzenie naraz, krawędzie tego sześcianu to wszystkie możliwe przewozy. Niektóre jednak są złe, np. krawędź oznacza, że farmer pozostawił wilka z kozą bez opieki i wiezie kapustę, co skończy się źle dla kozy. Zadanie sprowadza się więc do połączenia punktów i wzdłuż dobrych krawędzi, a to już łatwo zrobić na rysunku.

Czterowymiarowy hipersześcian. Czwarty wymiar symbolicznie reprezentowany jest "do wewnątrz"

Zadanie można rozwiązać podobnie jak poprzednie. Wystarczy rozważyć wszystkie czwórki zer i jedynek, które tym razem są wierzchołkami czterowymiarowego hipersześcianu. Po usunięciu złych krawędzi łatwo znaleźć drogę od do

Numery wierzchołków to numery pól szachownicy, kolorem oznaczono cykl Hamiltona

Tak.
Z każdego pola konik ma dokładnie cztery możliwe ruchy. Ilustrują je krawędzie czterowymiarowego hipersześcianu, a szukana droga odwiedzająca wszystkie jego wierzchołki (pola szachownicy) i wracająca do punktu wyjścia to tzw. cykl Hamiltona.

Cykl z rysunku powstał z dwóch osobnych cykli Hamiltona dla sześcianów trójwymiarowych (zewnętrznego i wewnętrznego), które połączono, usuwając z nich po jednej krawędzi (1-12 i 15-6) i dodając krawędzie 1-15 oraz 12-6. Podobnie cykl dla każdego trójwymiarowego sześcianu powstał z połączenia dwóch cykli dla kwadratów (podstaw tego sześcianu). Analogicznie można tworzyć cykle Hamiltona dla hipersześcianów -wymiarowych, gdzie

Każdy podzbiór -elementowego zbioru można opisać ciągiem zer i jedynek, gdzie 1 na -tym miejscu oznacza, że -ty element zbioru należy do rozważanego podzbioru, a 0 - że nie należy. Wtedy podzbiory to wierzchołki -wymiarowego hipersześcianu, przy czym podzbiory różniące się jednym elementem połączone są krawędzią.

Szukany ciąg można wyznaczyć przez cykl Hamiltona na tym hipersześcianie, podobnie jak na rysunku (ostatni i pierwszy podzbiór w takim ciągu też różnią się jednym elementem).

Jeżeli prostokąt został ułożony z pewnej liczby opisanych płytek, to jego powierzchnia jest liczbą podzielną przez wobec czego co najmniej jeden z wymiarów jest liczbą podzielną przez Przypuśćmy bez straty ogólności, że

Pomalujmy prostokąt w paski o wymiarach

Zauważmy, że każda kostka typu zawiera parzystą liczbę kolorowych pól (dokładnie dwa), a każda kostka typu zawiera nieparzystą liczbę kolorowych pól (jedno lub trzy). Ponieważ liczba kolorowych pól w całym prostokącie jest parzysta (jako wielokrotność liczby ), więc łączna liczba kostek zawierających nieparzystą liczbę kolorowych pól musi być parzysta.

Jeżeli prostokąt został ułożony z pewnej liczby opisanych płytek, to jego powierzchnia jest liczbą podzielną przez wobec czego co najmniej jeden z wymiarów jest liczbą podzielną przez Przypuśćmy bez straty ogólności, że

Pomalujmy prostokąt w paski o wymiarach

Zauważmy, że pól każdego koloru jest po tyle samo zarówno w całej tablicy (po ), jak i w obrębie dowolnej płytki typu Tymczasem każda z płytek typu jest zdominowana przez pewien kolor (w stosunku pól ). Wobec tego liczba płytek zdominowanych przez kolor biały musi być równa liczbie płytek zdominowanych przez kolor, a zatem łączna liczba płytek typu jest parzysta.

Podany warunek przepisujemy równoważnie jako Niech będzie zbiorem odwrotności wszystkich liczb za zbioru Dowolne dwa elementy zbioru są więc oddalone o co najmniej Zatem w każdym spośród przedziałów

może być co najwyżej jeden element zbioru Pozostałe liczby dodatnie tworzą przedział w którym są jedynie odwrotności liczb naturalnych To pokazuje, że zbiór (więc i zbiór ) może liczyć co najwyżej elementów.

Odpowiedź na drugie pytanie z zadania jest przecząca: na przykład dla nie istnieje -elementowy zbiór o podanej własności. Jak w przypadku ogólnym, zauważamy, że w każdym z przedziałów może być tylko jeden element zbioru Dalej, odwrotności liczb naturalnych, leżące w przedziale rozbijamy na pięć podzbiorów:

- każdy z nich ma średnicę mniejszą niż więc zawiera co najwyżej jeden element zbioru No i zostają jeszcze ułamki Liczność zbioru (więc i ) nie przekracza czyli 16.

Odpowiedź: Na sposobów.
Wyróżnijmy 15 pól tablicy, które tworzą skrajny dolny wiersz i skrajną lewą kolumnę. Zauważmy, że dowolne kolorowanie tych pól dwoma kolorami jednoznacznie określa pokolorowanie całej tablicy zgodnie z warunkami zadania - kolory pozostałych pól określamy w kolejności zadanej przez numery na rysunku.

Z drugiej strony każdy sposób pomalowania wszystkich pól tablicy jednoznacznie zadaje kolory pól wyróżnionych. To oznacza, że kolorowania tablicy o zadanych własnościach są we wzajemnie jednoznacznej odpowiedniości z dowolnymi pokolorowaniami wyróżnionych pól, a takich pokolorowań jest

Aby udowodnić równoważność, wykażemy osobno dwie implikacje.

Ponumerujmy osoby obecne na przyjęciu liczbami od do oraz oznaczmy liczbę wszystkich powitań przez Niech będzie permutacją zbioru która liczbie przyporządkowuje numer osoby, mającej na głowie kapelusz -tej osoby po -tym powitaniu. Mamy więc oraz gdzie jest transpozycją, a to numery osób uczestniczących w -tym powitaniu.

Wobec tego jest iloczynem transpozycji (wszystkich możliwych par elementów zbioru ). Z drugiej strony, w myśl warunków zadania, Ponieważ identyczność jest permutacją parzystą, więc wynika z tego, że skąd uzyskujemy To oznacza, że jeżeli opisana sytuacja jest możliwa, to daje resztę 0 lub 1 przy dzieleniu przez 4.

Aby uzasadnić, że dla każdego dającego resztę 0 lub 1 przy dzieleniu przez 4 istnieje kolejność powitań prowadząca do opisanej w treści zadania sytuacji, przeprowadzimy dowód indukcyjny.

Jeżeli to bezpośrednio sprawdzamy, że

więc wystarczy, że najpierw przywitają się osoby 1 i 2, potem 3 i 4 itd.

Przypuśćmy, że dla pewnego mamy odpowiednią kolejność powitań, czyli odpowiedni iloczyn transpozycji. Aby uzyskać odpowiednią kolejność dla dokonajmy następujących zmian w tym iloczynie:

dla W ten sposób uzupełniliśmy iloczyn o transpozycji (odpowiadających powitaniom z "nową" osobą numer ) i łatwo sprawdzić, że warunki zadania dla nowej kolejności są spełnione.

Z kolei aby uzyskać odpowiednią kolejność dla osób, dokonujemy podobnych zmian:

dla oraz dołączamy (w dowolnym miejscu) zestaw sześciu kolejno po sobie następujących powitań czterech nowych osób:

W ten sposób rozszerzyliśmy kolejność powitań w taki sposób, że znów po nastąpieniu wszystkich każdy ma znów swój kapelusz przy osobach. To kończy dowód indukcyjny.

Dla każdego jest dokładnie pięć możliwości opisujących, które z liczb należą do podzbioru spełniającego warunek zadania. Mianowicie:

a.

żadna z nich nie należy;

b.

tylko należy;

c.

tylko należy;

d.

tylko należy;

e.

liczby oraz należą (natomiast nie należy).

Ponieważ dla różnych możliwości te są niezależne, to liczba szukanych pozdbiorów wynosi

Zgodnie z uwagą wyżej, prawa strona to liczba pokryć paska kwadratami i prostokątami Każde takie pokrycie musi zawierać co najmniej elementów, w tym co najmniej jeden kwadrat. Jeśli w pokryciu wśród pierwszych elementów jest dokładnie kwadratów (i prostokątów ), to można je rozmieścić na sposobów i pokrywają one w sumie prostokąt Pozostały fragment paska można pokryć na sposobów. Tę drugą interpretację opisuje lewa strona tożsamości, stąd teza.

Słowu długości przyporządkujmy słowo długości przyjmując Znając słowo oraz element jednoznacznie odtwarzamy słowo

Obecność bloku 010 w słowie oznacza obecność bloku 0011 lub 1100 w słowie i na odwrót. Liczba słów bez bloków 0011, 1100, z elementem początkowym jest taka sama, jak tych z elementem początkowym ; i jest, w myśl poprzedniego spostrzeżenia, taka sama, jak liczba słów bez bloku 010. Stąd wniosek, że

• 100 dni: każdy pije z 1 beczki
• 3 dni:
  1) każdy pije ze 100 beczek
  2) każdy pije z 10 podejrzanych beczek
  3) każdy pije z 1 podejrzanej beczki
• 1 dzień: numerujemy beczki w systemie dwójkowym każdy pije z każdej beczki, której numer ma cyfrę 1 na jego miejscu

Niech oraz oznaczają odpowiednio liczbę wierszy i kolumn, zawierających liczbę dla Ponieważ każda z dziesięciu liczb umieszczonych w tablicy leży na skrzyżowaniu jednego z wierszy z jedną z kolumn, to dla każdego spełniona jest nierówność W takim razie również

więc

Rozważmy zbiory

oraz

Wówczas Bez straty ogólności przyjmijmy, że (przypadek rozważa się analogicznie). Z zasady szufladkowej Dirichleta wiemy, że w takim razie dla pewnego zbiór zawiera co najmniej pary postaci a to daje tezę.

Niech będzie zawodnikiem, który wygrał maksymalną liczbę meczów. Jeśli wygrał wszystkie, jest zwycięzcą. W przeciwnym wypadku istnieje zawodnik który wygrał z oraz istnieje przynajmniej jeden zawodnik pokonany przez

Gdyby gracz zwyciężył ze wszystkimi, którzy przegrali z to wygrałby więcej meczów niż (bo pokonał też ) - sprzeczność. Zatem przegrał z którymś z graczy, z którymi wygrał czyli istnieje trójkąt.

Z zadania 1 wiemy, że skoro nie ma trójkąta, to istnieje zwycięzca ; ustawmy go na początku rzędu. W gronie pozostałych graczy również nie ma trójkąta, więc istnieje gracz który pokonał ich wszystkich (ale nie ) - ustawmy go na drugim miejscu rzędu. Kolejnych graczy ustawiamy analogicznie.

Niech będzie cyklem, gdzie Rozważmy mecz Jeśli wygrał go gracz otrzymujemy trójkąt W przeciwnym przypadku otrzymujemy cykl o graczach. Jeśli jest ich więcej niż 3, postępujemy dalej analogicznie.

Rys. 2

Rys. 3 Cykl dłuższy o 1 od cyklu

Jeśli nie ma żadnych cykli, to nie ma trójkątów i na mocy zadania 1 istnieje zwycięzca. Wówczas niech grupa składa się tylko z niego, a grupa z pozostałych zawodników.

Jeśli istnieją cykle, to rozważmy cykl o maksymalnej długości. Jeżeli zawiera wszystkich graczy, to teza jest spełniona. W przeciwnym przypadku istnieje osoba która nie należy do cyklu eśli istnieją cykle, to rozważmy cykl o maksymalnej długości. Jeżeli zawiera wszystkich graczy, to teza jest spełniona. W przeciwnym przypadku istnieje osoba która nie należy do cyklu

Rys. 4 Cykl dłuższy o 2 od cyklu

Wykażemy, że albo wygrał ze wszystkimi zawodnikami z albo ze wszystkim przegrał. Załóżmy przeciwnie, że przegrał z ale wygrał z z cyklu (Rys. 2). Wówczas w cyklu na "drodze" od do istnieją tacy dwaj kolejni zawodnicy że przegrał z ale wygrał z . Wtedy cykl można wydłużyć, dołączając zawodnika pomiędzy a (Rys. 3), sprzecznie z założeniem o maksymalności

Jeżeli istnieją zawodnicy i spoza cyklu którzy odpowiednio wygrali i przegrali ze wszystkimi z cyklu, to wygrał z gdyż w przeciwnym razie cykl można by wydłużyć o tych dwóch graczy w sposób przedstawiony na rysunku 4.

Niech do grupy należą wszyscy zawodnicy, którzy wygrali z graczami z do ci, którzy przegrali z uczestnikami Wszystkich graczy z cyklu dołączmy do dowolnego spośród zbiorów W ten sposób otrzymujemy żądany podział.

Dla wskazany cel da się osiągnąć. W trzech ruchach wybieramy proste zawierające boki dużego trójkąta. Jego wierzchołki pozostaną białe (każdy zmieni kolor dwukrotnie), zaś środki boków staną się czarne. Teraz w jednym ruchu zmieniamy kolor dwóch z tych środków z powrotem na biały. Pozostaje jeden punkt czarny.

Także dla można uzyskać wymagany stan. Jak poprzednio, w trzech ruchach bierzemy proste, zawierające boki dużego trójkąta. Jego wierzchołki i jego środek staną się białe, pozostałe punkty siatki staną się czarne. W kolejnych trzech ruchach bierzemy proste równoległe do boków dużego trójkąta i przechodzące przez jego środek. Czarne punkty wybielą się, a punkt w środku się zaczerni.

Natomiast dla nie da się! W trójce punktów, będących wierzchołkami dużego trójkąta, po każdym ruchu jest parzysta liczba czarnych punktów (0 lub 2). Żaden z tej trójki nie może więc być owym punktem, który w pewnym momencie miałby stać się jedynym czarnym.

Każdy inny punkt siatki jest elementem pewnej szóstki punktów, tworzących sześciokąt foremny o boku 1. Również i w takiej szóstce każdy ruch powoduje zmianę koloru dokładnie dwóch punktów, więc niezmiennie jest w niej parzysta liczba czarnych punktów (0, 2, 4, 6). Pojedynczy czarny punkt pojawić się nie może.

Przyporządkujmy polom szachownicy w naturalny sposób pary liczb całkowitych gdzie Pomalujmy pola o obu współrzędnych parzystych na niebiesko, pola o obu współrzędnych nieparzystych - na czerwono, a pozostałe pola - na żółto.

Przypuśćmy, że pionki mogą poruszać się dowolnie długo w taki sposób, by żadne dwa nie spotkały się na jednym polu. W takim razie w każdej chwili na 16 niebieskich polach może znajdować się co najwyżej 16 pionków. Każdy pionek z czerwonego pola znajdzie się po dwóch ruchach na niebieskim polu, więc na czerwonych polach może przebywać w każdej chwili również co najwyżej 16 pionków. Ponadto każdy pionek z żółtego pola po jednym ruchu znajdzie się na polu niebieskim lub czerwonym. W takim razie na żółtych polach mogą przebywać naraz co najwyżej 32 pionki. Stąd na szachownicy mogą być łącznie najwyżej 64 pionki.

Jeśli pionków jest 65, to po pewnym czasie dwa z nich muszą znaleźć się na jednym polu.