XLIX OLIMPIADA MATEMATYCZNA

Do Pani/Pana Dyrektora Szkoły Do Pani/Pana Profesora Matematyki

Komitet Główny Olimpiady Matematycznej uprzejmie prosi o zapoznanie uczniów i nauczycieli zainteresowanych zadaniami Olimpiady z podanymi tu szkicami rozwia_{}zań zadań konkursowych stopnia pierwszego XLIX Olimpiady Matematycznej.

W dalszej cze_{}ści niniejszego druku podajemy teksty zadań z zawodów mie_{}dzynarodowych: XXXVIII Mie_{}dzynarodowej Olimpiady Matematycznej i XX Austriacko–Polskich Zawodów Matematycznych, a także z VIII Zawodów Matematycznych Państw Bałtyckich (Baltic Way ′97).

Zawody pierwszego stopnia XLIX Olimpiady Matematycznej sa_{}zakończone. Zawody stopnia drugiego odbe_{}da_{}sie_{}w dniach 27 i 28 lutego 1998 r.

Zawiadomienia o dokładnym terminie i miejscu zawodów stopnia drugiego wyśla_{}komitety okre_{}gowe zakwalifikowanym zawodnikom w terminie do dnia 10 lutego 1998 r.

Komitet Główny Olimpiady Matematycznej

Szkice rozwia_{}zań zadań konkursowych

zawodów pierwszego stopnia XLIX Olimpiady Matematycznej

1. Przypuśćmy, że liczby x, y spełniaja_{}podany układ równań. Z pierwszego równania wynika, że x ≠ 0 oraz że iloraz |x|: x nie może być równy −1; jest wie_{}c równy 1, co oznacza, że x jest liczba_{}dodatnia_{}. Pierwsze równanie mówi zatem, że |x−y| = 0. Podstawiaja_{}c y = x do drugiego równania (i pamie_{}taja_{}c, że x > 0) otrzymujemy zależność 2x−1+|2x−1| = 0, równoważna_{} temu, że 2x−1 0. Tak wie_{}c każde rozwia_{}zanie (x,y) danego układu równań ma postać 0 < x = y 1/2. Na odwrót, każda para (x,y) takiej postaci spełnia oba równania układu.

2. Oznaczmy przez M środek boku BC. Rozwia_{}zanie zadania be_{}dzie oparte na równości AH = 2·OM (która zachodzi w każdym trójka_{}cie, niezależnie od założenia, że AO = AH). Oto jej dowód:

Można przyja_{}ć, że AB AC; ka_{}t ABC jest wie_{}c ostry. Gdy ka_{}t CAB jest prosty, wówczas AH = OM = 0. Gdy ka_{}t CAB jest ostry lub rozwarty, prowadzimy średnice_{}okre_{}gu opisanego na trójka_{}cie ABC. Odcinek OM ła_{}czy środki boków CX i CB trójka_{}ta prostoka_{}tnego CBX, a zatem 2·OM = BX. Proste AX i HB sa_{}równoległe (każda z nich jest prostopadła do AC); także proste BX i HA sa_{}równoległe (jako prostopadłe do BC). Wobec tego czworoka_{}t AHBX jest równoległobokiem i AH = BX = 2·OM.

Jeśli teraz, zgodnie z treścia_{}zadania, długość odcinka AH jest równa promieniowi okre_{}gu opisanego na trójka_{}cie ABC, to punkt M jest środkiem promienia prostopadłego do BC. Sta_{}d wynika, że < ) BOC = 120^{∘}. Wniosek: ka_{}t CAB, jako ka_{}t wpisany oparty albo na krótszym albo na dłuższym łuku BC, ma miare_{}60^{∘} lub 120^{∘}.

3. Wykażemy przez indukcje_{}, że

(1)  2^{2n−1} +1 < a_{n} 2^{2n}.

Dla n = 1 nierówności 3 < a_{1} 4 sa_{}spełnione. Zakładaja_{}c, że oszacowania (1) zachodza_{}dla pewnej liczby naturalnej n, otrzymujemy dla n+1 analogiczne oszacowania:

a_{n+1} = a_{n}(a_{n} −1) \{ \begin{matrix}< a_{n}^{2} (2^{2n})^{2} = 2^{2n+1} \\ > (2^{2n−1} +1)·2^{2n−1} = 2^{2n} +2^{2n−1} > 2^{2n} +1. \end{matrix}

Na podstawie zasady indukcji wnosimy o prawdziwości zwia_{}zków (1) dla wszystkich liczb naturalnych n 1. Ze zwia_{}zków tych wynika oczywiście, że 2^{2n−1} < a_{n} 2^{2n}. Zaste_{}puja_{}c a_{n} przez 2^{bn}, a naste_{}pnie b_{n} przez 2^{n−cn}, dostajemy kolejno nierówności: 2^{n−1} < b_{n} 2^{n}; naste_{}pnie: n−1 < n−c_{n} n; i wreszcie: 0 c_{n} < 1. Cia_{}g (c_{n}) jest wie_{}c ograniczony.

4. Ustalmy liczbe_{}rzeczywista_{}c. Podstawiaja_{}c w podanej nierówności y = tx i dziela_{}c stronami przez x^{a+1} otrzymujemy warunek równoważny

(1)  ct^{a+1} −t^{a} c−1 dla t > 0.

Mówia_{}c wyraźniej: rozważana w zadaniu nierówność zachodzi dla każdej pary liczb dodatnich x, y wtedy i tylko wtedy, gdy nierówność (1) zachodzi dla każdej liczby dodatniej t.

Oznaczaja_{}c lewa_{}strone_{}(1) przez f(t) stwierdzamy, że f(1) = c−1 oraz f′(t) = c(a+1)t^{a} −at^{a−1}. Jeżeli warunek (1) jest spełniony, to funkcja f ma w punkcie t = 1 minimum, a wie_{}c f′(1) = c(a+1)−a = 0, ska_{}d c = a/(a+1). Na odwrót, jeśli c = a/(a+1), to

f′(t) = at^{a} −at^{a−1} = at^{a−1}(t−1) \{ \begin{matrix}> 0 & dla t > 1, \\ < 0 & dla t < 1; \end{matrix}

a zatem najmniejsza_{}wartościa_{}funkcji f w przedziale (0;∞) jest f(1) = c−1, czyli spełniony jest warunek (1).

Wniosek: dla danej liczby dodatniej a jedynie liczba c = a/(a+1) ma postulowana_{}własność.

5. Ponieważ 2ctg2x = 2· \frac{cos2x}{sin2x} = \frac{cos^{2}x−sin^{2}x}{sinxcosx} = ctgx−tgx, dane równanie jest równoważne naste_{}puja_{}cemu:

(1)  |tg^{n}x−ctg^{n}x| = n|tgx−ctgx|.

Gdy n = 1, równanie (1) jest spełnione tożsamościowo w zbiorze liczb, które nie sa_{}całkowitymi wielokrotnościami π/2.

Dalej rozważamy przypadek, gdy n 2. Równanie (1) jest oczywiście spełnione, gdy tgx = ctgx, czyli dla liczb postaci x = mπ/4, gdzie m jest dowolna_{}liczba_{}całkowita_{}nieparzysta_{}. Wykażemy, że dla n 2 równanie (1) nie ma innych rozwia_{}zań.

Przypuśćmy wie_{}c, że istnieje liczba x spełniaja_{}ca równanie (1) i taka, że liczby a = tgx, b = ctgx nie sa_{}równe; warunek a ≠ b jest równoważny temu, że |a| ≠ 1. Dziela_{}c (1) stronami przez |a−b| dostajemy zwia_{}zek

|a^{n−1} +a^{n−2}b+...+ab^{n−2} +b^{n−1}| = n.

Wszystkie składniki sa_{}jednocześnie dodatnie lub ujemne; moduł sumy jest wie_{}c równy sumie modułów. Uwzgle_{}dniaja_{}c zależność b = 1/a otrzymujemy:

(2)  |a|^{n−1} +|a|^{n−3} +...+|a|^{−n+3} +|a|^{−n+1} = n.

Dla każdej liczby dodatniej t ≠ 1 prawdziwa jest nierówność t+t^{−1} > 2 (równoważna, po prostym przekształceniu, nierówności (t−1)^{2} > 0). Zatem dla każdej liczby całkowitej k mamy

|a|^{k} +|a|^{−k} \begin{cases}> 2 & gdy k ≠ 0, \\ = 2 & gdy k = 0. \end{cases}

Podstawiaja_{}c za k kolejno liczby n−1, n−3, ..., −n+3, −n+1 i dodaja_{}c stronami otrzymane n nierówności stwierdzamy, że podwojona wartość sumy napisanej po lewej stronie zwia_{}zku (2) jest wie_{}ksza od 2n. (W tym miejscu ma znaczenie warunek, że n 2.) Zatem równość (2) nie jest w rozważanym przypadku możliwa, co oznacza, że równanie (1) nie ma innych rozwia_{}zań niż te, które zostały znalezione na pocza_{}tku.

6. Oznaczmy przez X punkt przecie_{}cia odcinków BE i AD, a przez F punkt symetryczny do C wzgle_{}dem A; prosta F B jest równoległa do AD. Przyjmijmy oznaczenia ka_{}tów:

< ) CAD = < ) EF B = φ, < ) DXB = < ) EBF = ψ.

Przy założeniu, że AB > AC (podanym w poprawionej wersji zadania, rozesłanej w Erratach) punkt D leży mie_{}dzy punktami A i P, i mamy oszacowanie: ψ = < ) BXP < < ) BDP < 90^{∘}; wynika z niego, że P Q = BE ·cosψ.

Odcinek AD ła_{}czy środki boków trójka_{}ta F CB; tak wie_{}c BF = 2·AD. Sta_{}d oraz z twierdzenia sinusów dla trójka_{}ta EF B otrzymujemy zależności:

\frac{AD}{P Q} = \frac{2·AD}{2·BE} · \frac{BE}{P Q} = \frac{BF}{2·BE} · \frac{1}{cosψ} = \frac{sin< ) BEF}{sin< ) BF E} · \frac{1}{2cosψ} =
= \frac{sin(φ+ψ)}{2sinφcosψ} = \frac{1+ctgφtgψ}{2} .

Zatem równość AD = P Q jest równoważna temu, że tgψ = tgφ, czyli φ = ψ. Ta ostatnia równość jest zaś równoważna temu, że trójka_{}t BEF jest równoramienny: BE = EF. A skoro EF = AE +AC, dostajemy teze_{}zadania.

7. Funkcje_{}f spełniaja_{}ca_{}podane warunki be_{}dziemy nazywać dobra_{}. Przypuśćmy, że liczby k_{1} <... < k_{m} sa_{}wszystkimi wartościami przyjmowanymi przez dobra_{}funkcje_{}f. Niech

(1)  l_{i} = max{j ∈ A: f(j) = k_{i}} dla i = 1,...,m;

oczywiście l_{m} = n. Z określenia (1) oraz z warunków definiuja_{}cych funkcje dobre wynika, że f(k_{i}) = f(f(l_{i})) = f(l_{i}) = k_{i} dla i = 1,...,m, i wobec tego

(2)  0 < k_{1} l_{1} < k_{2} l_{2} <... < k_{m−1} l_{m−1} < k_{m} n.

Na odwrót, jeżeli (k_{1},l_{1},k_{2},l_{2},...,k_{m−1},l_{m−1},k_{m}) jest dowolnym cia_{}giem liczb naturalnych spełniaja_{}cym warunki (2), to wzór

f(j) = \begin{cases}k_{1} & & & gdy 0 < j l_{1} \\ k_{2} & & & gdy l_{1} < j l_{2} \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ k_{m} & & & gdy l_{m−1} < j n \end{cases}

określa dobra_{}funkcje_{}f:A → A, której wartościami sa_{}liczby k_{i}, a warunek (1) wyznacza zadane liczby l_{i} (trzeba tylko przyja_{}ć l_{m} = n). Dobrych funkcji f jest wie_{}c tyle, ile cia_{}gów typu (2).

Każdemu cia_{}gowi liczb naturalnych spełniaja_{}cemu warunki (2) przyporza_{}dkujemy cia_{}g (a_{1},b_{1},a_{2},b_{2},...,a_{m−1},b_{m−1},a_{m}) o wyrazach

(3)  \begin{aligned}a_{i} & = k_{i} +i−1 dla i = 1,...,m, \\ b_{i} & = l_{i} +i  dla i = 1,...,m−1. \end{aligned}

Z układu nierówności (2) wynika, że wówczas

(4)  0 < a_{1} < b_{1} < a_{2} < b_{2} <... < a_{m−1} < b_{m−1} < a_{m} < n+m.

Na odwrót, maja_{}c dany dowolny cia_{}g spełniaja_{}cy warunki (4) możemy odtworzyć cia_{}g (k_{1},l_{1},k_{2},l_{2},...,k_{m−1},l_{m−1},k_{m}) przyjmuja_{}c

(5)  \begin{aligned}k_{i} & = a_{i} −i+1 dla i = 1,...,m, \\ l_{i} & = b_{i} −i  dla i = 1,...,m−1; \end{aligned}

nierówności (2) be_{}da_{}spełnione. Wzajemnie odwrotne układy równań (3) i (5) ustalaja_{}wzajemnie jednoznaczna_{}odpowiedniość mie_{}dzy cia_{}gami typu (2) i cia_{}gami typu (4).

Wniosek: dobrych funkcji f:A → A jest tyle, ile (2m−1)-wyrazowych cia_{}gów liczb naturalnych spełniaja_{}cych warunki (4) — czyli tyle, ile (2m−1)- elementowych podzbiorów ma zbiór {1,2,...,n+m−1}. Ta szukana liczba jest równa \binom{n+m−1}{2m−1}.

8. Niech k be_{}dzie liczba_{}krawe_{}dzi, a s — liczba_{}ścian wielościanu wypukłego W. Brzeg każdej ściany zawiera co najmniej trzy krawe_{}dzie, a każda krawe_{}dź jest wspólnym bokiem dokładnie dwóch ścian. Zatem 2k 3s. Jeśli płaszczyzna nie przechodza_{}ca przez żaden wierzchołek przecina r krawe_{}dzi, to przekrój wielościanu ta_{}płaszczyzna_{}jest wieloka_{}tem wypukłym maja_{}cym r wierzchołków, a wie_{}c także r boków. Każdy jego bok jest zawarty w pewnej ścianie wielościanu W, i to każdy w innej. Wobec tego s r, i w konsekwencji 2k 3r. Nie istnieje wie_{}c wielościan o rozważanej w zadaniu własności.

9. W myśl podanego określenia,

a_{k} = 1−(\frac{1}{10})^{2k} +(\frac{1}{10})^{2k+1} dla k = 0,1,2,... .

Oznaczmy liczbe_{}\frac{1}{10} przez β oraz przyjmijmy α = 1+β +β^{2} = 1,11. Zachodza_{} równości

α·a_{0} = (1+β^{1} +β^{2})(1−β^{1} +β^{2}) = 1+β^{2} +β^{4},
α·a_{0}a_{1} = (1+β^{2} +β^{4})(1−β^{2} +β^{4}) = 1+β^{4} +β^{8},
α·a_{0}a_{1}a_{2} = (1+β^{4} +β^{8})(1−β^{4} +β^{8}) = 1+β^{8} +β^{16},

i ogólnie (indukcja)

α·a_{0}a_{1}...a_{n} = 1+β^{2n+1} +β^{2n+2} dla n = 0,1,2,... .

Gdy n da_{}ży do nieskończoności, wartość otrzymanego wyrażenia da_{}ży do 1. Zatem

lim_{n→∞}(a_{0}a_{1}...a_{n}) = \frac{1}{α} = \frac{100}{111} .

10. Oznaczmy miary ka_{}tów CAB, ABC, BCA przez α, β, γ, a miary ka_{}tów F GE, DGF, EGD odpowiednio przez α′, β′, γ′. Na czworoka_{}tach AF GE i BDGF można opisać okre_{}gi, wie_{}c α+α′ = 180^{∘} oraz β +β′ = 180^{∘}. Zatem także γ +γ′ = 180^{∘} (bowiem α+β +γ = 180^{∘}, α′ +β′ +γ′ = 360^{∘}); a to oznacza, że również na czworoka_{}cie CEGD można opisać okra_{}g.

Z istnienia pierwszej wymienionej pary okre_{}gów opisanych wynika ponadto, że < ) AF E = < ) AGE = < ) DGB = < ) DF B. Odcinki F E i DF sa_{}odpowiednio równoległe do BC i CA; wobec tego < ) AF E = β, < ) DF B = α, i otrzymujemy równość α = β.

Wykorzystuja_{}c istnienie okre_{}gu opisanego na czworoka_{}cie CEGD dowodzimy analogicznie, że β = γ. Trójka_{}t ABC jest wie_{}c równoboczny.

11. Niech A be_{}dzie tym uczestnikiem turnieju, który pokonał najwie_{}ksza_{} liczbe_{}przeciwników. (Jeśli kilku zawodników odniosło jednakowa_{}maksymalna_{}liczbe_{}zwycie_{}stw, wybieramy któregokolwiek z nich.) Twierdzimy, że wybrany w ten sposób gracz A pokonał bezpośrednio lub pośrednio wszystkich innych zawodników.

Niech B be_{}dzie dowolnym graczem, który wygrał z A. Należy wykazać, że wśród wszystkich graczy C_{1},...,C_{m} pokonanych przez A istnieje taki, który wygrał z B. Gdyby to nie było prawda_{}, wynikałoby sta_{}d, że zawodnik B pokonał graczy C_{1},...,C_{m} oraz jeszcze gracza A — miałby wie_{}c na swoim koncie wie_{}cej zwycie_{}stw niż zawodnik A, wbrew wyborowi tego ostatniego. Sprzeczność kończy dowód.

12. Niech p_{1} = 2, p_{2} = 3, p_{3} = 5, p_{4} = 7,... be_{}dzie rosna_{}cym cia_{}giem wszystkich liczb pierwszych i niech W be_{}dzie wielomianem stopnia dodatniego o współczynnikach całkowitych. Ustalmy liczbe_{}całkowita_{}a, dla której W (a) ≠ 0, oraz ustalmy liczbe_{}naturalna_{}n.

Weźmy pod uwage_{}liczbe_{}c = W (a)·p_{1}p_{2}...p_{n}. Znajdujemy liczbe_{}naturalna_{}m 2, dla której W (a+mc) ≠ W (a); liczba taka istnieje, bo wartość W (a) jest przez wielomian W przyjmowana tylko w skończenie wielu punktach.

Dla danej liczby całkowitej b ≠ a różnica W (b)−W (a) dzieli sie_{}przez b−a (jeśli bowiem W (x) = α_{0} +α_{1}x+...+α_{l}x^{l}, to W (b)−W (a) jest suma_{} składników α_{j}(b^{j} −a^{j}) dla j = 1,...,l, a każdy z nich dzieli sie_{}przez b−a). W szczególności różnica W (a+mc)−W (a) dzieli sie_{}przez mc. Zatem dla pewnej liczby całkowitej q ≠ 0 zachodzi równość

W (a+mc) = W (a)+qmc = W (a)(1+qmp_{1}p_{2}...p_{n}).

Skoro m 2, liczba w nawiasie ma moduł wie_{}kszy od 1. Liczba ta nie dzieli sie_{}przez p_{1}, p_{2},..., p_{n}; ma wie_{}c co najmniej jeden dzielnik pierwszy wie_{}kszy od p_{n}. Jest on także dzielnikiem liczby W (a+mc) (która również ma moduł wie_{}kszy od 1). To znaczy, że g(W (a+mc)) > p_{n}.

Wykazaliśmy w ten sposób, że dla dowolnie ustalonej liczby naturalnej n zbiór liczb postaci g(W (x)) zawiera liczbe_{}wie_{}ksza_{}od p_{n}. Nie istnieje wie_{}c wielomian, dla którego zbiór ten byłby skończony.

(mek)

Zadania z XXXVIII Mie_{}dzynarodowej Olimpiady Matematycznej

Mar del Plata (Argentyna), 24 – 25 lipca 1997 r.

1. Na płaszczyźnie punkty o współrze_{}dnych całkowitych sa_{}wierzchołkami kwadratów jednostkowych. Kwadraty te pomalowano na przemian na czarno i biało (tak, jak na szachownicy).

Dla każdej pary liczb całkowitych dodatnich m i n rozważamy trójka_{}t prostoka_{}tny, którego wierzchołki maja_{}współrze_{}dne całkowite, a przyprostoka_{}tne długości m i n leża_{}na liniach wyznaczonych przez boki kwadratów. Niech S_{1} be_{}dzie polem czarnej cze_{}ści trójka_{}ta, a S_{2} — polem cze_{}ści białej oraz niech f(m,n) = |S_{1} −S_{2}|.

(a) Obliczyć f(m,n) dla wszystkich liczb całkowitych m i n, które sa_{}albo obie parzyste, albo obie nieparzyste.

(b) Udowodnić, że f(m,n) \frac{1}{2} max\{m,n\} dla wszystkich m i n.

(c) Wykazać, że nie istnieje taka stała C, że f(m,n) < C dla wszystkich m i n.

2. Ka_{}t A jest najmniejszym ka_{}tem trójka_{}ta ABC. Punkty B i C dziela_{} okra_{}g opisany na trójka_{}cie na dwa łuki. Niech U be_{}dzie punktem wewne_{}trznym tego łuku o końcach B i C, który nie zawiera punktu A. Symetralne odcinków AB i AC przecinaja_{}prosta_{}AU odpowiednio w punktach V i W. Proste BV i CW przecinaja_{}sie_{}w punkcie T. Udowodnić, że AU = T B +T C.

3. Niech x_{1},x_{2},...,x_{n} be_{}da_{}liczbami rzeczywistymi spełniaja_{}cymi warunki:

|x_{1} +x_{2} +...+x_{n}| = 1 oraz |x_{i}| \frac{n+1}{2} dla i = 1,2,...,n.

Dowieść, że istnieje permutacja y_{1},y_{2},...,y_{n} liczb x_{1},x_{2},...,x_{n}, dla której

|y_{1} +2y_{2} +...+ny_{n}| \frac{n+1}{2} .

4. Macierz n×n (tablice_{}kwadratowa_{}maja_{}ca_{}n wierszy i n kolumn) o wyrazach ze zbioru S = {1,2,...,2n−1} be_{}dziemy nazywać macierza_{}srebrzysta_{}, jeżeli dla każdego i = 1,2,...,n wiersz i-ty oraz i-ta kolumna zawieraja_{} ła_{}cznie wszystkie elementy zbioru S. Dowieść, że

(a) nie istnieje macierz srebrzysta dla n = 1997;

(b) istnieja_{}macierze srebrzyste dla nieskończenie wielu wartości n.

5. Wyznaczyć wszystkie pary (a,b) liczb całkowitych a 1, b 1, które spełniaja_{}równanie a^{b^{2}} = b^{a}.

6. Dla liczby całkowitej dodatniej n niech f(n) oznacza liczbe_{}sposobów przedstawienia n w postaci sumy pote_{}g liczby 2 o wykładnikach całkowitych nieujemnch. Nie rozróżniamy takich przedstawień, które różnia_{}sie_{}jedynie porza_{}dkiem składników. Na przykład f(4) = 4, gdyż liczbe_{}4 można przedstawić na cztery sposoby: 4; 2+2; 2+1+1; 1+1+1+1. Udowodnić, że

2^{n^{2}/4} < f(2^{n}) < 2^{n^{2}/2}

dla każdej liczby całkowitej n 3.

Zadania z XX Austriacko-Polskich Zawodów Matematycznych

Salzburg (Austria), 25 – 27 czerwca 1997 r.

1. Proste l_{1} i l_{2} przecinaja_{}sie_{}w punkcie P. Okre_{}gi S_{1} i S_{2} sa_{}styczne zewne_{}trznie w punkcie P i prosta l_{1} jest ich wspólna_{}styczna_{}w tym punkcie. Podobnie, okre_{}gi T_{1} i T_{2} sa_{}styczne zewne_{}trznie w punkcie P i prosta l_{2} jest ich wspólna_{}styczna_{}w tym punkcie. Okre_{}gi S_{1} i T_{1} przecinaja_{}sie_{}w punktach P i A. Podobnie, okre_{}gi S_{1} i T_{2} przecinaja_{}sie_{}w punktach P i B, okre_{}gi S_{2} i T_{2} w punktach P i C oraz okre_{}gi S_{2} i T_{1} w punktach P i D. Udowodnić, że punkty A, B, C i D leża_{}na okre_{}gu wtedy i tylko wtedy, gdy proste l_{1} i l_{2} sa_{}prostopadłe.

2. Dana jest szachownica maja_{}ca m kolumn i n wierszy. Każde pole ma współrze_{}dne (x,y), gdzie x jest numerem kolumny (1 x m), a y jest numerem wiersza (1 y n). Niech p i q be_{}da_{}liczbami całkowitymi dodatnimi. Pionek stoja_{}cy na polu (x,y) może poruszyć sie_{}na pole (x′,y′) wtedy i tylko wtedy, gdy |x−x′| = p i |y −y′| = q.

Na każdym polu stoi jeden pionek. Chcemy jednocześnie wykonać ruch wszystkimi pionkami tak, by znów na każdym polu stał tylko jeden pionek. Na ile sposobów można to zrobić ?

3. Na tablicy napisano 97 liczb: 48, 24, 16, ..., 48/97, tzn. liczby wymierne 48/k dla k = 1,2,3,...,97. W każdym kroku wybieramy dowolnie dwie liczby a i b napisane na tablicy, usuwamy je i wpisujemy liczbe_{}2ab−a−b+1. Po 96 krokach na tablicy pozostanie dokładnie jedna liczba. Wyznaczyć zbiór liczb, które moga_{}pozostać na tablicy.

4. W czworoka_{}cie wypukłym ABCD boki AB i CD sa_{}równoległe. Przeka_{}tne AC i BD przecinaja_{}sie_{}w punkcie E. Punkt F jest punktem przecie_{}cia wysokości trójka_{}ta EBC, a punkt G jest punktem przecie_{}cia wysokości trójka_{}ta EAD. Udowodnić, że środek odcinka GF leży na prostej przechodza_{}cej przez punkt E i prostopadłej do AB.

5. Niech p_{1}, p_{2}, p_{3}, p_{4} be_{}da_{}czterema różnymi liczbami pierwszymi. Udowodnić, że nie istnieje wielomian trzeciego stopnia Q(x) = ax^{3} +bx^{2} +cx+d o współczynnikach całkowitych taki, że

|Q(p_{1})| = |Q(p_{2})| = |Q(p_{3})| = |Q(p_{4})| = 3.

6. Udowodnić, że nie istnieje funkcja f:Z → Z spełniaja_{}ca równanie f(x+f(y)) = f(x)−y dla wszystkich liczb całkowitych x, y.

Uwaga. Z jest zbiorem liczb całkowitych.

7. (a) Udowodnić, że dla dowolnych liczb rzeczywistych p, q zachodzi nierówność: p^{2} +q^{2} +1 > p(q +1).

(b) Wyznaczyć najwie_{}ksza_{}liczbe_{}rzeczywista_{}b taka_{}, że dla wszystkich liczb rzeczywistych p, q zachodzi nierówność: p^{2} +q^{2} +1 bp(q +1).

(c) Wyznaczyć najwie_{}ksza_{}liczbe_{}rzeczywista_{}c taka_{}, że dla wszystkich liczb całkowitych p, q zachodzi nierówność: p^{2} +q^{2} +1 cp(q +1).

8. Niech n be_{}dzie liczba_{}naturalna_{}i niech M be_{}dzie zbiorem n-elemen-towym. Wyznaczyć najwie_{}ksza_{}liczbe_{}naturalna_{}k o naste_{}puja_{}cej własności:

Istnieje k-elementowa rodzina K trójelementowych podzbiorów zbioru M taka, że każde dwa zbiory należa_{}ce do K maja_{}niepuste przecie_{}cie.

9. Dany jest równoległościan P. Niech V_{P} be_{}dzie jego obje_{}tościa_{}, S_{P} polem jego powierzchni i L_{P} suma_{}długości jego krawe_{}dzi. Dla liczby rzeczywistej t 0 niech P_{t} be_{}dzie bryła_{}złożona_{}ze wszystkich punktów X, których odległość od P jest nie wie_{}ksza niż t. Udowodnić, że obje_{}tość bryły P_{t} wyraża sie_{}wzorem:

V (P_{t}) = V_{P} +S_{P} ·t+(π/4)·L_{P} ·t^{2} +(4/3)·π ·t^{3}.

Wyjaśnienie: Odległość punktu X od równoległościanu P jest nie wie_{}ksza niż t, jeśli istnieje punkt Y należa_{}cy do równoległościanu P taki, że |XY | t.

Zadania z VIII Zawodów Matematycznych Państw Bałtyckich

Baltic Way ′97 Kopenhaga (Dania), 9 listopada 1997 r.

1. Wyznaczyć wszystkie funkcje f ze zbioru liczb rzeczywistych do zbioru liczb rzeczywistych, różne od funkcji zerowej i takie, że f(x)f(y) = f(x−y) dla wszystkich liczb rzeczywistych x i y.

2. Dany jest cia_{}g a_{1},a_{2},a_{3},... liczb całkowitych dodatnich, w którym każda liczba całkowita dodatnia wyste_{}puje dokładnie raz. Dowieść, że istnieja_{} liczby całkowite ℓ i m, 1 < ℓ < m, takie, że a_{1} +a_{m} = 2a_{ℓ}.

3. Niech x_{1} = 1 oraz x_{n+1} = x_{n} +[\frac{x_{n}}{n} ]+2 dla n = 1,2,3,... ([x] oznacza najwie_{}ksza_{}liczbe_{}całkowita_{}nie wie_{}ksza_{}niż x). Wyznaczyć x_{1997}.

4. Niech a be_{}dzie średnia_{}arytmetyczna_{}liczb x_{1},...,x_{n}. Udowodnić nierówność

(x_{1} −a)^{2} +...+(x_{n} −a)^{2} \frac{1}{2}(|x_{1} −a|+...+|x_{n} −a|)^{2}.

5. Dany jest cia_{}g u_{0},u_{1},... liczb całkowitych dodatnich o dowolnym wyrazie pocza_{}tkowym u_{0}. Dla każdej liczby całkowitej dodatniej n:

u_{n+1} = \begin{cases}u_{n}/2 & gdy liczba u_{n} jest parzysta, \\ a+u_{n} & gdy liczba u_{n} jest nieparzysta; \end{cases}

a jest ustalona_{}dodatnia_{}liczba_{}całkowita_{}nieparzysta_{}. Dowieść, że cia_{}g ten od pewnego miejsca jest okresowy.

6. Znaleźć wszystkie trójki (a,b,c) liczb całkowitych nieujemnych takie, że a b c oraz 1·a^{3} + 9·b^{2} + 9·c + 7 = 1997.

7. Niech P i Q be_{}da_{}wielomianami o współczynnikach całkowitych. Przypuśćmy, że liczby całkowite a i a+1997 sa_{}pierwiastkami wielomianu P oraz że Q(1998) = 2000. Dowieść, że równanie Q(P (x)) = 1 nie ma rozwia_{}zań w liczbach całkowitych.

8. Gdy dodajemy liczby 1996 i 1997, to najpierw dodajemy cyfry jedności 6 i 7. Otrzymujemy 13, zapisujemy 3 i ,,przenosimy” 1 do naste_{}pnej kolumny. W ten sposób wykonujemy przeniesienie. Kontynuuja_{}c, wykonamy ła_{}cznie trzy przeniesienia:

1 1 1 1996 + 1997 3993

Czy istnieje taka liczba całkowita dodatnia k, że przy dodawaniu 1996·k do 1997·k nie be_{}dzie ani jednego przeniesienia?

9. Na Sferze Światów światy sa_{}ponumerowane 1,2,3,... i poła_{}czone tak, że dla każdej liczby naturalnej n 1 czarodziej Gandalf może poruszać sie_{}w obu kierunkach pomie_{}dzy światami o numerach n, 2n i 3n+1. Czy zaczynaja_{}c od dowolnego świata Gandalf może dotrzeć do każdego innego świata?

10. Dowieść, że w dowolnym cia_{}gu 79 kolejnych liczb całkowitych dodatnich, zapisanych w systemie dziesie_{}tnym, istnieje liczba całkowita dodatnia, której suma cyfr jest podzielna przez 13.

11. Na dwóch równoległych prostych wybrano odpowiednio różne punkty A_{1}, A_{2}, A_{3},... oraz B_{1}, B_{2}, B_{3},... w taki sposób, że |A_{i}A_{i+1}| = 1 oraz

|B_{i}B_{i+1}| = 2 dla i = 1,2,3,..., przy czym wektory \overrightarrow{A_{i}A_{i+1}} i \overrightarrow{B_{i}B_{i+1}} sa_{}jednakowo skierowane. Wiedza_{}c, że < ) A_{1}A_{2}B_{1} = α, obliczyć wartość nieskończonej sumy

< ) A_{1}B_{1}A_{2} +< ) A_{2}B_{2}A_{3} +< ) A_{3}B_{3}A_{4} +... .

12. Dwa okre_{}gi C_{1} i C_{2} przecinaja_{}sie_{}w punktach P i Q. Prosta przechodza_{}ca przez P przecina ponownie C_{1} i C_{2} odpowiednio w punktach A i B. Punkt X jest środkiem odcinka AB. Prosta przechodza_{}ca przez Q i X przecina ponownie C_{1} i C_{2} odpowiednio w punktach Y i Z. Udowodnić, że X jest środkiem odcinka Y Z.

13. Pie_{}ć różnych punktów A, B, C, D i E leży na prostej, przy czym |AB| = |BC| = |CD| = |DE|. Punkt F nie leży na tej prostej. Punkt G jest środkiem okre_{}gu opisanego na trójka_{}cie ADF, zaś H jest środkiem okre_{}gu opisanego na trójka_{}cie BEF. Dowieść, że proste GH i F C sa_{}prostopadłe.

14. Dany jest trójka_{}t ABC, w którym |AC|^{2} jest średnia_{}arytmetyczna_{} liczb |BC|^{2} i |AB|^{2}. Udowodnić, że ctg^{2}B ctgA·ctgC.

15. W trójka_{}cie ostroka_{}tnym ABC dwusieczne ka_{}tów < ) A, < ) B i < ) C przecinaja_{}okra_{}g opisany odpowiednio w punktach A_{1}, B_{1} i C_{1}. Niech M be_{}dzie punktem przecie_{}cia prostych AB i B_{1}C_{1}, a N punktem przecie_{}cia prostych BC i A_{1}B_{1}. Dowieść, że MN przechodzi przez środek okre_{}gu wpisanego w trójka_{}t ABC.

16. Dwaj gracze graja_{}na szachownicy 5×5 w naste_{}puja_{}ca_{}gre_{}. Pierwszy gracz stawia skoczka na wybranym polu. Naste_{}pnie gracze na przemian (zaczynaja_{}c od gracza drugiego) przesuwaja_{}skoczka według reguł szachowych. Nie wolno przesuna_{}ć skoczka na pole, na którym już był. Przegrywa gracz, który nie może wykonać ruchu. Który z dwóch graczy ma strategie_{} wygrywaja_{}ca_{}?

17. Prostoka_{}t można podzielić na n równych kwadratów. Ten sam prostoka_{}t można również podzielić na n+76 równych kwadratów. Wyznaczyć n.

18. (a) Udowodnić, że istnieja_{}dwa nieskończone zbiory liczb całkowitych nieujemnych A i B (niekoniecznie rozła_{}czne) takie, że każda_{}liczbe_{}całkowita_{} nieujemna_{}n można jednoznacznie przedstawić w postaci n = a+b, gdzie a ∈ A, b ∈ B.

(a) Udowodnić, że dla każdej takiej pary (A,B) zbiór A lub zbiór B zawiera tylko wielokrotności pewnej liczby całkowitej k > 1.

19. W puszczy każde z n zwierza_{}t (n 3) mieszka w swojej grocie. Przed wyborami Króla Puszczy niektóre zwierze_{}ta organizuja_{}kampanie_{}wyborcza_{}. Każde zwierze_{}organizuja_{}ce kampanie_{}odwiedza każda_{}z pozostałych grot dokładnie raz. Porusza sie_{}tylko po ścieżkach prowadza_{}cych od groty do groty; nie przechodzi przy tym z jednej ścieżki na inna_{}pomie_{}dzy grotami i wraca do swojej własnej groty na końcu kampanii. Przez żadna_{}ścieżke_{}ła_{}cza_{}ca_{}dwie groty nie przechodzi wie_{}cej niż jedno zwierze_{}organizuja_{}ce kampanie_{}.

(a) Udowodnić, że dla każdej liczby pierwszej n maksymalna możliwa liczba zwierza_{}t organizuja_{}cych kampanie_{}równa sie_{}(n−1)/2.

(b) Wyznaczyć maksymalna_{}liczbe_{}zwierza_{}t organizuja_{}cych kampanie_{}dla n = 9.

20. W rze_{}dzie leży dwanaście kart. Karty sa_{}trzech rodzajów: maja_{}obie strony białe, obie strony czarne lub jedna_{}strone_{}biała_{}i jedna_{}czarna_{}. Pocza_{}tkowo dziewie_{}ć z tych kart leży czarna_{}strona_{}do góry. Naste_{}pnie odwracamy karty 1 – 6, po czym cztery karty leża_{}czarna_{}strona_{}do góry. Potem odwracamy karty 4 – 9, w rezultacie czego sześć kart leży czarna_{}strona_{}do góry. W końcu odwracamy karty 1 – 3 i 10 – 12, po czym pie_{}ć kart leży czarna_{} strona_{}do góry. Ile jest kart każdego rodzaju?