Zad. 1. Czy szachownicę o wymiarach 10×10 można pokryć prostokątami o
wymiarach 2×1 tak, by dokładnie połowa z nich była ustawiona poziomo?
Zad. 2. Niemalejąca funkcja f: N+ → N+ spełnia warunki: f(2) = 1 oraz f(ab) = f(a)f(b) dla dowolnych względnie pierwszych liczb a i b. Dowiedź, że f(n) = 1 dla każdego n.
Zad. 3. Niech W będzie niestałym wielomianem o współczynnikach całkowitych nieujemnych. Wykaż, że zbiór dzielników pierwszych liczb W(n) dla n = 1, 2, 3... jest nieskończony.
W tym miesiącu punkty zdobyli:
Mateusz Jagoda (ZSO Kluczbork): 29 = 10 + 10 + 9,
Jan Kropidłowski (III LO Wrocław): 20 = 10 + 10 + 0,
Szymon Michalik (XIV LO Warszawa): 18 = 10 + 8 + 0,
Danuta Wroniszewska (I LO Jelenia Góra): 12 = 2 + 10 + 0.
Gratulujemy!
Zad. 1. Nie da się tak. Ponumerujmy pola szachownicy liczbami od 1 do 100 tak, by w k-tym wierszu znalazły się liczby od 10(k-1)+1 do 10k. Dwadzieścia pięć protokątów ułożonych poziomo porywa wtedy 25 liczb parzystych i 25 nieparzystych. Pionowe prostokąty natomiast pokrywają każda parzyście wiele liczb nieparzystych (0 lub 2). Nie mogą więc pokryć pozostałych 25 liczb nieparzystych.
Zad. 2. f(1) = f(1·1) = f(1)·f(1), a zatem f(1) = 1. Zauważmy, że f(6) = f(2)·f(3) = f(3), a więc skoro f jest niemalejąca, to f(3) = f(4) = f(5) = f(6). Z kolei f(10) = f(2)·f(5) = f(5) = f(3) więc ponownie funkcja f jest stała na przedziale [3, 10]. Indukcyjnie nietrudno pokazać, że f(k) jest stale równa f(3) dla wszystkich k>2. Pozostaje tylko wykazać, że f(3) = 1. f(3) = f(15) = f(3)·f(5) = f(3)·f(3), więc f(3) = 1.
Zad. 3. Załóżmy nie wprost, że zbiór ten jest skończony. Oznaczmy go przez {q1, ..., qs}, a iloczyn wszystkich jego elementów przez Q. Zapiszmy nasz wielomian jako W(X) = a0 + a1X + ... + anXn, gdzie an > 0 i wszystkie współczynniki są całkowite nieujemne. Jeżeli a0 = 0 to X | W(X) jako wielomiany, a zatem dla dowolnej liczby pierwszej p zachodzi p | W(p). Załóżmy więc, że a0 > 0.
Wtedy W(a0Q) = a0(1 + a1Q + a2a0Q2 + ... + ana0n-1Qn). Zauważmy, że wyrażenie w nawiasie nie jest podzielne przez żadną z liczb q1, ..., qs, posiada więc inny czynnik pierwszy q. Wtedy q | W(a0Q), sprzeczność.
