[LX OM] I etap

[limes123]

Daje tu tylko jest problem z S (tzn latwo sie domyslic o ktore chodzi ale nie sadze zeby komisja brala to pod uwage).

... d858c.html
... a62d5.html
http://www.fotosik.pl/pokaz_obrazek/pel ... ecff0.html

Robil ktos jeszcze inna metoda niz analitycznie?

[neecos]

Z tej serii 6 i 8(analitycznie). Mógłby ktoś chociaż sam zamysł rozwiązania 5 indukcyjnie przytoczyc? :> Jak ograniczyc ze nie moze byc wiecej niz 2n-1 (bez pustego) ?

[Dumel]

u mnie to wyglądało tak (z ta roznica ze wliczylem zbior pusty):
1. dla n=1 i n=2 wiadomo
2. wywalmy tymczasowo zbior {1,2,...n}. Pozostaly zbiory co najwyżej n-1 elementowe. Weźmy największy podzbior oraz wszystkie jego podzbiory w optymalnym podziale i oznaczmy je przez X. na mocy poprzednich 2 zdań to co nam zostało- Y nie jest zbiorem pustym. Kazda liczba nalezaca do dowolnego zbioru w X nie nalezy do zadnego zbioru w Y.
3. korzystam z zalozenia indukcyjnego i obliczam liczbe pozdbiorow. dla pewnego k:
\(\displaystyle{ 2k-1+2(n-k)-1+1=2n-1}\) - na koncu dodaje 1 bo wczesniej wywalilem zbior {1,2,...,n}

[Piotr Rutkowski]

Ktora czesc tego rozwiazania nie jest szkolna?

1. Indukcja?
2. Podzielnosc w(a)-w(b) przez a-b?
3. Rozwiazanie nierownosci liniowej z modulem?

Nieszkolne byloby, gdyby uzywalo pojec, twierdzen spoza zakresu szkoly. Tu nawet rozumowanie jest prymitywne, zadnych niezmiennikow, zamieniania kolejnosci sumowania, szufladek, grafow etc.

Fakt, ze strasznie dlugie, ale to w zapisie, bo w glowie krotkie.

Jesli czegos z tego rozwiazania nie miales w szkole i to w pierwszych jej 8-9 latach, to mozesz np. napisac list ze skarga do ministra.

Mogę się zgodzić, że "szkolne" jest np. zadanie 6, a w 7 wybitnie "nieszkolny" jest stopień skomplikowania. Równie dobrze w ten sposób mogę sobie powiedzieć, że szkolne jest zadanie \(\displaystyle{ n|2^{n}-1}\), bo metody tu wykorzystane opierają się o proste własności liczb całkowitych...

Piotrusg niestety nie rozumiem rozwiązania (ze względu na trochę niejednoznaczny i nieestetyczny zapis), a co do rozwiązania kubek1 niezbyt chyba dla mnie jest jasne, dlaczego to nasze \(\displaystyle{ b_{n}}\) miałoby być stałą...

[Sylwek]

kubek1, Twoje rozwiązanie do 7. wygląda na blef, w każdym razie co najmniej jest ono bardzo zamotane, np.:

Ponieważ \(\displaystyle{ b_n}\) jest niezależne od \(\displaystyle{ f_n}\)

Przecież mając dane n dopasowujemy k tak, aby: \(\displaystyle{ W(k)=f_n}\), zatem gdy: \(\displaystyle{ k=tf_n+b_n}\), to \(\displaystyle{ b_n}\) zależy od n, czyli zależy od \(\displaystyle{ f_n}\) i to w sposób oczywisty.


A rozwiązanie 7. rzeczywiście nie było takie trudne, szkoda, że już na samym początku stwierdziłem, że w sposób podany przez xiikzodz wyjdzie mi masa przypadków (nie uwzględniłem lematu \(\displaystyle{ (a-b)|W(a)-W(b)}\) tylko próbowałem rozkładać \(\displaystyle{ W(x)-x}\) z twierdzenia Bezout, co nie mogło się udać). A szkoda, bo jak przyjmując, że stopień tego wielomianu jest większy bądź równy 2, już potem łatwo dostawało się sprzeczność, spróbuję sobie przypomnieć mój dalszy dowód...


No więc mamy łatwo sprawdzić przypadki wielomianu liniowego i kwadratowego, dalej: \(\displaystyle{ W(0)=0, W(1)=1}\), a: W(a)=2 => \(\displaystyle{ (a-1)|(W(a)-1)=1 \Rightarrow a-1=1 \vee a-1=-1 \iff a=2 \vee a=0}\) - dla \(\displaystyle{ W(0)=0 \neq 2}\), stąd: a=2: \(\displaystyle{ W(2)=2}\), itp., stąd: \(\displaystyle{ W(x)-x=x(x-1)(x-2)Q(x) \Rightarrow W(x)=x \left( (x-1)(x-2)Q(x) + 1 \right)}\)


Pokażemy indukcyjnie (nie wprost, czyli przypuśćmy, że \(\displaystyle{ Q(x) \neq 0}\)), że \(\displaystyle{ W(k_n)=f_n \Rightarrow Q(k_n)=0}\), no więc (niech \(\displaystyle{ k_3=b}\)):
\(\displaystyle{ W(b)=f_3=3 \Rightarrow 3=b \left( (b-1)(b-2)Q(b)+1 \right)}\), stąd: \(\displaystyle{ b \in \lbrace -3,-1,1,3 \rbrace}\), widzimy, że tylko dla b=3 jest ok - musi być wówczas Q(b)=0, stąd: \(\displaystyle{ Q(x)=bP(x)}\)


I teraz wykonując tą operację określoną ilość razy dostajemy z założenia indukcyjnego:
\(\displaystyle{ W(x)=x \left( (x-1)(x-2)\ldots(x-f_n)T(x)+1 \right}\), czyli: \(\displaystyle{ |W(x)|=|x| \cdot |\left( (x-1)(x-2)\ldots(x-f_n)T(x)+1 \right)|}\), gdzie: \(\displaystyle{ Q(x)=(x-f_3)\cdot \ldots (x-f_n) \cdot T(x)}\)


Teraz krok indukcyjny (przy dość luźnych szacowaniach jakie użyję, działa on dla \(\displaystyle{ n \ge 7}\), z łatwością można to zrobić dokładniej), czyli: \(\displaystyle{ W(k_{n+1})=f_{n+1} \Rightarrow Q(k_{n+1})=0}\). Jeszcze uwaga: wszystkie liczby \(\displaystyle{ k_i}\) są parami różne (z definicji funkcji - jeden argument -> jedna wartość) [dla zapisu przyjmę: \(\displaystyle{ k_{n+1}=s}\)]. Postaram się dowieść, że \(\displaystyle{ T(s) \neq 0 \Rightarrow W(s)>f_{n+1}}\) - co będzie sprzecznością.


Przypuśćmy, że \(\displaystyle{ |T(s)| \ge 1}\), stąd: \(\displaystyle{ f_{n+1}=|W(s)|=|s| \cdot | \left( (s-1)(s-2)\ldots(s-f_n)T(s)+1 \right)| \ge |\left( (s-1)(s-2)\ldots(s-f_n)T(s)+1 \right)| \ge |(s-1)(s-2)\ldots(s-f_n)T(s)|-1 \ge |(s-1)(s-2)(s-f_{n-1})(s-f_n)|-1 = |(s-1)(s-f_{n})| \cdot |(s-2)(s-f_{n-1})| -1 \ge |f_n - 2| \cdot |f_{n-1} - 3|-1 = (f_n-2)(f_{n-1}-3)-1}\)


Po drodze skorzystałem z wielu nierówności np. z tego, że dla s, \(\displaystyle{ f_n}\) całkowitych minimalną wartością wyrażenia (różną od zera): \(\displaystyle{ |(s-1)(s-f_n)|}\) jest \(\displaystyle{ |f_n-2|}\) itp. - każda jest prosta do wyprowadzenia, w końcu wiadomo co chcemy osiągnąć w kroku indukcyjnym.


Pozostaje dowieść, że dla \(\displaystyle{ n \ge 6}\) zachodzi: \(\displaystyle{ (f_n-2)(f_{n-1}-3)-1 > f_{n+1}}\) - np.: \(\displaystyle{ f_n=k, f_{n-1}=m}\) i: \(\displaystyle{ (k-2)(m-3)-1 >k+m \iff km-4k-3m+5 >0 \iff k(m-4) - 3m+5>0}\), ale: \(\displaystyle{ k(m-4)-3m+5 \ge f_6 (m-4)-3m+5 = 13(m-4)-3m+5=10m-47 \ge 10 f_5 - 47 =33>0}\)

Stąd Q(x)=0 dla nieskończenie wielu argumentów, czyli jest zerowy. Czyli: \(\displaystyle{ W(x)-x=0 W(x)=x}\) - pamiętając o symetrii i początkowych założeniach \(\displaystyle{ W(x)= x a, \ a \mathbb{Z}}\).


P.S. Michaln90, jesteś bardzo zabawny. Piszesz: "Co do 7. to widzę że xiikzodz ma pewnie dobrze (rozwiązanie właściwie identyczne z moim)", a trzy posty dalej: "Bez kitu w tamtym dowodzie jest luka". No ale nic, nie mnie wysnuwać tezy

P.S.2. Mam nadzieję, że nie zamieszałem za bardzo. Jakby były jakieś pytania, to proszę pytać, jednak wydaje mi się, że wzorcówka będzie podobna do tego rozwiązania lub tego z poprzedniej strony.

P.S.3. Coś w tym jest, że jeśli nie jest się pewnym swojego rozwiązania z zadania o wielomianach bądź funkcji, to najprawdopodobniej jest to blef

[lukasz_650]

Ja zrobiłem zadanie ósme inaczej niż wszyscy i nie analitycznie
Też pokazuję, że proste wyznaczone przez odpowiednie rzuty prostokątne punktu H na AB, BC, CD i DA przecinają się w jednym punkcie (oznaczmy go jako P) lub są równoległe, jednak wykorzystuję do tego twierdzenie Menelaosa. Następnie z twierdzenia odwrotnego do twierdzenia Menelaosa, pokazuję, że punkty K, L i P są współliniowe i analogicznie, że M, N i P są współliniowe, co kończy dowód.

[*Kasia]

P.S.3. Coś w tym jest, że jeśli nie jest się pewnym swojego rozwiązania z zadania o wielomianach bądź funkcji, to najprawdopodobniej jest to blef

Zawsze dobrze spróbować. A nuż się trafi, a jak nie, to chociaż komisja będzie miała lekturę.

[limes123]

lukasz mozesz wrzucic szkic swojego rozwiazania? I moze mi ktos powiedziec czy moge liczyc na jakies punkty za moje?

[Piotrusg]

5 mozna tak jeszcze popchnac indukcja dla n=1 jest tego 2n-1 ok dla n=k ma byc max zauawzmy ze jak jest ich max to musimy utworzyc zbior wszystkoelementowy {1,2,3...k} i niech tego bedzie 2k-1 to mamy wykazac ze dla n=k+1 jest tego max 2k+1. Stad mamy pokazac ze tylko 2 nowe podzbiory da sie stworzyc. Istotnie zawsze zbiory {k+1} i {1,2,3.....k+1} spełniaja warunki zadania wiec pozostaje pokazac ze nie da sie juz utworzyc innego podzbioru. Załozmy ze sie go da stworzyc to bedzie on wowczas przynajmniej 2-elementowy ale co najwyzej k elementowy. niech ma postac {a....k+1} gdzie a to liczba nalezaca do zbioru {1,2,3.....k} Stad podzbiory {a....k+1} i {1,2,3......k} nigdy nie spełniaja warunkow zadania bo a jest elementem wspolnym a zawierac sie w sobie nie moga wiec faktycznie nie da sie utworzyc wiecej niz 2k+1 podzbiorow a zatem odp wynosi 2n-1

[kubek1]

Cytat:

Ponieważ b_n jest niezależne od f_n

Przy podstawieniu robiłem założenie, że t jest ustalone, a \(\displaystyle{ b_n}\) jest liczbą całkowitą niezależącą od \(\displaystyle{ f_n}\). Bo gdyby zależało od \(\displaystyle{ f_n}\), to bym mógł tą liczbę przedstawić w postaci: \(\displaystyle{ b_n=cf_n+d_n}\), gdzie c jest ustalone, a \(\displaystyle{ d_n}\) nie zależy od \(\displaystyle{ f_n}\). Wtedy \(\displaystyle{ k=tf_n+cf_n+d_n=(t+c)f_n+d_n}\) i na jedno wychodzi.

Sylwek napisał/a:
P.S.3. Coś w tym jest, że jeśli nie jest się pewnym swojego rozwiązania z zadania o wielomianach bądź funkcji, to najprawdopodobniej jest to blef


Zawsze dobrze spróbować. A nuż się trafi, a jak nie, to chociaż komisja będzie miała lekturę.

Zgadzam się z Kasią Może będą dwa punkty za samą próbę

[andkom]

2. Na mocy (F) \(\displaystyle{ w(1)=\pm 1}\), bo
jesli \(\displaystyle{ w(x)=1}\), to \(\displaystyle{ x=x-0|w(x)-w(0)=1-0=1}\),
wiec zalozmy tez, ze \(\displaystyle{ w(1)=1}\) rozwazajac w razie potrzeby \(\displaystyle{ -w(x)}\).

Zapewne miało być raczej

2. Na mocy (F) \(\displaystyle{ w(1)=1}\) lub \(\displaystyle{ w(-1)=1}\), bo
jesli \(\displaystyle{ w(x)=1}\), to \(\displaystyle{ x=x-0|w(x)-w(0)=1-0=1}\),
wiec zalozmy tez, ze \(\displaystyle{ w(1)=1}\) rozwazajac w razie potrzeby \(\displaystyle{ w(-x)}\).

Zastąpienie w(x) przez -w(x) nie jest dobre, bo nie wiemy, czy oryginalny w przyjmuje dla argumentów całkowitych wszystkie wartości postaci \(\displaystyle{ -f_n}\).

[xiikzodz]

Zgadza sie. I jeszcze w przypadku \(\displaystyle{ 0}\) zamiast zastepowac \(\displaystyle{ w(x)}\) wielomianem \(\displaystyle{ w(x-a)}\), nalezy zastepowac \(\displaystyle{ w(x)}\) wielomianem \(\displaystyle{ w(a -x)}\). (Glupio mi bylo 10 razy edytowac.)

Dodatkowo, jesli juz to zapisywac, to lepiej zaczac od pokazania, ze jesli \(\displaystyle{ w(T)=f_{n+1}}\), to \(\displaystyle{ t\ge f_{n-1}}\) i caly dowod przez indukcje poczawszy od \(\displaystyle{ n=2}\). tylko argument nieco inny dla \(\displaystyle{ n}\)

[Swistak]

Wybaczcie mi moje niedouczenie, ale czemu przyjmujecie, że W(0)=0? Wiem, że na 99% macie rację, ale sam chcę wiedzieć, czemu tak można . Jak już wcześniej mówiłem kilka razy nigdy wcześniej nie robiłem zadań z wielomianem takim w postaci funkcji i stąd te moje problemy .

[xiikzodz]

\(\displaystyle{ f_0=0}\), bo tak jest w tresci zadania.

Wszystkie wartosci z ciagu \(\displaystyle{ f_n}\) sa przyjmowane przez wielomian \(\displaystyle{ w}\), w szczegolnosci istnieje liczba calkowita \(\displaystyle{ a}\), taka, ze \(\displaystyle{ w(a)=f_0=0}\).

Jesli wielomian w spelnia warunki zadania, to rowniez wielomian \(\displaystyle{ v(x)=w(a-x)}\), bo zbiory wartosci tych wielomianow osiaganech w liczbach calkowitych sa identyczne.

\(\displaystyle{ v(0)=w(a-0)=w(a)=0}\)

czyli rozwazajac dalej \(\displaystyle{ v}\) zamiast \(\displaystyle{ w}\) mozemy zalozyc, ze badany wielomian zeruje sie w zerze.

[wally]

Piotrusg, ale do otrzymanych wczesniej podzbiorow nie tylko dodajemy nowe ale mozemy usuwac stare i tworzyc nowe, jezeli tego nie opisales to watpie zeby to bylo pelne rozwiazanie.
Zakladam indukcyjnie ze dla n mozemy zrobic 2n podzbiorow (z pustym), no i zakladam ze dla kazdego \(\displaystyle{ k= i tworzyc nowe, jezeli tego nie opisales to watpie zeby to bylo pelne rozwiazanie.
Zakladam indukcyjnie ze dla n mozemy zrobic 2n podzbiorow (z pustym), no i zakladam ze dla kazdego \(\displaystyle{ k= w razie pytan do jakiegos kawalka pisac ^^}\)}\)