/Konkursy/Olimpiada Matematyczna/60 (LX)

LX Olimpiada Matematyczna I stopień 2008/2009

I seria

Zadanie 1

Na niektórych polach szachownicy rozmiaru m × n ustawiono wieże. Wiadomo, że dowolna wieża znajduje się w polu rażenia co najwyżej dwóch innych wież. Wyznaczyć, w zależności od m ,n ≥ 2 , największą liczbę wież na szachownicy, dla której taka sytuacja jest możliwa.

Rozwiązanie

Oczywiście zaczynamy od prób i po jakimś czasie można wymyślić, że da się ustawić m + n wież. Przykład takiego ustawienia na rysunku.

Spróbujemy pokazać, że więcej wież postawić się nie da.

Sposób I

Przypuśćmy, że na szachownicy da się ustawić m + n + 1 wież tak, aby każda znajdowała się w polu rażenia co najwyżej dwóch. Dodatkowo przyjmijmy, że m ≥ n i jest liczbą wierszy. Gdyby w każdej kolumnie były co najwyżej 2 wieże to wszystich wież byłoby co najwyżej 2n ≤ m + n < m + n+ 1 . Zatem w pewnej kolumnie muszą być co najmniej 3 wieże.

Spośród tych wież wybierzmy środkową – jest ona atakowana przez dwie wieże, zatem odpowiadający jej wiersz nie może zawierać żadnych innych wież. Usuwamy ten wiersz i mamy poprawną sytuację w tablicy rozmiaru (m − 1)× n i w której jest m + n = (m − 1 )+ n + 1 wież. To jest nasz krok indukcyjny. Kontynuujemy tę operację aż dojdziemy do tablicy 2 × 2 , na której jest

2 + 2 + 1 = 5

wież. Oczywiście jest to niemożliwe.

Sposób II

Zauważmy, że z warunków zadania wynika, że każda wieża „widzi" co najmniej dwie krawędzie brzegowych pól szachownicy (bo najwyżej dwa ma zasłonięte). Wszystkich takich krawędzi pól jest 2m + 2n , zatem wszystkich wież nie może być więcej niż m + n (bo każde pole brzegowe może widzeć tylko jedna wieża).
Odpowiedź: m + n

Zadanie 2

Dana jest liczba całkowita n ≥ 2 . Niech r1,r2,r3,...,rn−1 będą odpowiednio resztami z dzielenia liczb

1,1+ 2,1+ 2+ 3,...,1+ 2+ ...+ (n − 1)

przez . Znaleźć wszystkie takie wartości , że ciąg (r1,r2,r3,...,rn− 1) jest permutacją ciągu (1,2,3 ,...,n − 1) .

Rozwiązanie

Dla prostoty nie będziemy odróżniać ciągu

n(n-−-1)- rn = 1+ 2+ ...+ (n − 1) = 2 ,

od ciągu reszt jakie dają te liczby przy dzieleniu przez ( będziemy mieli cały czas ustalone, więc nie prowadzi to do nieporozumień).

Po pierwsze wypisujemy sobie pierwszych kilka (kilkanaście) początkowych wyrazów ciągu i patrzymy dla jakich ciągi reszt są takie jak powinny być. Jak się to zrobi to narzuca się odpowiedź – będzie OK tylko dla potęg 2, czyli liczb postaci n = 2k . Ponadto dla liczb nieparzystych ostatnia reszta rn− 1 dzieli się przez . Spróbujmy to uzasadnić.

Jeżeli n = 2k + 1 jest nieparzyste to sprawa jest prosta

(2k-+-1)2k- rn−1 = r2k = 2 = (2k + 1)k

i widać, że liczba ta jest podzielna przez (a więc nie należy do zbioru (1,2,3 ,...,n − 1) )

O zadaniu trzeba myśleć następująco: ciąg reszt będzie żądaną permutacją, jeżeli każde dwie reszty będą różne. Aby tak było wystarczy, że rb − ra nie dzieli się przez dla 1 ≤ a < b < n . Ze wzoru na sumę ciągu arytmetycznego mamy

a+-1-+-b- rb − ra = (a+ 1)+ (a + 2 )+ ⋅⋅ ⋅+ b = 2 ⋅(b − a).

Załóżmy najpierw, że ma czynnik nieparzysty, czyli jest postaci n = (2k+ 1)m i m > 1 . Spróbujmy dobrać i , żeby różnica reszt wyszła podzielna przez . Trochę kombinując, można to wymyślić:

2km (2k + 1) rkm +k − rkm−k− 1 = -------------= km (2k+ 1). 2

W powyższej równości jest jeden drobny detal, mianowicie dla m = 2 i k = 1 mamy km − k − 1 = 0 , ale przypadek n = 6 możemy rozważyć osobno (lub przyjąć, że r0 = 0 ).

Pozostało zastanowić się nad przypadkiem n = 2k . Zastanówmy się czy liczba

(a+ 1 + b )(b − a) rb − ra = ------------------, 2

gdzie k 1 ≤ a < b < 2 , może dzielić się przez k n = 2 . Zauważmy, że tylko jedna z liczb a + b + 1,b − a jest parzysta i w dodatku maksymalnie może dzielić się przez (bo obie liczby są mniejsze od , więc oba wyrażenia są mniejsze od 2k+1 ). Zatem liczba

(a-+-1+--b)(b−--a) 2

nie dzieli się przez potęgę 2 wyższą niż 2k− 1 , co kończy dowód.

Zadanie 3

Okrąg wpisany w trójkąt ABC jest styczny do boków BC ,CA ,AB odpowiednio w punktach D ,E ,F . Punkty M ,N ,J są odpo- wiednio środkami okręgów wpisanych w trójkąty AEF ,BDF ,DEF . Dowieść, że punkty i są symetryczne względem prostej .

Rozwiązanie

W tym zadaniu (jak to często w geometrii) najważniejszy jest rysunek – to on powie nam co mamy robić.

Gdy dokładnie narysujemy opisaną sytuację, to pierwsza rzecz która się narzuca, to że punkty i leżą na okręgu wpisanym w trójkąt ABC . Zanim zaczniemy kombinować do czego to się może przydać, spróbujmy sprawdzić czy tak jest (prawy rysunek).

To co musimy sprawdzić, to czy ∘ ∡EMF + ∡EDF = 18 0 (bo to jest warunek na to, aby punkt leżał na okręgu opisanym na trójkącie EDF , albo jak ktoś woli na to, żeby na czworokącie MF DE można było opisać okrąg). Oba kąty łatwo jest wyliczyć korzystając z tego, że trójkąty AF E ,FBD ,DCE są równoramienne. Jeżeli oznaczymy kąty jak na rysunku to mamy

∘ ∘ ∘ ∘ ∡EDF = 180 − ∡CDE − ∡BDF = 180 − (9 0 − γ)− (90 − β) = γ + β ∘ ∘ 1- ∘ 1- ∘ ∘ α- ∡EMS = 90 − ∡F EM = 90 − 2∡F EA = 90 − 2(90 − α ) = 45 − 2 ∡EMF = 2∡EMS = 90 ∘ − α .

Jest więc jasne, że ∡EMF + ∡EDF = 180∘ , czyli punkt leży na okręgu wpisanym w trójkąt ABC . Oczywiście podobnie jest z punktem . Zanim przejdziemy dalej, zauważmy jeszcze, że punkt dzieli łuk na połowy, a punkt dzieli na połowy łuk .

Ok, teraz z powrotem popatrzmy na wyjściowy obrazek i się zastanówmy co dalej robić.

Ponieważ punkt dzieli łuk na połowy, prosta jest dwusieczną kąta EDF . Zatem leży na niej punkt . Podobnie, punkty E,J,N są współliniowe. Ponadto, z tych samych powodów, prosta jest dwusieczną kąta ENF oraz kąta DMF . Zatem czworokąt MF NJ musi być deltoidem, co dowodzi, że punkty i są symetryczne względem prostej .