IMO 2011

[ElEski]

Na IMO życie się nie kończy (ani nie zaczyna).

Nie daję głowy za prawdziwość, ale słyszałem plotę, że kiedyś na IMO znaleziono serbską parę w łóżku, więc z tym zaczynaniem życia, to możesz nie mieć racji

Moje rozwiązanie pierwszego, jakby ktoś nie umiał odczytać tego, co tam Wojtek nabazgrolił - chociaż tutaj też jest mętlik, bo zjadło indeksy dolne przy kopiowaniu.. w każdym razie indeksy dolne to te cyferki, które są po literkach . No, albo ai, aj, Sn. i,j,n to indeksy dolne w tym wypadku.



Dobra para- taka para liczb \(\displaystyle{ ai, aj,}\) że \(\displaystyle{ ai+aj}\) dzieli \(\displaystyle{ Sn}\)
Bez straty ogólności możemy przyjąć, że \(\displaystyle{ a1<a2<a3<a4}\). Pierwsze co zauważamy to to, że pary \(\displaystyle{ a2,a4}\) i \(\displaystyle{ a3,a4}\) nie nadają się do spełnienia warunków na „dobrą parę” w zadaniu, gdyż \(\displaystyle{ a2+a4}\) jest większe niż połowa \(\displaystyle{ Sn,}\)ale mniejsze niż \(\displaystyle{ Sn}\), tak samo \(\displaystyle{ a3+a4.}\)
Zatem każdy zbiór \(\displaystyle{ 4}\) różnych liczb całkowitych będzie zawierał maksymalnie \(\displaystyle{ 4}\) dobre pary. Pokażę, że będą takie, które zawierają \(\displaystyle{ 4}\), np. zbiór liczb \(\displaystyle{ 1,5,7,11.}\) Teraz zadanie prosi nas o to, żeby wyznaczyć wszystkie takie zbiory spełniające warunki zadania, w których będą \(\displaystyle{ 4}\) dobre pary.
Zapiszę podzielności, które muszą zachodzić w takim zbiorze:
1.)\(\displaystyle{ a1+a2}\) dzieli \(\displaystyle{ a3+a4,}\)
2.)\(\displaystyle{ a1+a3}\) dzieli \(\displaystyle{ a2+a4,}\)
3.)\(\displaystyle{ a1+a4}\) dzieli \(\displaystyle{ a2+a3,}\)
4.)\(\displaystyle{ a2+a3}\) dzieli \(\displaystyle{ a1+a4.}\)
Dlaczego tak napisałem? Bo jeśli np. \(\displaystyle{ a1+a2}\) dzieli \(\displaystyle{ Sn}\), to także dzieli \(\displaystyle{ a3+a4,}\)jest to łatwe do zauważenia i równoważne sobie.

No dobra. Co teraz się rzuca w oczy? Podzielność 3) i 4). Aby obie były spełnione, musi być \(\displaystyle{ a1+a4=a2+a3}\), stąd wniosek, ze \(\displaystyle{ a1+x=a2, a3+x=a4}\) (\(\displaystyle{ x}\) to jakaś liczba całkowita dodatnia)
Czyli odstępy między liczbami \(\displaystyle{ a1}\) i \(\displaystyle{ a2}\), a także między liczbami \(\displaystyle{ a3}\) i \(\displaystyle{ a4}\)są równe \(\displaystyle{ x}\) (tak je nazwaliśmy)
Ponadto odstęp między liczbami \(\displaystyle{ a2}\) i \(\displaystyle{ a3}\) nazwę y. \(\displaystyle{ (a2+y=a3)}\)
Uporządkuję to ładnie:
• \(\displaystyle{ a1=a1,}\)
• \(\displaystyle{ a2=a1+x}\)
• \(\displaystyle{ a3=a1+x+y}\)
• \(\displaystyle{ a4=a1+2x+y}\)
Ok. Teraz patrzymy na podzielność 2).
Podstawiamy pod \(\displaystyle{ a1, a2, a3, a4}\) te ładne sumki, które przed chwilą napisałem.
Wychodzi: \(\displaystyle{ 2a1+x+y}\) jest dzielnikiem \(\displaystyle{ 2a1+3x+y.}\)
Stąd także \(\displaystyle{ 2a1+x+y}\) jest dzielnikiem \(\displaystyle{ 2x}\). Obie te liczby są dodatnie, a także \(\displaystyle{ 2a1+x+y}\) jest większe niż \(\displaystyle{ x}\), stąd\(\displaystyle{ 2a1+x+y=2x,}\) z czego wynika, że \(\displaystyle{ 2a1+y=x.}\)

Dobra. Teraz patrzymy na podzielność 1).
Tak samo podstawiając jest ona równoważna podzielności:
\(\displaystyle{ 2a1+x}\) dzieli \(\displaystyle{ 2a1+3x+2y.}\)
Stąd \(\displaystyle{ 2a1+x}\) dzieli \(\displaystyle{ 2x+2y.}\) I teraz z pomocą przychodzi nam pogrubiony fakt ( ten, który, jak udowodniliśmy, gdyby nie zachodził, to nieprawdziwa byłaby podzielność 2.))
Rozbijamy \(\displaystyle{ x}\)po prawej i lewej na \(\displaystyle{ 2a1+y.}\)
Otrzymujemy: \(\displaystyle{ 4a1+y}\) dzieli \(\displaystyle{ 4a1+ 4y,}\)
Czyli \(\displaystyle{ 4a1+y}\) dzieli \(\displaystyle{ 3y.}\) Obie te wartości, składniki wartości itp. Są dodatnie, stąd:
\(\displaystyle{ 4a1=2y}\) ALBO \(\displaystyle{ 8a1=y.}\)
Sprawdzamy pierwszy przypadek, czyli \(\displaystyle{ 4a1=2y.}\)
Wtedy korzystamy z równości: \(\displaystyle{ 4a1=2y, 2a1+y=x.}\) Łatwo z nich wychodzi, że \(\displaystyle{ x=4a1, y=2a1.}\)
Zobaczymy, czy zbiór, który ma \(\displaystyle{ x=4a1, y=2a1}\) posiada \(\displaystyle{ 4}\) dobre pary.
Jest to ciąg: \(\displaystyle{ a1, 5a1, 7a1, 11a1.}\) Łatwo sprawdzić, że dla każdego a1 ten ciąg ma 4 dobre pary.
Sprawdzamy drugi przypadek, czyli \(\displaystyle{ 8a1=y.}\)
Wtedy tak samo dochodzimy, że \(\displaystyle{ y=8a1, x=10a1}\) . Wówczas zbiór wygląda tak: \(\displaystyle{ a1, 11a1, 19a1, 29a1}\). Od razu widać, że tu nie ma \(\displaystyle{ 4}\) dobrych par. (np. \(\displaystyle{ 8a1}\) nie dzieli \(\displaystyle{ 28a1}\), bo \(\displaystyle{ 8}\) ma większą liczbę dwójek w rozkładzie niż \(\displaystyle{ 28}\)). Zatem wszystkie takie zbiory, dla których liczba dobrych par jest największa to zbiory takie: \(\displaystyle{ a1, 5a1, 7a1, 11a1}\) i \(\displaystyle{ a1, 11a1, 19a1, 29a1}\).

Chyba już nie ma pomyłki

[michaj]

Wyniki zaraz po ostatniej koordynacji:
POL1 (Borowiec): 707771, 29
POL2 (Ciesla): 500720, 14
POL3 (Duleba): 702761, 23
POL4 (Jerzak): 707770, 28
POL5 (Orlef): 710770, 22
POL6 (Porowski): 401771, 20

Na IMO życie się nie kończy (ani nie zaczyna).

Nie daję głowy za prawdziwość, ale słyszałem plotę, że kiedyś na IMO znaleziono serbską parę w łóżku, więc z tym zaczynaniem życia, to możesz nie mieć racji

Dokladnie byla to serbka i grek, w Madrycie, 3 lata temu. Ale ponoc serbska ekipa zaraz po wyladowaniu pytala sie guida o prezerwatywy, wiec o zaczynaniu zycia pewnie nie bylo mowy

[Swistak]

POL5 (Orlef): 710770, 22

Jest szansa, że Damian w końcu urwie to nieosiągalne srebro!

[Marcinek665]

Jest szansa, że Wojtek za rok w końcu urwie to nieosiągalne IMO!

[michaj]

Progi:
zloto 28
srebro 22
braz 16

Tym samym:
Filip i Teodor maja zloto, Damian i Maciek srebro, Wojtek braz i Tomek wzmianka

Druzynowo 136 punktow, 15 miejsce ex aequo z Ukraina.

[Sylwek]

Wielkie słowa uznania dla całej ekipy, w szczególności dla zdobywców najcenniejszych medali

Wyniki: ... ?year=2011

[ElEski]

Brawo dla całej ekipy!
Całkiem ładnie Wam poszło!

A propos, Lisa Sauermann nieźle pojechała
Też chcę mieć 5 medali!

[MateuszL]

Wielkie, wielkie gratulacje dla wszystkich, a szczególne dla Jeżozwierza, bo pamiętam jeszcze jak pisał, że nie szły mu zadania z pierwszej serii OMa dwa lata temu

[Funktor]

ElEski, Biorąc pod uwagę twój wiek to masz szanse pobić jej wynik ;] Ciekawe czy IMC-a też tak wykosi ;]

[bakala12]

Również gratuluję całej polskiej delegacji na IMO i życzę jak najwięcej tak wybitnych osiągnięć.

[me123]

również przyłączam się do gratulacji:)

Wielkie, wielkie gratulacje dla wszystkich, a szczególne dla Jeżozwierza, bo pamiętam jeszcze jak pisał, że nie szły mu zadania z pierwszej serii OMa dwa lata temu

to możliwe? w tak krótkim czasie takie wyniki?

[adamm]

Serdeczne gratulacje dla całej szóstki. W przyszłym roku zanosi się chyba na niezgorszy sukces, trójka medalistów ma jeszcze jeden start.

[Myrthan]

Gratz dla całej naszej ekipy.

Singapur zaskoczył, zważywszy że tam też mają wszyscy jeden start jeszcze to mogą znów bić się o czołówkę.

[AVquiraniel]

Gratulacje, szczególnie dla Filipa i Jerza.

[Swistak]

Wielkie gratulacje dla wszystkich, których satysfakcjonuje ich wynik (czyli na pewno dla Filipa, Jerza, a na pewno nie dla Tomka ; p).

Swoją drogą jak wszedłem na mathlinksa, to i przeleciałem temat o zad. 5, to zauważyłem, że wszystkie rozwiązania tam są kompletnie inne od mojego! Tamte rozwiązania nie mówią prawie nic o wyglądzie tej funkcji, natomiast moje mówi wszystko .

-- 22 lipca 2011, 15:19 --

również przyłączam się do gratulacji:)

Wielkie, wielkie gratulacje dla wszystkich, a szczególne dla Jeżozwierza, bo pamiętam jeszcze jak pisał, że nie szły mu zadania z pierwszej serii OMa dwa lata temu

to możliwe? w tak krótkim czasie takie wyniki?

Jest możliwe, bo zobaczcie, kto jest na 55 miejscu: (2 lata temu).-- 22 lipca 2011, 16:54 --Mimo tego, że ustaję, że jednak z moich zdjęć można przeczytać całkiem sporo, to jednak już któraś osoba mówi mi, że nie da się przeczytać nic, zatem normalnie napiszę swoje rozw. zad. 5 i może jeszcze potem zad. 3.

zad. 5 - niestandardowy sposób, który mówi wszystko o wyglądzie tej funkcji:    

Rozwiązanie jest nie za dobrze zredagowane, ale na pewno złapiecie główną ideę.
\(\displaystyle{ f(m)|f(m)-f(0) \Rightarrow f(m)|f(0)}\), a skoro f przyjmuje tylko wartości dodatnie, w szczególności \(\displaystyle{ f(0)>0}\), to wartości tej funkcji są ograniczone z góry przez \(\displaystyle{ f(0)}\), które jest dzielona przez wszystkie inne jej wartości.
Banalna indukcja daje nam \(\displaystyle{ f(m)|f(km)}\) dla wszystkich całkowitych \(\displaystyle{ k}\) (\(\displaystyle{ f(m)|f(m(k+1))-f(mk)}\)).
Niech W będzie największa wartością, którą f przyjmuje dla argumentów różnych od 0 i niech l będzie liczbą o najmniejszym niezerowym module, dla której \(\displaystyle{ f(l)=W}\). Wtedy dla wszystkich całkowitych k mamy \(\displaystyle{ W=f(l)|f(kl)}\), ale jeżeli k jest niezerowe, to z definicji W mamy \(\displaystyle{ f(kl) \le W}\), czyli \(\displaystyle{ f(kl)=W}\). Jeżeli istniałaby jakaś liczba postaci \(\displaystyle{ kl+r}\), gdzie \(\displaystyle{ 0<|r|<|l|}\), taka że \(\displaystyle{ f(kl+r)=W}\), to mielibyśmy \(\displaystyle{ W=f(kl)|f(kl+r)-f(r)}\), ale \(\displaystyle{ 0=W-W<W-f(r)<W}\), czyli otrzymaliśmy sprzeczność.
Zatem f przyjmuje wartość W w punktach podzielnych przez l (no w 0 jakąkolwiek wielokrotność l) i są to wszystkie punkty, w których jest ona przyjmowana. Ponadto mamy \(\displaystyle{ W=f(kl)|f(kl+r)-f(r) \Rightarrow f(kl+r)=f(r)}\), zatem wartości f na przedziałach długości \(\displaystyle{ l-1}\), (na które przedzieliły nam liczby całkowite podzielne przez l) wyglądają tak samo.
Oczywiście jeżeli m i n będą liczbami podzielnymi przez l, to warunek z tezy zachodzi.
No i teraz chwila skupienia, bo zaczynam mówić rozumowanie, które będę powtarzać, jednak nie chcę mi się myśleć nad ścisłym sformułowaniem indukcyjnym (ale ten krok jest już w sporej części podobny do tego, co już zrobiliśmy).
Niech X będzie największa wartością mniejszą od W przyjmowaną przez f na przedziale [1, l-1] i niech g będzie najmniejszym dodatnim argumentem takim, że \(\displaystyle{ f(g)=X}\). Niech hg będzie najmniejsza wielokrotnością g większą od l. \(\displaystyle{ f(l)|f(hg)-f(hg-l)}\), jeżeli g nie dzieli l, to \(\displaystyle{ hg-l<g \Rightarrow 0<f(hg-l)<X}\), ale z prostych przyczyn \(\displaystyle{ f(hg)=X}\), zatem \(\displaystyle{ W|X-f(hg-l)}\), ale \(\displaystyle{ 0<f(hg)-f(hg-l)<f(hg)=X<W}\), zatem mamy sprzeczność. Zatem g musi dzielić l. Skoro \(\displaystyle{ g|l}\), to \(\displaystyle{ X=f(g)|f(l)=W}\) i proste sprawdzenie dowodzi, że jeżeli m i n są wielokrotnościami g, to warunek z tezy zachodzi. Ponadto \(\displaystyle{ X=f(g) | f(kg) | f(kg+r)-f(r)}\), więc jeżeli \(\displaystyle{ 0<r<g}\), to \(\displaystyle{ f(kg+r)=f(r)}\), zatem wartości f na przedziale \(\displaystyle{ [1, g-1]}\) determinują nam wartości f w całej dziedzinie.
Powtarzamy to rozumowanie tak długo jak możemy, kiedyś na pewno skończymy i otrzymamy analogiczny wniosek, że jeżeli m i n są wielokrotnościami 1, to warunek z tezy zachodzi (musimy po prostu kiedyś dojść do momentu, w którym z punktów, w których jeszcze nie znamy wartości f, największa wartość f przyjmuje w punkcie 1).
c.b.d.u.

To rozumowanie daje nam ogląd na to jak wyglądają wszystkie takie funkcje f spełniające założenia zadania.
Na początku w każdym całkowitym punkcie zadajemy jakąś ustaloną wartość \(\displaystyle{ a_1}\). Potem wybieramy sobie jakieś \(\displaystyle{ a_2}\) oraz \(\displaystyle{ b_1}\) i w całkowitych wielokrotnościach \(\displaystyle{ b_1}\) poprawiamy wartość naszej funkcji na \(\displaystyle{ a_1a_2}\). Następnie wybieramy sobie jakieś \(\displaystyle{ a_3}\) i \(\displaystyle{ b_2}\) i w całkowitych wielokrotnościach \(\displaystyle{ b_1b_2}\) poprawiamy wartość naszej funkcji na \(\displaystyle{ a_1a_2a_3}\). Powtarzamy to tak długo jak chcemy i na końcu jeszcze w zerze ustalamy jakąkolwiek wielokrotność tego, co tam mamy aktualnie.
Przykładowa funkcja, którą możemy otrzymać takim sposobem wygląda np. tak:
\(\displaystyle{ 120, 2, 6, 2, 6, 2, 24, 2, 6, 2, 6, 2, 24, 2}\) (120 to wartość w 0, a potem po kolei).