LXII Olimpiada Matematyczna I etap

[mariolawiki1]

To są moje rozwiązania zadań z 1 serii:

[Marcinek665]

Zad1:    

Najpierw dowodzimy, że \(\displaystyle{ \sqrt{ab} \notin Q}\), później robimy w ogólności układ równań

\(\displaystyle{ \begin{cases} a+b=4+x \\ 2\sqrt{ab} = \sqrt{7}-x \end{cases}}\), gdzie x jest jakieś wymierne, znowu dowodzimy, ze x jest równe 0 i układ wypluwa nam rozwiązania postaci: \(\displaystyle{ \left(a,b\right) \in \left\{ \left( \frac{1}{2}, \frac{7}{2} \right)\left(\frac{7}{2},\frac{1}{2} \right) \right\}}\)

Zad2:    

\(\displaystyle{ \begin{cases} mn^{2} + 1 \equiv 0 \ (mod \ d) \\ nm^{2} + 1 \equiv 0 \ (mod \ d) \end{cases} \Rightarrow mn(m-n) \equiv 0 \ (mod \ d) \Rightarrow m \equiv n \ (mod \ d)}\), a stąd już łatwo teza. W międzyczasie jeszcze dowodzimy, że \(\displaystyle{ \left(mn,d\right)=1}\)

Zad3:    

Przeliczyłem na wektorkach Iloczyn skalarny = 0, to wektory są prostopadłe - idea rozwiązania

Zad4:    

Indukcyjnie oczywiście, ale dowodu nie chce mi się przepisywać.

adamm - można było rozważyć zbiór \(\displaystyle{ K=\left\{ \sum_{i=1}^{n}a _{i} \alpha_{i} : \alpha_{i} \in \left\{ -1,0,1\right\} \right\}}\), gdzie \(\displaystyle{ a_{i}}\) są wyrazami dobrego n-elementowego podzbioru S. Wtedy mamy \(\displaystyle{ |K| \le 3 ^{n}}\) oraz \(\displaystyle{ |S| \ge 3 ^{n}+1}\) co praktycznie kończy zadanie.

A za rozwalanie od razu w szczególności \(\displaystyle{ a+b=4}\) będzie chyba niestety 2p.

Generalnie zadania z pierwszej serii były bardzo proste, o pierwszym wcale nawet już nie będę mówił. Ale w sumo logiczne, bo w celach 'reklamowych' powinno się znaleźć parę prostszych zadań niż typowo olimpijskie. Próg na razie bym typował na 3 niepełne zadania.

[ordyh]

Hm, a w 2. nie można było po prostu zrobić tak:

Ukryta treść:    

\(\displaystyle{ \begin{cases}
mn^{2} + 1 \equiv 0 \pmod d \cdot m\\
m^2n + 1 \equiv 0 \pmod d \cdot n
\end{cases}\\
\begin{cases}
m^2n^{2} + m \equiv 0 \pmod d \\
m^2n^{2} + n \equiv 0 \pmod d
\end{cases}}\)
po odjęciu stronami
\(\displaystyle{ \begin{cases}
n\equiv m \pmod d
\end{cases}}\)

albo:

Ukryta treść:    

\(\displaystyle{ \begin{cases}
mn^{2} + 1 \equiv 0 \pmod d \cdot m^3\\
m^2n + 1 \equiv 0 \pmod d \cdot n^3
\end{cases}\\
\begin{cases}
m^4n^{2} + m^3 \equiv 0 \pmod d \\
m^2n^4 + n^3 \equiv 0 \pmod d
\end{cases}\\
\begin{cases}
(m^2n)^2 + m^3 \equiv 0 \pmod d \\
(mn^2)^2 + n^3 \equiv 0 \pmod d
\end{cases}\\
\begin{cases}
(-1)^2 + m^3 \equiv 0 \pmod d \\
(-1)^2 + n^3 \equiv 0 \pmod d
\end{cases}\\
\begin{cases}
1 + m^3 \equiv 0 \pmod d \\
1 + n^3 \equiv 0 \pmod d
\end{cases}}\)

Co do 3. to podoba mi się rozwiązanie mariolawiki1 ideę początkową miałem nawet podobną, zrobiłem równoległobok przez połączenie środków wszystkich boków czworokąta ABCD, a dalej to wprowadzenie kilku kątów i tw. Talesa.

[Marcinek665]

Zadanie 2 można jeszcze tak:
\(\displaystyle{ \left( m ^{2} n + 1\right) \left( n ^{3} + 1 \right) \equiv 0}\)
\(\displaystyle{ m ^{2}n^{4} + m ^{2} n + n ^{3} + 1 \equiv 0}\)

Ale \(\displaystyle{ \left( n ^{2} m + 1\right)\left( n ^{2} m - 1\right) = m ^{2}n^{4} - 1 \equiv 0}\)

\(\displaystyle{ m ^{2}n^{4} + m ^{2} n + n ^{3} + 1 = \left(m ^{2}n^{4} - 1 \right) + \left( m ^{2} n+1\right) + n ^{3} + 1 \equiv 0}\).

Pierwszy i drugi nawias przystaje do 0, więc \(\displaystyle{ n ^{3} + 1 \equiv 0}\)

Rozwiązanie nie moje.

[smigol]

Pierwsze wiadomo jak, tylko od razu porównywałem części wymierne i niewymierne (uznałem, że często się to stosuje, więc nie powinni się czepiać), wcześniej pokazując, że pierwiastek z ab nie może być wymierne.

Drugie: podniosłem stronami do kwadratu jedną kongruencję, dalej wiadomo.

Trzecie: Niech P i Q będą środkami boków odpowiednio BC i AD. Czworokąt MNPQ jest równoległobokiem, jeśli AC=BD to jest rombem, dalej wiadomo. Jeśli tam jest kąt prosty, to dowodzimy, że równoległobok jest rombem.

Czwarte: Indukcja (dla k=0 działa) wystarczy dobrać x różne od zera, ale możemy to zrobić, bo liczność zbioru, z którego dobieramy x jest większa od 1.
Potem korzystając z założenia indukcyjnego itd. Konstruujemy zbiór \(\displaystyle{ S_{k+1}=S_k+{\omega}}\) ze zbioru \(\displaystyle{ X_{k+1}, \ |X_{k+1}| \ge 3^{k+1}+1}\).
\(\displaystyle{ S_k}\) z założenia zawsze możemy wybrać, a chcemy dodać jakieś \(\displaystyle{ \omega}\) do tego zbioru i skonstruujemy szukany zbiór, no to gdybyśmy nie wybrali odpowiedniego \(\displaystyle{ \omega}\), to dla pewnych dwóch zbiorów byłoby: \(\displaystyle{ s_{i_1}+s_{i_2}+...+s_{i_n}+\omega=s_{j_1}+s_{j_2}+...+s_{j_m}}\), czyli \(\displaystyle{ \omega}\) musiałoby być postaci \(\displaystyle{ \sum_{i=1}^{k+1}a_is_i}\), gdzie \(\displaystyle{ a_1 \in \left\{-1,0,1 \right\}}\), no ale liczb postaci \(\displaystyle{ \sum_{i=1}^{k+1}a_is_i}\) jest \(\displaystyle{ 3^{k+1}}\), a liczbę \(\displaystyle{ \omega}\) wybieramy ze zbioru o większej liczbie elementów, więc zawsze możemy dobrać odpowiednie \(\displaystyle{ \omega}\).

[Big ?eb]

Mam takie pytanie. W swoim rozwiązaniu zadania 1 napisałem tak:

Ukryta treść:    

\(\displaystyle{ a+b - 4 = \sqrt{7} - 2 \sqrt{ab}}\)
Po lewej stronie równości mamy liczbę wymierną. Po prawej stronie od \(\displaystyle{ \sqrt{7}}\) (który jest liczbą niewymierną) odejmujemy jakąś liczbę, czyli możemy otrzymać tylko liczbę niewymierną lub zero. dlatego:
\(\displaystyle{ a+b - 4 = \sqrt{7} - 2 \sqrt{ab} = 0}\)

Trochę to moje wytłumaczenie wydaje mi się naciągane, dlatego chciałbym się dowiedzieć co wy o tym sądzicie .

Drugie zrobiłem bardzo podobnie jak w pierwszym rozwiązaniu podanym przez ordyha.
W trzecim dorysowałem dwie proste prostopadłe do dwusiecznej, każda przechodziła przez jeden z wierzchołków czworokąta i później w jedną stronę równoważności szło z Talesa, a w drugą stronę z odwrotnego Talesa.
W czwartym zrobiłem indukcyjnie.

W ogóle jestem zszokowany, że udało mi się zrobić wszystkie zadania (pewnie nie idealnie, ale wszystkie) . W zeszłym roku szło mi o wiele gorzej.

[Dumel]

błędne rozumowanie. mozemy np. od \(\displaystyle{ \sqrt{7}}\) odjąć \(\displaystyle{ \sqrt{7}-1}\) dostając liczbę wymierną.

[Big ?eb]

Prawda :/. Cóż, mam nadzieję, że ten głupi błąd nie zaważy o moim przejściu lub nie.

[kubus1353]

w sumie, wśród tych zadań z pierwszej serii, najtrudniejsze było zadanie 1. Na pierwszy rzut oka było oczywiste, jednak dowód już nie taki prosty. Sądzę, że na tym zadaniu największa liczba osób potraci punkty (z pierwszej serii oczywiście).

[smigol]

Jaki dowód nie był prosty? że ab nie może być kwadratem liczby wymiernej? Dalej tylko porównywanie części wymiernej i niewymiernej, standard, nawet zadanie maturalne mogłoby takie być (patrz zad. 11 na stronie 89 z czerwonej książki do matury)

[Luxxar]

Hah! Jak tak czytam rozwiązania to chyba tylko 1. mam dobrze zrobione ;]

2.Udowodniłem (albo i nie) tak że przyjąłem :\(\displaystyle{ n=m+k}\)
podstawiłem i odjąłem \(\displaystyle{ m^3+m^2k+1 = ad}\) i \(\displaystyle{ m^3+2km^2 +k^2m+1=bd}\)
po odjęciu zostało mi \(\displaystyle{ km(k+m)=(b-a)d}\) \(\displaystyle{ k+m=n}\) więc samo nie może być podzielne przez \(\displaystyle{ d}\)
a później wracając do \(\displaystyle{ m^3+m^2k+1 = ad}\) ,\(\displaystyle{ m^2k}\) musi być podzielne co wcześniej "udowodniłem" więc \(\displaystyle{ m^3+1}\) też musi być podzielne ?

3.
Tutaj zauważyłem że MN jest równoległe do dwusiecznej kąta AEB czyli jest równoległe do dwusiecznej kąta BEC ^^ "Udowodniłem" to kątami przystającymi. (dałem tam też wzmiankę o rombie ale nie wiem czy to miało sens)

4. Tu kompletnie źle zrobiłem , nie wiem nawet jak rozwiązywać zadania przez indukcję.
Ale przyjąłem że skoro
np.\(\displaystyle{ k=1}\)
\(\displaystyle{ S={a,b}}\) \(\displaystyle{ a,b \in C}\)
\(\displaystyle{ A={a}}\) \(\displaystyle{ a \neq 0}\)
\(\displaystyle{ B=puste}\)
jeśli \(\displaystyle{ A=0}\) to
\(\displaystyle{ A={b}}\)
\(\displaystyle{ B=puste}\)

\(\displaystyle{ k=2}\)
\(\displaystyle{ S={a,b,c}}\) \(\displaystyle{ a,b,c \in C}\)
\(\displaystyle{ A={a}}\) \(\displaystyle{ a \neq 0}\)
\(\displaystyle{ B=puste}\)
jeśli \(\displaystyle{ A=0}\) to
\(\displaystyle{ A={b}}\)
\(\displaystyle{ B=puste}\)
i tak dalej xd
Wiedziałem że to zadanie nie może być tak proste ;x


Macie jakieś propozycje jak mógłbym się lepiej przygotować do dalszych zadań?

[smigol]

Tutaj zauważyłem że MN jest równoległe do dwusiecznej kąta AEB czyli jest równoległe do dwusiecznej kąta BEC

Tak średnio, bo nawet te proste 'równoległe' się przecinają.

[ordyh]

Chyba literówka po prostu, chodzi że jeśli prostopadłe do jednej, to równoległe do drugiej dwusiecznej, to idzie od razu z rachunku po kątach, 2 kąty dają 180 stopni, a my bierzemy połówki czyli 90 stopni, czyli są prostopadłe. Mi było łatwiej udowadniać równoległość z BEC niż prostopadłość z AEB

[Asade]

Mam pytanie czy taki dowód zadania 2 jest poprawny?

\(\displaystyle{ (mn^2+1)*m^3=m^4n^2+m^3}\) jest podzielne przez d
\(\displaystyle{ (m^2n+1)*m^2n=m^4n^2+m^2n}\) jest podzielne przez d
\(\displaystyle{ (m^2n+1)*2=2m^2n+2}\) tak samo
\(\displaystyle{ (m^2n+1)^2=m^4n^4+2m^2n+1=(m^4n^2-1)+(2m^2n+2)}\) suma dwóch liczb całkowitych jest podzielna przez d
\(\displaystyle{ m^4n^2+m^3-(m^4n^2-1)=m^4n^2-m^4n^2+m^3+1=m^3+1}\) więc \(\displaystyle{ m^3+1}\) jest podzielne

i poźniej analogicznie dla n^3+1

[Panda]

Ej, wiecie, że poczty do 24 są czasem czynne ;d ? Ja wczoraj nadałem o 22:30, ale jakbym poczekał 30 minut już bym miał podpowiedź (dodałbym np odrębny przypadek dla d = 1 w drugim bo chyba brak tego będzie błędem).
y
Co do zadań:
1.

Ukryta treść:    

Tak jak wszyscy chyba

2.

Ukryta treść:    

Użyłem tej wersji z odejmowaniem, później mamy podobieństwo m i n z którego wynika teza.

3.

Ukryta treść:    

Krótko mówiąc, narysowałem takie odcinki że otrzymałem dwa trójkąty prostokątne o jednym boku tej samej długości, jeden o przeciwprostokątnej AC a drugi BD oraz jeden z kątem \(\displaystyle{ \alpha}\) a drugi \(\displaystyle{ \beta}\). Tezę widać, i to w dwie strony.

4.

Ukryta treść:    

Indukcja. Jeśli dla \(\displaystyle{ k}\) działa to dla \(\displaystyle{ k+1}\) również działa, i to na zbiorze \(\displaystyle{ S_{k+1}}\) równym \(\displaystyle{ S_{k} + {x}}\), gdzie \(\displaystyle{ x}\) to wybrany element z tego zbioru o mocy większej niż \(\displaystyle{ 3^{k}}\) - nazwijmy go \(\displaystyle{ D}\). Zauważamy, że jest tak - zgodnie z Dirichletem - że teza jest spełniona, gdy w zbiorze D jest więcej elementów niż wszystkich różnych różnic sum wszystkich różnych kombinacji różnych zbiorów \(\displaystyle{ A,B}\) takich, że \(\displaystyle{ A,B \subseteq S}\) (oczywiście w \(\displaystyle{ S}\) nie ma \(\displaystyle{ x}\)). Nie uda nam się jednoznacznie określić ile jest takich par, ale zauważamy, że jeśli istnieje niepusty \(\displaystyle{ G}\) taki, że \(\displaystyle{ G \subseteq A}\) i \(\displaystyle{ G \subseteq B}\) to \(\displaystyle{ A - G = B - G}\). Wynika z tego, że jeśli łączna ilość par A,B takich, że są one wzajemnie rozłączne jest mniejsza niż moc D teza jest spełniona.

To, co wyżej napisałem zajęło mi 1,5 strony Ciekawe, czy ktoś załapał, bo ja nie dałem rady odczytać żadnego rozwiązania 4

Jedziemy dalej.

Pozostaje znaleźć wzór na to ile dla danego zbioru S jest par rozłącznych zbiorów \(\displaystyle{ A,B \subseteq S}\). Załóżmy, że \(\displaystyle{ A}\) i \(\displaystyle{ B}\) jest jedną z takich par. Zauważmy, że każdy element ze zbioru S albo należy do A, albo do B, albo nie należy do żadnego z nich. I teraz zgodnie z zasadami kombinatoryki (nie wiem jak to inaczej uzasadnić/udowodnić, nie miałem czasu po 21 wczoraj o tym myśleć a teraz nie chce mi się ) wnioskujemy, że ilość takich par jest równa \(\displaystyle{ 3^k}\). Widzimy, że jest to mniejsze niż moc zbioru D, zatem - zgodnie z wcześniejszym wnioskiem - kończymy dowód.

@Luxxar: Chyba nie zrozumiałeś treści, sam się gubiłem na początku jak zaczynałem myśleć nad tym wspaniałym zadaniem - ze zbioru o mocy 3^k +1 bądź więcej da się wybrać taki S o mocy k+1 (bez powtórzeń), że suma elementów każdego zbioru zawierającego się w S jest inna

Czółko.