Zad. 1. Pewne muzeum ma kształt trzydziestodwukąta. Wykaż, że da się tak ustawić dziesięciu nieruchomych strażników w tym muzeum, aby widzieli każdy jego punkt. Uwaga: zakładamy, że strażnicy mają oczy dookoła głowy.
Zad. 2. Wykaż, że z dowolnego zbioru stu dodatnich liczb całkowitych można tak wybrać pewien niepusty podzbiór, by suma liczb z tego podzbioru była podzielna przez 100.
Zad. 3. Wykaż, że dla dowolnej liczby naturalnej n>3 i dowolnych całkowitych a, b, c potrafimy znaleźć taką całkowitą liczbę k, że n nie jest dzielnikiem żadnej z liczb: k+a, k+b, k+c.
W tym miesiącu punkty zdobyli:
- 17 - Jakub Ceynowa (SP 95 Wrocław),
- 8 - Ignacy Gałek (SP 1 Wrocław).
Gratulujemy!
Zad. 1. Każdy wielokąt prosty można podzielić na trójkąty nieprzecinającymi się przekątnymi. Dowód indukcyjny opiera się na fakcie, że w każdym wielokącie (dla n > 3) istnieje wierzchołek, którego sąsiedzi wyznaczają przekątną leżącą całkowicie wewnątrz figury. Odcięcie wyznaczonego w ten sposób trójkąta redukuje liczbę wierzchołków o 1, co pozwala na powtarzanie procesu aż do pełnego podziału. Wierzchołki tak podzielonego wielokąta są kolorowalne trzema kolorami (3-kolorowalne). Przywracając w kroku indukcyjnym odcięty wierzchołek, zauważamy, że łączy się on krawędziami z dwoma wierzchołkami o różnych barwach. Zawsze można więc przypisać mu trzeci, wolny kolor. W efekcie każdy trójkąt podziału posiada wierzchołki w trzech różnych kolorach. Zbiór 32 wierzchołków dzielimy na 3 grupy kolorystyczne. Z zasady szufladkowej Dirichleta najmniej liczna grupa ma co najwyżej 10 elementów (część całkowita z 32/3). Ustawienie strażników w wierzchołkach tego koloru zapewnia widoczność każdego trójkąta podziału, a zatem całego muzeum.
Zad. 2. Niech a1, a2, ..., a100 będą liczbami ze zbioru. Rozważmy ciąg 100 sum początkowych:
S1 = a1, S2 = a1 + a2, ..., S100 = a1 + a2 + ... + a100. Jeśli któraś suma daje resztę 0 przy dzieleniu przez 100, zadanie jest rozwiązane. W przeciwnym razie każda z 100 sum daje resztę ze zbioru {1, 2, ..., 99}. Mamy 100 sum (szufladki) i tylko 99 możliwych reszt (przedmioty). Z zasady szufladkowej Dirichleta pewne dwie sumy Si oraz Sj (gdzie i < j) dają tę samą resztę. Wtedy ich różnica Sj – Si jest podzielna przez 100. Różnica ta jest sumą podzbioru {ai+1, ..., aj}, co kończy dowód.
Zad. 3. Szukamy liczby całkowitej k, dla której n nie jest dzielnikiem liczb: k+a, k+b oraz k+c. Warunek „n jest dzielnikiem k+x” jest równoważny temu, że k przy dzieleniu przez n daje taką samą resztę jak liczba –x. Mamy zatem co najwyżej 3 „zakazane” reszty dla liczby k: są to reszty z dzielenia przez n liczb –a, –b oraz –c. Zbiór wszystkich możliwych reszt z dzielenia przez n to {0, 1, 2, ..., n–1}. Liczność tego zbioru wynosi n. Z założenia n > 3, więc n ≥ 4. Ponieważ dostępnych reszt jest co najmniej 4, a reszt zakazanych co najwyżej 3, to istnieje przynajmniej jedna reszta dopuszczalna. Wybierając k dające taką resztę, zapewniamy, że żadna z sum nie będzie podzielna przez n.
