mat03_zeszyt_cwiczen_dla_ucznia.doc

Zeszyt ćwiczeń

KOMPLETNY CHAOS JEST NIEMOŻLIWY

Jarosław Grytczuk

ZADANIA

1.   Mamy 82 kolorowe kredki. Wykazać, że można wybrać spośród nich 10 kredek tego samego koloru, lub 10 kredek, z których każda jest innego koloru.

2.   Na prostej zaznaczono 10 odcinków. Wykazać, że można wybrać 4 odcinki, które mają punkt wspólny, lub 4 odcinki parami rozłączne.

3.   Brzeg trójkąta równobocznego pomalowano dowolnie używając dwóch kolorów. Wykazać, że istnieją trzy punkty w tym samym kolorze będące wierzchołkami trójkąta prostokątnego.

4.   Wykazać, że w dowolnym kolorowaniu wszystkich punktów płaszczyzny trzema kolorami istnieją dwa punkty w odległości 1 w tym samym kolorze.

5.   Na przyjęciu spotkało się sześć osób. Okazało się, że każda z nich ma wśród pozostałych dokładnie trzech znajomych. Wykazać, że pewne cztery z tych osób mogą usiąść przy okrągłym stole w taki sposób, aby każda z nich siedziała pomiędzy swoimi dwoma znajomymi.

ROZWIĄZANIA

1.                 Pogrupujmy kredki tego samego koloru. Przypuśćmy, że w każdej grupie jest co najwyżej 9 kredek. Jeżeli różnych kolorów (grup) byłoby również co najwyżej 9, to mielibyśmy łącznie co najwyżej 81 kredek. Ale kredek jest 82. Zatem, albo jest co najmniej 10 kredek tego samego koloru, albo liczba różnych kolorów wynosi co najmniej 10.

2.                 Na początku wszystkie odcinki są szare. Rozważmy odcinek A, którego lewy koniec jest najdalej wysunięty na prawo. Pomalujmy ten odcinek na czerwono. Pomalujmy także na czerwono wszystkie odcinki, które przecinają odcinek A. Te czerwone odcinki mają punkt wspólny (jest nim na przykład lewy koniec odcinka A). Jeżeli czerwonych odcinków mamy co najmniej 4, to koniec zadania. Przypuśćmy więc, że są co najwyżej 3 czerwone odcinki i zapomnijmy o nich na chwilę. Niech B, będzie odcinkiem, którego lewy koniec jest najdalej na prawo wysunięty spośród wszystkich szarych odcinków. Pomalujmy odcinek B i wszystkie szare odcinki, które go przecinają na niebiesko. Podobnie jak poprzednio, albo mamy 4 niebieskie odcinki i koniec zadania, albo jest ich co najwyżej 3. Wówczas rozważmy szary odcinek C, którego lewy koniec jest wysunięty najdalej na prawo spośród pozostałych szarych odcinków i pomalujmy ten odcinek na zielono, wraz ze wszystkimi odcinkami, które go przecinają. Jeżeli mamy 4 zielone odcinki, to koniec zadania. Przypuśćmy więc, że jest ich co najwyżej 3. Został wobec tego co najmniej jeden szary odcinek D. Wystarczy teraz zauważyć, że odcinki A, B, C, D są parami rozłączne, co kończy dowód.

3.                 Rozważmy dziewięć punktów na brzegu trójkąta – trzy wierzchołki A, B, C, i sześć punktów P, Q, X, Y, U, V tworzących sześciokąt foremny (rysunek 1a, 1b). Nietrudno przekonać się, że istnieją jedynie dwa istotnie różne sposoby pomalowania tego sześciokąta tak, aby uniknąć trójkąta prostokątnego (rysunki 1a, 1b). Na przykład punkty PQUV tworzą prostokąt, zatem żadne trzy z nich nie mogą być tego samego koloru. Podobnie rzecz się ma dla PVXY i QUXY. Jednak w obu tych sytuacjach, pomalowanie punktu A dowolnym kolorem utworzy jednobarwny trójkąt prostokątny – APU lub AQV.

Rys. 1a                                         

Rys. 1b

4.                 Rozważmy figurę składającą się z czterech trójkątów równobocznych o bokach jednostkowych, położonych tak aby odległość między punktami B i C wynosiła dokładnie 1 (rysunek 2). Dysponując jedynie trzema kolorami nie uda nam się pomalować tych pięciu punktów tak, aby uniknąć odcinka jednostkowego o jednobarwnych końcach. W istocie, każdy z trójkątów musi być trójkolorowy, ale wtedy punkty B i C dostaną ten sam kolor.

Rys. 2

5.                 Wyobraźmy sobie, że te sześć osób znajduje się w wierzchołkach sześciokąta. Połączmy znajomych odcinkiem niebieskim a nieznajomych odcinkiem czerwonym. Skoro każda osoba zna dokładnie trzy inne osoby, to z każdego wierzchołka wychodzą trzy niebieskie i dwa czerwone odcinki. Istnieją tylko dwie możliwości rozmieszczenia czerwonych odcinków – albo w kształt pełnego sześciokąta, albo w dwa trójkąty (rysunki 3a i 3b). W obydwu przypadkach wierzchołki A, B, C, D tworzą cykl na niebieskich odcinkach czyniący zadość warunkowi zadania.

Rys. 3a

Projekt współfinansowany z Europejskiego Funduszu Społecznego w ramach Programu Operacyjnego Kapitał Ludzki

3