LXVII (67) OM - II etap

[marcin7Cd]

Zadania:
1.We wnętrzu trójkąta o bokach długości \(\displaystyle{ 3,4,5}\) leży punkt \(\displaystyle{ P}\). Wykazać, że jeżeli odległości \(\displaystyle{ P}\) od wierzchołków są wszystkie wymierne, to odległość \(\displaystyle{ P}\) od boków też.

2.W trójkącie ostrokątnym \(\displaystyle{ ABC}\) dwusieczna kąta \(\displaystyle{ BAC}\) przecina bok \(\displaystyle{ BC}\) w punkcie \(\displaystyle{ D}\). Symetralna odcinka \(\displaystyle{ AD}\) przecina okrąg opisany na trójkącie \(\displaystyle{ ABC}\) w punktach \(\displaystyle{ E}\) i \(\displaystyle{ F}\). Udowodnić, że okrąg opisany na trójkącie \(\displaystyle{ D E F}\) jest styczny do prostej \(\displaystyle{ BC}\)

3.Niech \(\displaystyle{ \ZZ}\) oznacza zbiór liczb całkowitych. Rozstrzygnąć, czy istnieje funkcja \(\displaystyle{ f}\), która każdej liczbie całkowitej \(\displaystyle{ k}\) przypisuje nieujemną liczbę całkowitą \(\displaystyle{ f(k)}\) i spełnia następujące dwa warunki:\(\displaystyle{ f(0)>0}\) ; dla każdej liczby całkowitej \(\displaystyle{ k}\) najmniejsza spośród liczb postaci \(\displaystyle{ f(k-l)+f(l)}\), gdzie \(\displaystyle{ l\in \ZZ}\), jest równa \(\displaystyle{ f(k)}\).

[bakala12]

Dziękujemy wybawco! Myślę, że wielu sympatyków Olimpiady czekało na zadania jak na szpilkach!

[Wiesiek7]

Jak oceniacie poziom zadań?
Dwa pierwsze łatwe, ale zawiodłem się, bo nie było klasycznej torii liczb i jakieś trudne kombi :/ Wydaje mi się, że o wiele trudniejsze niż rok temu Jak wy oceniacie?

[Pinionrzek]

No pierwsze dwa w istocie proste. Trzecie już trochę trudniejsze, ale też bez przesady. Moim zdaniem to była klasyczna teoria liczb, ewentualnie teoria liczb z elementami algebry. Nie widzę za bardzo aspektu kombinatorycznego w tym zadaniu. Poza tym, to uważam, że zadania porównywalne poziomem z ubiegłorocznymi, może nawet ciut trudniejsze.

[cuber2460]

Mógłby ktoś podzielić się swoim rozwiązaniem do trzeciego? (najlepiej poprawnym)

[Swistak]

To napiszę trzecie:

Ukryta treść:    

Niech \(\displaystyle{ c = f(d)}\) będzie najmniejszą wartością \(\displaystyle{ f}\). \(\displaystyle{ c = f(a) + f(d - a) \ge c + c \Rightarrow c = 0}\). Niech teraz \(\displaystyle{ A}\) będzie zbiorem takich \(\displaystyle{ x \in \mathbb{Z}}\), że \(\displaystyle{ f(x) = 0}\). Już wiemy, że jest to zbiór niepusty. Ponadto \(\displaystyle{ a, b \in A \Rightarrow a + b \in A}\) oraz jak \(\displaystyle{ a \in A}\), to istnieją \(\displaystyle{ b, c \in A}\) t. że \(\displaystyle{ a = b + c}\). Łatwo zauważyć, że zbiór ten musi zawierać zarówno liczby dodatnie jak i ujemne i niech \(\displaystyle{ x}\) będzie najmniejszym dodatnim elementem \(\displaystyle{ A}\) i niech \(\displaystyle{ y}\) będzie największym ujemnym elementem. Ale wtedy \(\displaystyle{ x +y \in A}\), ale \(\displaystyle{ y < x+y < x}\) i \(\displaystyle{ x+y \neq 0}\), zatem sprzeczność z wyborem x i y.

[piotr5]

Szkic trzeciego:

Ukryta treść:    

Jeśli \(\displaystyle{ m=f(k)}\) jest najmniejszą wartością \(\displaystyle{ f}\), to istnieje takie \(\displaystyle{ l}\), że
\(\displaystyle{ m=f(k)=f(k-l)+f(l)\ge 2m}\) skąd \(\displaystyle{ m=0}\).
Niech \(\displaystyle{ k}\) najmniejsze dodatnie takie, że \(\displaystyle{ f(k)=0}\) (ponieważ \(\displaystyle{ f(-k)}\) też spełnia warunki zadania to możemy tak założyć).
Indukcja po \(\displaystyle{ m}\), że dla wszystkich \(\displaystyle{ m<l<k}\) zachodzi \(\displaystyle{ f(l)>0}\).
Dla \(\displaystyle{ m=-1}\) oczywiste. Jeśli zachodzi dla \(\displaystyle{ m}\) to \(\displaystyle{ m<m+k<k}\) więc
\(\displaystyle{ f(m)=f(m)+f(k)\ge f(m+k)>0}\) czyli teza zachodzi dla \(\displaystyle{ m-1}\).
No i teraz mamy już łatwą sprzeczność bo dla dowolnego \(\displaystyle{ l}\) mamy \(\displaystyle{ f(l)>0}\) lub \(\displaystyle{ f(k-l)>0}\).

edit:
Świstak mnie wyprzedził o minutę Ale moje rozwiązanie jest troszeczkę inne (chociaż mniej eleganckie)

edit2:
Zadania moim zdaniem bardzo proste, nawet za proste.

Ukryta treść:    

Pierwsze pałowalne, drugie na jedną symetrię, którą widać od razu i rozwala całe zadanie, a w trzecim najtrudniejsze było zrozumieć drugi warunek.

[marcin7Cd]

Zadania:
4.Dana jest liczba całkowita dodatnia \(\displaystyle{ k}\). Udowodnić, że istnieje liczba całkowita dodatnia \(\displaystyle{ n}\), dla której zbiory \(\displaystyle{ A=\left\{ 1^2,2^2,3^2,...\right\}}\) i \(\displaystyle{ B=\left\{ 1^2+n,2^2+n,3^2+n,...\right\}}\) mają dokładnie \(\displaystyle{ k}\) wspólnych elementów.

5.Czworokąt \(\displaystyle{ ABCD}\) jest wpisany w okrąg. Punkty \(\displaystyle{ P}\) i \(\displaystyle{ Q}\) leżą odpowiednio na półprostych \(\displaystyle{ AB}\) i \(\displaystyle{ AD}\), przy czym \(\displaystyle{ AP=CD}\), \(\displaystyle{ AQ=BC}\). Wykazać, że środek odcinka \(\displaystyle{ PQ}\) leży na prostej \(\displaystyle{ AC}\).

6.W przestrzeni danych jest \(\displaystyle{ n}\) zielonych punktów, przy czym \(\displaystyle{ n \ge 4}\) i żadne cztery zielone punkty nie leżą na jednej płaszczyźnie. Niektóre odcinki łączące zielone punkty pomalowano na czerwono. Liczba czerwonych odcinków jest parzysta. Każde dwa różne zielone punkty łączy pewna łamana złożona z czerwonych odcinków. Udowodnić, że czerwone odcinki da się podzielić na takie pary, że odcinki z jednej pary mają wspólny koniec.

[bakala12]

No to z tego co widzę, to dzisiaj jeszcze łatwiej niż wczoraj 4 i 5 są bardzo proste, za ostatnie jeszcze się nie zabierałem. Dwa pierwsze dzisiaj są prostsze niż wczorajsze i uważam, że jak na drugi dzień to za proste...
Oto szkice rozwiązań dwóch pierwszych zadań:

Zadanie 4.:    

Niech \(\displaystyle{ a \in A}\) oraz \(\displaystyle{ b\in B}\). Wystarczy wykazać, że równanie \(\displaystyle{ a^{2}-b^{2}=n}\) ma dokładnie \(\displaystyle{ k}\) rozwiązań w liczbach całkowitych dodatnich \(\displaystyle{ a,b}\) dla pewnego \(\displaystyle{ n}\). Przyjmijmy \(\displaystyle{ n=2^{2k+2}}\). Mamy wówczas \(\displaystyle{ \left(a-b\right)\left(a+b\right)=2^{2k+2}}\). Oczywiście mamy \(\displaystyle{ a>b}\) oraz \(\displaystyle{ a-b<a+b}\) a więc:
\(\displaystyle{ \begin{cases} a-b = 2^{i} \\ a+b = 2^{2k+2-i} \end{cases}}\)
przy czym oczywiście \(\displaystyle{ 0 \le i <k+1}\). Jak się okazuje, każdy taki układ równań ma dokładnie jedno rozwiązanie, więc w sumie mamy \(\displaystyle{ k+1}\) rozwiązań naszego równania, ale jak napisał świstak poniżej za co bardzo dziękuję, bo ja to przeoczyłem, dla \(\displaystyle{ k=0}\) rozwiązanie nie jest całkowite, a więc zbiory \(\displaystyle{ A}\) i \(\displaystyle{ B}\) mają dokładnie \(\displaystyle{ k}\) elementów wspólnych.

Zadanie 5.:    

To zadanie to przegięcie. Niech \(\displaystyle{ S}\) będzie przecięciem prostych \(\displaystyle{ PQ}\) i \(\displaystyle{ AC}\). Niech \(\displaystyle{ \angle BAC = \alpha}\) oraz \(\displaystyle{ \angle CAD = \beta}\). Korzystając dwukrotnie z twierdzenia sinusów mamy:
\(\displaystyle{ \frac{PS}{QS} = \frac{AP}{AQ} \cdot \frac{\sin \alpha}{\sin \beta} = \frac{CD}{BC} \cdot \frac{\sin \alpha}{\sin \beta}}\)
Na mocy twierdzenia sinusów do trójkąta \(\displaystyle{ \Delta BCD}\) mamy:
\(\displaystyle{ \frac{BC}{CD} = \frac{\sin \alpha}{\sin \beta}}\).
Łącząc dwie powyższe równości natychmiast dostajemy tezę zadania.

[kfas]

Zadanie 5. zrobiłem jak ty, ale męcząc się wcześniej dość długo

W 4. chyba jest jednak jeszcze drobna pułapka, która każe za n wziąć \(\displaystyle{ 3^{2k}}\), gdyż inaczej układ przy k=0 ma niecałkowite rozwiązanie.

Były więc chyba 4 proste zadania (proste dla olimpijskich starych wyjadaczy), ale to nie znaczy, że 100/600 osób rozwiązało wszystkie 4. Było sporo mocnych osób, które jakiegoś z nich nie zrobiły.

Jeśli po sprawdzeniu okaże się, że właśnie 4 trzeba było mieć (np. próg 22), to będzie bardzo dobrze świadczyć o tym zestawie zadań.

[Swistak]

bakala12, masz malutki błąd:

Ukryta treść:    

Jak \(\displaystyle{ i=0}\), to wtedy to rozwiązanie wychodzi niecałkowite, zatem będzie ich \(\displaystyle{ k-1}\), a nie \(\displaystyle{ k}\), o czym łatwo się przekonać testując dla \(\displaystyle{ k=1}\) . Powinieneś wziąć np. \(\displaystyle{ 2^{2k+2}}\) i śmiga.

[bakala12]

Racja, dziękuję bardzo! W pośpiechu takie rzeczy wychodzą. Zaraz wyedytuję post.
A jeśli już stawiamy jaki będzie próg to pewnie standardowo koło 18-19, bo trzeba zauważyć że 4 zadania były proste, ale wśród nich są dwie geometrie, a z tym to różnie bywa

[rosyjska dusza]

W 4. chyba jest jednak jeszcze drobna pułapka, która każe za n wziąć \(\displaystyle{ 3^{2k}}\), gdyż inaczej układ przy k=0 ma niecałkowite rozwiązanie.

No nie do końca, gdyż k jest liczbą całkowitą dodatnią.

[Wiesiek7]

Ja właśnie nie zrobiłem obu geometrii i 3. Nie było klasycznej teorii liczb (No 3, ale to nie takie standardowe moim zdaniem). Ale przynajmniej świetnie się bawiłem i dużo sie nauczyłem

[Pinionrzek]

Jak ktoś pomyślał o zadaniu 6. z poprzedniego II etapu, to wnioski w dzisiejszej geometrii same się nasuwały- trzeba było dorysować równoległobok, a z tego już pykała teza. 4. zadanie było proste, ale też nie do konca trywialne. Z kolei 6. to trochę wredna opisówka i mam przeczucie, że poleci sporo zer za nie, bo łatwo przyblefic.