[LX OM] I etap

[limes123]

W sumie to racja ze ta pierwsza seria taka niewygodna do zapisania. A co do trudnosic to chyba rzeczywiscie 1 i 2 najciezsze.
Swistak, ja nie uwazam 5 i 11 za latwe. 10 wlasciwie tez ale mozliwe ze mamy rozne rozwiazania.

[nivwusquorum]

hmmm... wg mnie 1 najprostsze, no i łatwe do zapisania, tak samo jak 4. 3cie hmm,,, nie jest tak źle, ale za to 2gie mnie przerosło trochę. No w każdym razie czekam na ładny dowód do 2giego i nie idę spać specjalnie w tym celu mimo zmęczenia:p

[ Dodano: 3 Października 2008, 23:20 ]
co tak wszyscy zamilkli?:)

[neecos]

heh tez czekam na ladny dowod 2, moj zajmuje 2 strony i zdecydowanie nie jest zgrabny :C to bylo z 1 serii jak dla mnie najciezsze do opisania zadanie ;/

[Swistak]

W zasadzie to nie wiem, czy mój jest taki zgrabny, ale na pewno zajmuje 2 strony A4 i jestem z niego bardzo usatysfakcjonowany .

A do opisania najtrudniejsze to 1, bo to taka sama pisanina. Najpierw łopatologicznie opisuję pierwsze wnioski, a potem już mi się nie chce i mam małe luki w rozumowaniu, których nie chciało mi się pisać xP.

[nivwusquorum]

Eee pierwsze to kilka prostych wnisków, które bardzo ściśle wynikają z siebie i prowadzą do rozwiązania, nie widzę tam miejsca na luki w rozumowaniu. No chyba, że ktoś coś tam naściemniał:P

[ Dodano: 4 Października 2008, 00:01 ]
No dobra deadline osiągnięty:P Chwalić się:)

[neecos]

1) Wykreslanie wierszy i kolumn w ktorych jest jedna wieza i nie moze byc wiecej, pozniej oszacowanie ze max to m+n i pokazanie ze zawsze istnieje takie ustawienie ze jest m+n wiez na planszy.

2) Kolejno pokazanie ze dla nieparzystych nie dziala, dla parzystych roznych od poteg dwojki nie dziala, oraz na koncu ze dla poteg dwojki jest rzeczywiscie permutacja Ale strasznie zamotane.

3) Pokazanie ze M i N leza na okregu, oraz ze M,D,J leza na jednej prostej, potem poszlo szybko.

4) Podstawienie a^3=x b^3=y c^3 = z, potem dwa razy nierownosc pomiedzy srednia aryt. i geom. i wyszlo

[limes123]

1) podobnie
2) mozna pokazac, ze jak istnieje czynnik nieparzysty w rozkladnie tej liczby to juz nie dziala, i oddzielnie dla 2 do jakiegos calkowitego dodatniego n
3) podobnie
4) ja robilem przez uzupelnienie do kwadratu i tez poszlo

[nivwusquorum]

1) Ze mozna m+n wychodzi ładnie konstrukcyjnie. Ze nie mozna wiecej mozna ladnie rozwiazac w ten sposob:
paskiem nazwiemy taka jednostkowy fragment brzegu szachownicy. Zauwazmy, ze z warunkow zadania kazda wieza musi "widziec" co najmniej dwa paski. A poniewaz wszystkich paskow jest 2(m+n) stąd nie można ustawić więcej jak n+m wież.
2) wciaż czekam na kogoś kto bardziej rozwinie swoje rozwiazanie
3)Ja tam nie zauwazalem zadnego okregu wystarczylo udowodnic, ze D, J, M oraz E, J, N są współliniowe i potem juz trywialnie wychodziło, ze MNJF jest deltoidem.
4) ja podstawialem a=d^2, b=e^2, c=f^2 i wychodzilo bardzo latwo ze sredniej i kwadratu, czy z dwoch kwadratow jak kto woli

[ Dodano: 4 Października 2008, 00:36 ]
Apropo Ciekawi mnie czy ktoś się silił na dowodzenie pierwszego w teorii grafów, bo generalnie bardzo mi się ten problem kojarzy z pokryciem wierzchołkowym w grafie dwudzielnym, ale w sumie nie jestem w stanie sprecyzować na czym polega zależność

[limes123]

Ja pierwsze robiłem indukcja

[allure]

Widzę że specjalnej różnorodności nie ma.

Pierwsze zadanie tak jak nivwusquorum

W drugim trochę się rozpisałem zajeło mi 6 stron. Kluczem do rowiązania było to że jak się napisze dla liczby k reszty od 1 do 2k-2 to można zauważyć że pomiędzy resztami od 1 do k-1 i od k do 2k-2 jest symetria. A potem indukcyjnie, dla k nie zachodzi, jezeli dla k nie zachodzi do dla 2k nie zachodzi jezeli dla 2k nie zachodzi to dla 4k nie zachodzi itd. ale to jest tak w skrócie.

Trzecie zadanie skonczyłem dziś o 21.30 , ale zrobiłem, nie ma jak to zostawiać sobie wszystko na ostatni dzien! Sposób podobny do neecos,

No i czwarte przekształcenia, mógłby ktoś kto zrobił średnimi napisać swój sposób, bo jak na moje gust to średnie były za mocne na tą nierówność, ale mogę i pewnie się mylę.

Według mnie I seria mimo wszystko trudniejsza niż rok temu. Rok temu na wstępie miałem dwa zadanka, jedno zrobilem w trakcie a jednemu nie dałem rady, a trudne nie było. A w tym roku nad kazdym zadaniem równo się namęczyłem i nie rozumiem niektórych osób, które mówiły że zadania za łatwe, takie chyba powinny byc na pierwszym etapie.

Kolejność trudności (od najłatwiejszego): 4, 1, 3, 2

Widzę, że wy już macie odpoczynek, ja we wrześniu się wziałem tylko za I serię. Z zadań od 5-12 jeszcze nic nie mam. Pora się wziąć.

[enigm32]

1. Moje rozwiązanie: (troszkę skrócone)
M - największa liczba wieży...
Łatwo zaobserwować, że jeśli w dowolnym wierszu znajduje się t wież (t≥2), to w odpowiednich t-2 kolumnach znajduje się tylko po jednej wieży (należącej do wcześniej wspomnianego wiersza). Identycznie jest w sytuacji odwrotnej: gdy w dowolnej kolumnie znajduje się s wież (s≥2), to w odpowiednich s-2 wierszach jest po jednej wieży. Wynika to z warunku, że każda wieża może znajdować się w polu rażenia co najwyżej dwóch innych wież.
Na początku uzasadniłem, że przy maksymalnej liczbie wieży na szachownicy, żaden wiersz ani kolumna nie może być wolna oraz, że każda wieża znajduje się w polu rażenia dokładnie dwóch wieży (gdyby było inaczej, to zawsze można dostawić wieżę lub liczba wież jest mniejsza od m+n, a łatwo zauważyć, że \(\displaystyle{ M qslant m+n}\)).
Liczbę kolumn, w których znajdują się po jednej wieży oznaczmy przez k, natomiast liczbę wierszy o tej własności przez liczbę l.
Usuńmy właśnie te kolumny oraz wiersze wraz z wieżami, a pozostałe pola „złączmy” w szachownicę.
Liczba wierszy w otrzymanej szachownicy będzie naturalnie wynosiła n-l, liczba kolumn m-k, natomiast liczba rozstawionych wieży M-k-l.
Oczywiście widzimy, że w każdej kolumnie oraz każdym wierszu otrzymanej w opisany wyżej sposób szachownicy musi znajdować się dokładnie po dwie wieże. Jest to możliwe tylko wtedy, gdy ilość kolumn nowej szachownicy będzie równa ilości jej wierszy:
[Gdyby x - ilość kolumn, y – ilość wierszy i x≠y, to licząc ilość wież na szachownicy na dwa sposoby: sumując wieże wg kolumn oraz sumując je wg wierszy, otrzymalibyśmy, że ich ilość wynosi 2x=2y, co jest sprzeczne z założeniem x≠y.]

Mamy zatem, że: \(\displaystyle{ \begin{cases}2(n-l)=M-k-l\\ 2(m-k)=M-k-l \end{cases}}\) - dodajemy stronami i otrzymujemy:
\(\displaystyle{ M=m+n}\)

Ponoć ładnie można to rozwiązać indukcyjnie. Kumple robili też to uzasadniając, że nie można rozmieścić m+n+1 wież (korzystając m.in. z zasady szufladkowej), jednak nie wiem jak wyglądają pełne rozwiązania tymi metodami.

PS
Gratki dla nivwusquorum oraz tych, którzy rozwiązali zadanie w ten sposób - ładny

[xiikzodz]

2) wciaż czekam na kogoś kto bardziej rozwinie swoje rozwiazanie

Na przyklad:
Jesli \(\displaystyle{ n}\) jest parzyste i ma nieparzysty dzielnik, powiedzmy \(\displaystyle{ n=(2k+1)m}\), \(\displaystyle{ m}\) - parzyste, wowczas:

\(\displaystyle{ r_{km+k} - r_{km-k-1}=km-k + km-k+1 + ... + km + km+1 + ... + km+k = kn}\)

Czyli \(\displaystyle{ n}\) nie spelnia. Teraz powinno byc latwo...

[Sylwek]

1) Zupełnie inaczej niż wszyscy, pokazałem, że m+n się da, jeśli da się m+n+1+k wież, to oczywiście po usunięciu k wież powstaje ustawienie spełniające warunek zadania (dla żadnej wieży nie zwiększyła się liczba bić), czyli składające się z m+n+1 wież, zatem wystarczy udowodnić, że nie da się ustawić m+n+1. A to udowodniłem tak (w skrócie zaprezentuję), jeśli \(\displaystyle{ p}\) to liczba wież w kolumnie/wierszu, to liczba bić w tej kolumnie/wierszu jest \(\displaystyle{ \ge 2p-2}\), sumując to po wszystkich kolumnach i wierszach dostajemy, że łączna liczba bić (równa łącznej ilości pól atakowanych) jest \(\displaystyle{ \ge 2m+2n+4 = 2(m+n+1)+2}\) - zatem z Dirichleta istnieje wieża atakowana przez 3 inne - sprzeczność z założeniem.

2) nieparzyste - istnieje reszta 0
\(\displaystyle{ 2^k l}\) - definiuję: \(\displaystyle{ r_0=0}\), potem mamy:
\(\displaystyle{ i j=\frac{2^{k+1}+m- 1}{2}}\), oczywiście tutaj: \(\displaystyle{ 0 i l}\), w szczególnym przypadku gdy i=0 mamy \(\displaystyle{ r_j=r_i=0}\)
\(\displaystyle{ 2^k}\) się da - nie wprost idzie prosto

3)

Pokazanie ze M i N leza na okregu, oraz ze M,D,J leza na jednej prostej, potem poszlo szybko.

4)

przez uzupelnienie do kwadratu

Dokładniej to przerzucając wszystko na prawą i zwijając otrzymujemy, że nierówność jest równoważna: \(\displaystyle{ \left(2\sqrt{c^3}-\sqrt{a^3}-\sqrt{b^3} \right)^2 + 3ab ft( \sqrt{a} - \sqrt{b} \right)^2 0}\), tego chyba nie trzeba komentować...


Od najprostszego: 4,3,2,1

Przed wysłaniem zeskanowałem swoje rozwiązania. Ponieważ już upłynął czas wysyłania pierwszej serii, to wrzuciłem je na jakiś serwer, aby pokazać kolegom. Pomyślałem, że na forum też ktoś zechcę popatrzeć, jak wyglądają moje rozwiązania :

Kod: Zaznacz cały

http://www.speedyshare.com/125886349.html

[xiikzodz]

Yyy, to jednak dokoncze 2...

Do pokazania, ze \(\displaystyle{ n=2^t}\) spelnia dodajmy \(\displaystyle{ r_0=0}\) oraz rozwazamy roznice \(\displaystyle{ r_i-r_j}\).

Jesli \(\displaystyle{ i-j = 2m+1}\), to

\(\displaystyle{ r_i-r_j=\sum_{i=-m}^m (a +i)=(2m+1)a}\), co nie moze dzielic sie przez \(\displaystyle{ 2^t}\), bo \(\displaystyle{ a}\)

[Rush]

To moze ja w skrocie zaproponuje swoj dowod drugiego:
1) Lemat: Kazda liczbe ktora w rozkladzie na czynniki pierwsze zawiera liczbe nieparzysta (oczywiscie wieksza od 1) mozna przedstawic w postaci sumy kilku kolejnych liczb naturalnych.
2) Dowod lematu.
3) Wykazalem, ze takie liczby nie spelniaja zalozen zadania (powtarza sie reszta)
4) Zatem mamy zbior ograniczony do poteg dwojki
5) Wykazalem, ze nigdy nie otrzymamy reszty 0( w tym celu zastosowalem wzor \(\displaystyle{ 1+2+3+...+x = \frac{x (x+1)}{2}}\) I wykazalem, ze w rozkladzie licznika na czynniki pierwsze nigdy nie otrzymamy o jedna dwojke wiecej niz sama liczba n(wynika to z faktu, ze \(\displaystyle{ max(x+1)=n}\) oraz n rozkada sie tylko na czynniki rowne 2.
6) Pokazalem, ze zadna reszta sie nie powtorzy ( w tym celu zalozylem, ze sie powtorzy, zatem mamy liczby \(\displaystyle{ 1+2+3+...+c i 1+2+3+...+c+...(c+z) zatem 1+2+3+...+(c+z) - (1+2+3+...+c)}\) jest podzielne przez n. Zastosowalem wzor ktory uzylem wyzej, odjalem ladnie, zwinalem i rozpatrzylem dwa przypadki dla z(parzyste/nieparzyste) w obu wyszla sprzecznosc.
W zadaniu pierwszym robilem wykreslajac wiersze/kolumny z jedna wieza, a w zadaniu czwartym zwinalem w nawias kwadratowy przez zastosowanie wzoru \(\displaystyle{ (a+b-c)^2 = a^2 + b^2 + c^2 - 2bc - 2ac + 2ab}\)