[LX OM] I etap

[Swistak]

1. Najpierw banalny dowód, że zawsze da się ustawić m+n wież rozstawiając wieże na dwóch prostopadłych krawędziach i w pozostałym rogu. Potem zakładam, że jest ustawienie, w którym jest m+n+1 wież.
Biorę sobie jakieś b>=0 takie, że m=n+b. Wtedy na planszy n+bxnznajduje się 2n+b+1 wież. Przez nadprogramowe wieże będę nazywać takie wieże, które są atakowane przez 2 inne wieże albo w kolumnie albo w rzędzie. Załóżmy, że n+b to liczba kolumn. W jednym rzędzie mogą się znaleźć maxymalnie 2 nie nadprogramowe wieże. Z tego wynika, że skoro mamy n rzędów, to max będzie 2n wież, które nie są nadprogramowe biorąc pod uwagę wiersze, a więc jest minimum b+1 wież nadprogramowych. Jeżeli wieża jest atakowane przez 2 inne w swojej kolumnie to nie może się znaleźć inna wieża, która jest w tym samym rzędzie co ta nadprogramowa. Z tego wynika, że jak mamy b+1 wież to możemy wyeliminować b+1 kolumn i na planszy n-1xn zostaje nam 2n wież. Dalej patrzymy, że może być max 2(n-1) nie nadprogramowych, a więc 2 są nadprogramowe i zostaje nam plansze n-1xn-2 z 2n-2 wieżami. Dalej powtarzamy poprzedni krok, aż dojdziemy do momentu, w którym zostanie nam plansza 2x3, na której będzie 6 wież, a więc doszliśmy do sprzeczności.
2. Z tego co wychwyciłem to chyba nikt nie robił tak jak ja, albo nie chciało mi się czytać innych dowodów. Za T(a) będę rozumieć a-tą liczbę trójkątną, którą oznacza się wzorem \(\displaystyle{ \frac{a(a+1)}{2}}\). Jeżeli liczbę n da się przedstawić jako T(a)-T(b), gdzie n>a>b>=0 to, któreś dwie reszty się powtórzą albo reszta będzie równa 0 i teza nie będzie spełniona.
1)
n=2c+1=T(c+1)-T(c-1) SPRZECZNOŚĆ
2)
n=2e(2d+1), gdzie 2e to iloczyn dzielników parzystych (wiem, że można to zapisać także jako \(\displaystyle{ 2^{e}}\), ale tak se od poczatku zapisałem i było mi łatwiej, a 2d+2 to iloczyn dzielników nieparzystych. Oczywiście dla 2e>1 i d>0 i dla całkowitych e i d. n=2e(2d+1) co po przekształceniach daje nam n=T(2e+d)-T(2e-d-1)=T(2e+d)-T(d-2e). Pierwszy przypadek jest dobry dla d==2e więc n da się przedstawić w takiej formie dla każdego e i d. SPRZECZNOŚĆ
3) \(\displaystyle{ n=2^{f}}\)T(a)-T(b)=\(\displaystyle{ \frac{(a+b+1)(a-b)}{2}}\). Oczywiście a+b+1 i a-b są różnej parzystości. Jeżeli \(\displaystyle{ 2^{f}}\) ma się równać tej różnicy to \(\displaystyle{ 2^{f+1}=(a+b+1)(a-b)}\) Skoro te dwa czynniki są różnej parzystości to znaczy, że jeden z czynników musi być podzielny przez \(\displaystyle{ 2^{f+1}}\), bo drugi czynnik nie będzie podzielny przez 2. Skoro n>a>b to znaczy, że maxymalne a=n-1 a maxymalne b=n-2, a więc maxymalne \(\displaystyle{ a+b+1=2n-2=2^{f+1}-2}\), a więc \(\displaystyle{ 2^{f}}\) nie da się przedstawić w żądanej formie, a więc \(\displaystyle{ n=2^{f}}\) dla żadnego f nie da się przedstawić w formie różnicy odpowiednich liczb trójkątnych i żadne 2 reszty się nie powtórzą i będą różne od 0.

3 zadania nie ma sensu opisywać, a 4 idzie z tego, że \(\displaystyle{ (\sqrt{3a^{2}b}-\sqrt{3ab^{2}})^{2} + (\sqrt{a^{3}}+\sqrt{b^3}-2\sqrt{c^3})^{2}>0}\)co po prostych przekształceniach daje tezę.

[Sylwek]

O co ci chodzi?

Mimo wszystko pisząc po ludzku pełne nazwy zamiast rzucać hasłami na prawo i lew (nie wiem w jakim celu, bo to co najmniej bezmyślne) unika się komplikacji i niezrozumienia, dobry przykład:

metoda pgr polega na zasąpieniu a+b+c, ab+bc+ac, abc liczbami p,q,r.

[enigm32]

Jeszcze apropos drugiego: wszyscy dwodzą, że nieparzyste przystają do zera gdzieśtam, a parzyste sie powtórzą. A próbował ktoś odwrotnie? Tzn. że nieparzyste się powtórzą, a parzyste przystają do 0. Bo generalnie jestem niemal pewien, że takie coś także zachodzi (niemal = 1000000 pierwszych przypadków sprawdzonych na kompie).

Weźmy najmniejszą z możliwych nieparzystych n=3:
1 :3=0 r. 1
1+2=3 :3=1 r.0
Ciąg reszt: (1;0) - żadna się nie powtarza...

[nivwusquorum]

Hmm... dziwne.... Jeszcze wczoraj się powatarzały. Dziwne te liczby naturalne....

[xiikzodz]

2, 3 i 4 mam podobnie jak reszta, tylko 1 inaczej:

Każda wieża ma zasięg w czterech kierunkach. Każda wieża może przyjąć 2 uderzenia, a w przypadku kiedy będzie maksymalna ilość wież, to każdy odcinek obwodu (jednostkowy) będzie w polu rażenia (oczywiście jednej wieży), a tych odcinków jest 2(m+n). Teraz proste równanie:
\(\displaystyle{ 4 x = 2(m+n) + 2 x}\),
z którego otrzymujemy \(\displaystyle{ x= m+n}\)

To jest idealnie identyczne rozwiazanie z zaprezentowanym przez nivwusquorum i moim zdaniem w ogole najczestsze.

Hmm... dziwne.... Jeszcze wczoraj się powatarzały. Dziwne te liczby naturalne....

Przeczytaj rozwiazanie Sylwka. Jest tam o wiele wiecej, niz potrzeba, w tym warunek z ktorego latwo ustalic, kiedy jest reszta zero, a kiedy powtarzaja sie reszty.

[Elvis]

Jeszcze apropos drugiego: wszyscy dwodzą, że nieparzyste przystają do zera gdzieśtam, a parzyste sie powtórzą. A próbował ktoś odwrotnie? Tzn. że nieparzyste się powtórzą, a parzyste przystają do 0. Bo generalnie jestem niemal pewien, że takie coś także zachodzi (niemal = 1000000 pierwszych przypadków sprawdzonych na kompie).

Weźmy najmniejszą z możliwych nieparzystych n=3:
1 :3=0 r. 1
1+2=3 :3=1 r.0
Ciąg reszt: (1;0) - żadna się nie powtarza...

Prawda. 3 jest jedyną liczbą nieparzystą, dla której się nie powtarza.

[michaln90]

nie rozumiem dlaczego wszyscy rozważają w drugim 3 przypadki. Wystarczą dwa (liczby posiadające dzielnik pierwszy nieparzysty i potęgi liczby 2 o wykladnikach całkowitych dodatnich). Niepotrzebnie komplikujecie sobie dowody.

[Sylwek]

Przypadek dla n nieparzystego zajął mi 3 linijki, a rozumowanie w nim miałem inne niż w przypadku gdy mamy liczbę postaci \(\displaystyle{ 2^k l}\), więc na rękę było mi rozważenie go.

[xiikzodz]

Przeciwnie. Oddzielenie przypadku nieparzystego od parzystego z dzielnikiem nieparzystym upraszcza dowod negatywnej czesci do 2 linijek (slownie DWOCH):

Linijka pierwsza:
Jesli n nieparzyste, to \(\displaystyle{ r_{n-1}=n(n+1)/2=0}\) mod \(\displaystyle{ n}\).
Linika druga:
Jesli n parzyste postaci \(\displaystyle{ n=(2k+1)m}\), to \(\displaystyle{ r_{km+k} - r_{km-k-1}=\sum_{i=-k}^k (km-i)=kn=0}\) mod \(\displaystyle{ n}\)

Teraz juz rozumiesz?

[wiktoro]

No 1. zadanie było według mnie najłatwiejsze - wystarczyło przeanalizować brzegi szachownicy. Nierówność w 4. wymagała jedynie wyeliminowania pierwiastków, a później usunięcia c. Zadanie geometryczne jednak mnie przerosło, chociaż widzę, że nie było trudne. Zadanie 2. było dla mnie zbyt trudne do opisania, ale widzę, że niektórzy rozwiązali to bardzo "zgrabnie".

[Piotr Rutkowski]

nie rozumiem dlaczego wszyscy rozważają w drugim 3 przypadki. Wystarczą dwa (liczby posiadające dzielnik pierwszy nieparzysty i potęgi liczby 2 o wykladnikach całkowitych dodatnich). Niepotrzebnie komplikujecie sobie dowody.

Przypadek dla n nieparzystego zajął mi 3 linijki, a rozumowanie w nim miałem inne niż w przypadku gdy mamy liczbę postaci \(\displaystyle{ 2^k l}\), więc na rękę było mi rozważenie go.

Jeden woli matkę, drugi woli córkę...
Dajmy sobie spokój z rozważaniem, który dowód jest prostszy/trudniejszy. Prawdopodobnie obaj macie za 2 6 pkt, więc o co ta cała afera? Założę się, że zad. 3 da się zrobić analitycznie i niektórzy pewnie tak robili, co nie znaczy, że mają je zrobione źle.

[Swistak]

Może, niektóre rozwiązania są zgrabniejsze i krótsze, ale najbardziej przystępne są chyba moje rozwiązania (swoje rozumowania oczywiście rozumiem, a waszych to prawie nic xD).

[Dumel]

a wiecie, tak sobie ostatnio pomyslałem że tegoroczny I etap nie wyróżnia sie chyba wcale specjalnie łatwością spośród pozostałych olimpiad. były oczywiście I etapy wyraźnie trudniejsze (LIII, LVIII) ale pozostałe są na podobnym poziomie (LII) albo nawet troszkę łatwiejsze (LI, LV, LVII). Zawsze teoria liczb była prościutka (zwłaszcza w LI ale w pozostałych też) a teraz mamy nietrudną geometrie więc wychodzi na remis. Co o tym myślicie?

[michaln90]

Jeden woli matkę, drugi woli córkę...
Dajmy sobie spokój z rozważaniem, który dowód jest prostszy/trudniejszy. Prawdopodobnie obaj macie za 2 6 pkt, więc o co ta cała afera? Założę się, że zad. 3 da się zrobić analitycznie i niektórzy pewnie tak robili, co nie znaczy, że mają je zrobione źle.

W sumie to teraz zgadzam się z polskimmiśkiem. Rzeczywiście bez względu na to czy się rozpatrzy 2 czy 3 przypadki rozwiązanie może być krótkie. Zależy to od tego co się zauważy w zadaniu i od tego kto redaguje. Ja na przykład w 2 rozpatrywałem liczbę różnych reszt z dzielenia przez n które są podzielne przez l. Jest ich zawsze 2k(dwa do potęgi k-tej). Nietrudno zauważyć że wśród rozpatrywanych liczb również istnieje dokładnie 2k(dwa do k-tej) liczb podzielnych przez l, a ponieważ liczby te dają różne reszty to wśród nich jest liczba podzielna przez 2k(dwa do k-tej)l.

[ Dodano: 6 Października 2008, 15:31 ]
Sądzę że w tym roku zadania na pierwszym etapie nie różnią się poziomem trudności od zadań z pierwszych etapów 50-59 OM. Na pierwszym etapie zadania są po prostu bardzo łatwe(nie licząc wyjątków takich jak 7. w tym roku, 10 w tamtym, 8,12 dwa lata temu). Jedyne co może wkurzać w zadaniach z I etapu to jak pewnie zauważyliście złożoność dowodów ( rozwiązania nie są tak krótkie i zgrabne jak na II etapie). Ponadto co ciekawe zadania z II etapów są przeważnie dwa razy łatwiejsze niż te z I etapu. Dopiero na finale zaczyna się hardkor( choć i tak zawsze co najmniej dwa są bez problemu do zrobienia, a nawet więcej).

[timon92]

Jesli n parzyste postaci \(\displaystyle{ n=(2k+1)m}\), to \(\displaystyle{ r_{km+k} - r_{km-k-1}=\sum_{i=-k}^k (km-i)=kn=0}\) mod \(\displaystyle{ n}\)

dla \(\displaystyle{ n=6}\) mamy \(\displaystyle{ km-k-1=0}\), więc nie istnieje \(\displaystyle{ r_{km-k-1}}\)