[LX OM] I etap

[michaln90]

ale ten lemat przecież leci w drugą stronę:

Dumel ma rację. Bez kitu w tamtym dowodzie jest luka

[xiikzodz]

Heh, widze, ze trzeba to napisac slowami, bo inaczej ciagle beda watpliwosci:

W dowodzi przez indukcje w zalozeniu indukcyjnym mamy:

\(\displaystyle{ w(f_i)=f_i}\), dla \(\displaystyle{ i=0,1,2,...,n}\)

Owszem, chcemy pokazac, ze:

\(\displaystyle{ w(f_{n+1})=f_{n+1}}\)

ALE

nie probujemy w ogole obliczac \(\displaystyle{ w(f_{n+1})}\)

tylko bierzemy sobie taka liczbe \(\displaystyle{ T}\), ze

\(\displaystyle{ w(T)=f_{n+1}}\)

a dopiero potem okazuje sie, ze \(\displaystyle{ T=f_{n+1}}\).

Czyli te kongruencje sa postaci:

\(\displaystyle{ T-f_i | w(T)-w(f_i)}\)

Teraz

\(\displaystyle{ w(T)-w(f_i)=f_{n+1}-f_i}\)

na mocy definicji \(\displaystyle{ T}\) i zalozenia indukcyjnego. I stad taki a nie inny wyglad tych kongruencji.

W szczegolnosci dla \(\displaystyle{ f_1}\) ta sama procedura:

Niech \(\displaystyle{ w(t)=1=f_1}\)

Wowczas:

\(\displaystyle{ t-0|w(t)-w(0)=1-0}\), czyli \(\displaystyle{ t|1}\), czyli \(\displaystyle{ t=\pm 1}\).


Sadze, ze masz dobrze michaln90, tylko glowa ci psikusa zrobila i odwrocilo ci sie.

[Jelen]

odnośnie 7:

wielomiany postaci
\(\displaystyle{ W(x) = \frac{x+b}{a}}\) dla a,b \(\displaystyle{ \in {Z}}\)

spełniają warunki zadania

ogólnie wielomiany

\(\displaystyle{ {Z} {A}}\) gdzie \(\displaystyle{ {Z} {A}}\)

spełniają warunki zadania

niestety dowód byłby pełny gdybym udowodnił, że jeżeli wielomian przyjmuje nieskończenie wiele wartości całkowitych dla całkowitych x to istnieje w liczbach całkowitych rozwiązanie równia

\(\displaystyle{ W(x) = f _{n}}\)


a co do reszty
5 - indukcja
6 - trójkąty podobne (przystające) i kąty na kole
8 - brak

[xiikzodz]

Rozwiazanie kilka postow wyzej poprawione tak, zeby bylo widac. Faktycznie, sprawdzenie dla 1 bylo dosc niejasne...

Fragment zmieniony wyraznie zaznaczony w pseudotagach [EDIT][EDIT].

Jelen: wielomian \(\displaystyle{ w(x)=x^2}\) przyjmuje nieskonczenie wiele wartosci calkowitych, ale nie wszystkie \(\displaystyle{ f_n}\) sa kwadratami liczb calkowitych.

[Piotr Rutkowski]

Moim zdaniem to wlasnie ludzie, ktorym to zadanie 7 zajelo tydzien myslenia powinni sie pochwalic. Musieli znalezc jakies niesamowicie eleganckie rozwiazania... Mnie zajelo pol godziny, ale rozwiazanie nie zawiera zadnego pomyslu:

Wielokrotnie skorzystam z faktu:

(F) Jesli \(\displaystyle{ w\in\mathbb{Z}[x]}\), to \(\displaystyle{ w(a)-w(b)\in(a-b)\mathbb{Z}}\) dla dowolnych \(\displaystyle{ a,b\in\mathbb{Z}}\).

Redukcje:

1. Mozemy przyjac, ze \(\displaystyle{ w(0)=0}\), w przeciwnym razie rozwazamy \(\displaystyle{ v(x)=w(x-a)}\), dla \(\displaystyle{ w(a)=0=F_0}\).
2. Na mocy (F) \(\displaystyle{ w(1)=\pm 1}\), bo
[EDIT]
jesli \(\displaystyle{ w(x)=1}\), to \(\displaystyle{ x=x-0|w(x)-w(0)=1-0=1}\),
[EDIT]
wiec zalozmy tez, ze \(\displaystyle{ w(1)=1}\) rozwazajac w razie potrzeby \(\displaystyle{ -w(x)}\).

Teraz przez indukcje:

Sprawdzamy wielokrotnie wykorzystujac (F) oraz umiejetnosci nabyte w trakcie nauczania poczatkowego, ze \(\displaystyle{ w(F_i)=F_i}\) dla \(\displaystyle{ i=1,2,3,4,5}\) (brzydkie, ale na poziomie szkoly podstawowej).

Zalozenie indukcyjne: Przypuscmy, ze dla pewnej liczby \(\displaystyle{ n>5}\) oraz dowolnego \(\displaystyle{ k\le n}\) zachodzi:

\(\displaystyle{ w(F_k)=F_k}\).

Pokazemy, ze \(\displaystyle{ w(F_{n+1})=F_{n+1}}\)

Niech \(\displaystyle{ w(T)=F_{n+1}}\).

Na mocy (F) i zalozenia indukcyjnego mamy:

\(\displaystyle{ T-F_i|F_{n+1}-F_i}\) dla \(\displaystyle{ i=0,1,...,n}\).

Potrzebne mi tylko beda przypadki \(\displaystyle{ i=0,1,n}\) (uzycie przypadku \(\displaystyle{ i=n-1}\) skraca zapis, ale pogarsza czytelnosc), czyli:

(1) \(\displaystyle{ T|F_{n+1}}\)
(2) \(\displaystyle{ T-1|F_{n+1}-1}\)

(3) \(\displaystyle{ T-F_n|F_{n+1}-F_n=F_{n-1}}\)

Do tego momentu chyba wszyscy doszli na przyklad po lekcji matematyki... Sztuka polegala jedynie na tym, zeby zauwazyc, teraz juz bliziutko i prosto.

Na mocy (3):

\(\displaystyle{ T-F_{n}| F_{n-1}}\) skad

\(\displaystyle{ \boxed{T\ge F_n}}\)

LUB

\(\displaystyle{ 0\le F_n-T|F_{n-1}}\), skad albo

\(\displaystyle{ F_n-T=F_{n-1}}\) czyli \(\displaystyle{ T=F_{n-2}}\), co jest sprzeczne z zalozeniem indukcyjnym

albo

\(\displaystyle{ F_n-T\le\frac 12 F_{n-1}}\) skad

\(\displaystyle{ \boxed{T\ge F_n-\frac{F_{n-1}}{2}>F_n-F_{n-2}=F_{n-1}}}\).

Zatem z (3) wynika:

(*) \(\displaystyle{ 3T\ge 3F_{n-1}>F_{n-2}+F_{n-1}+F_{n-1}=F_n+F_{n-1}=F_{n+1}}\).

Krotko:

(*) \(\displaystyle{ \boxed{T>\frac{F_{n+1}}{3}}}\)

Teraz do gry wkraczaja (1,2)

Na mocy (*) oraz (1), czyli \(\displaystyle{ T|F_{n+1}}\), mamy

\(\displaystyle{ \boxed{T\ge \frac{F_{n+1}}{2}}}\).

Skad jesli \(\displaystyle{ F_{n+1}>4}\), czyli dla \(\displaystyle{ n\ge 5}\), to

\(\displaystyle{ T-1\ge \frac{F_{n+1}}{2}-1>\frac{F_{n+1}-1}{3}}\)

skad na mocy

\(\displaystyle{ T-1|F_{n+1}-1}\)

mamy:

\(\displaystyle{ T-1\ge \frac{F_{n+1}-1}{2}}\)

Zatem

\(\displaystyle{ \boxed{T> \frac{F_{n+1}}{2}}}\),

czyli

\(\displaystyle{ T=F_{n+1}}\), bo \(\displaystyle{ T|F_{n+1}}\).

Pokazalismy, ze \(\displaystyle{ w(F_n)=F_n}\) dla kazdego \(\displaystyle{ n}\), czyli \(\displaystyle{ w(x)-x=0}\) (nieskonczenie wiele pierwiastkow), czyli \(\displaystyle{ w(x)=x}\). Przypominamy sobie redukcje i ostatecznie odpowiedz to wszystkie wielomiany postaci:

\(\displaystyle{ \pm x+a}\) dla \(\displaystyle{ a\in\mathbb{Z}}\).

To rozwiazanie jest dlugie i brzydkie, ale proste: wiadomo co trzeba robic krok po kroku, a sprawdzanie przypadkow wymaga umiejetnosci z podstawowki. Najwiekszy tu pomysl polega na tym, ze jesli \(\displaystyle{ a|b}\), to albo \(\displaystyle{ a=b}\), albo \(\displaystyle{ a\le\frac{b}{2}}\).

Tak jak się spodziewałem, dość ciężko Miałem rację, że się nawet za to nie brałem. Resztę mam jak Sylwek.
Btw., a gdzie są te uprgnione "szkolne" rozwiązania, na które tak czekałem

[xiikzodz]

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.

[Jelen]

wiem, to fragment mojego dowodu którego mi brakło

ogólnie chdzilo o to że kazdy wielomian st conajmiej 2 nie przykmuje nieskonczenie wiele wartosci całkowitych bedacych wartościami innego wielomianu dla x całkowitych.

[Sylwek]

to otrzymamy nieskończony układ kongruencji, którego nie można będzie rozwiązać (rozwiązaniem jest liczba w nieskończoności, a rozpatrujemy liczby całkowite)

przykro mi, ale blef

Ponieważ dużo osób pisało, że ma 7., to może pojawią się prostsze rozwiązania

[limes123]

Dostane jakies punkty za zadanie rozwiazane, w ktorym niestety jest kolizja oznaczen, czy raczej sie nie spodziewac? (konkretnie 8, w ktorym wyszly mi 2 punkty S, czego niestety nie zauwazylem)

[Piotrusg]

Miło mi 5 mam jak limes 2n-1 6 jak Sylwek 8 brak a 7 zaraz przedstawie

[ Dodano: 4 Listopada 2008, 15:53 ]
Otoz to jest "prawie" ciag Fibonacciego a tam zachodzi takie cos ze F(k2n) = F(kn)*F(kn+1)+ F(k)*F(k-1) gdzie to sa indeksy dolne. Dowod jest indukcyjny a potem korzystamy sobie tak wielomian W(k) ma pierwiastek bo f0=0 wiec zachodzi W(k)=(k-k0)*G(k) gdzie G(k) jest o stopien nizszy i tez wspolczynniki całkowite. Teraz 2 przypadki sa gdy W(k) jest pierwsza lub 0 lub 1 i drugi gdy W(k) jest złozona =a*b poniewaz W(k2n)=p*a*b to mozemy tak to ustawic zeby sprzecznosc była naprzykład k-k0=a i G(k)=b ale wtedy moze byc k2n-k0=a i G(k2n)= p*b wiec szprzecznosc i tak dochodzimy do wniosku ze to sie zachowuje jak liczba pierwsza wiec jest iloczynem 1 i samej siebie i kombinacje tego a potem jedyna słuszna postac jest gdy G(k)=+-1 wiec W(K) jest liniowy i ma postac W(K)=k-k0 lub W(k)=-k+k0 gdzie ko to całkowita

[nivwusquorum]

A próbował ktoś dowodzić to za pomocą rachunku różnicowego? Bo ponoć można

[szablewskil]

Mógłby ktoś napisać pelne rozwiazanie do 5, bo naprawde nie mam pojecia jak tam indukcji uzyc. Z tej seri zrobilem 6 i 8

[kubek1]

Ja zrobiłem 7 trochę inaczej niż wszyscy, a czy dobrze czy źle, okaże się.

Niech:
\(\displaystyle{ W(x)=a_n*x^n+a_{n-1}*x^n-1+...+a_1x+a_0}\)
Podstawmy:
\(\displaystyle{ k=tf_n+b_n}\)
Przy czym: \(\displaystyle{ t}\) jest liczbą całkowitą, \(\displaystyle{ b_n}\) jest liczbą całkowitą niezależną od \(\displaystyle{ f_n}\).
Wówczas z własności danego ciągu:
\(\displaystyle{ W(tf_n+b_n)=W(tf_(n-1)+b_(n-1))+W(tf_(n-2)+b_(n-2))}\)

Ponieważ \(\displaystyle{ b_n}\) jest niezależne od \(\displaystyle{ f_n}\), a jak wiemy ze wzoru Bineta wartość \(\displaystyle{ f_n}\) zależy od \(\displaystyle{ n}\), więc \(\displaystyle{ b_n}\) nie zależy też od \(\displaystyle{ n}\), czyli \(\displaystyle{ b_n}\) jest stałą.
Oznaczmy więc:
\(\displaystyle{ b_n=l}\)
Mamy:
\(\displaystyle{ W(tf_n+l)=f_n}\)
Niech:
\(\displaystyle{ P(f_n)=W(tf_n+l)=f_n}\)
Czyli:
\(\displaystyle{ P(f_n)-f_n=0}\)
Niech więc:
\(\displaystyle{ Q(x)=P(x)-x}\)
Dla dowolnego n wielomian Q jest podzielny z twierdzenia Bezouta przez \(\displaystyle{ (x-f_0), (x-f_1),...,(x-f_n)}\), ma więc nieskończenie wiele pierwiastków, czyli jest zerowy, a to oznacza, że:
\(\displaystyle{ P(x)=x}\)
A stąd:
\(\displaystyle{ W(tx+l)=x}\)
Czyli:
\(\displaystyle{ W(x)=(x-l)/t}\)
Pamiętając, że wielomian ten ma współczynniki całkowite, \(\displaystyle{ t}\) musi być dzielnikiem liczby \(\displaystyle{ x-l}\), a więc:
\(\displaystyle{ t=1}\) lub \(\displaystyle{ t=-1}\)
Czyli:
\(\displaystyle{ W(x)=x-l}\) lub \(\displaystyle{ W(x)=-x+l}\)
Szukany wielomian ma więc ogólną postać:
\(\displaystyle{ W=x+b}\) lub \(\displaystyle{ W=-x+b}\)

W 5 wyszło mi podobnie jak większości 2n-1, w 6 aż 4 trójkąty były podobne, a 8 nie mam

[Swistak]

To że BKM i MCL są podobne to się wyprowadza w minutę z treści, a tak naprawdę cały problem w zadaniu polega właśnie na tym żeby udowodnić, że te 2 są podobne co LMK. Ja to zadanie zrobiłem tak, że poprowadziłem dwusieczną kąta LQK i punkt przeciecia z okregiem oznaczyłem jako X i zauważyłem, że kątAXQ=kątQXK i gładko wyszło.
Ja w 5 udowodniłem że zawsze da się 2n-1 (bez pustego) i założyłem, że da się 2n (bez pustego). Obrałem sobie dowolny element z tego zbioru, wypisałe wszystkie zbiory, w których występuje, usunąłem ten element z naszego zbiori i udowodniłem, że łączna liczba podzbiorów spełniacjących warunki nie zmniejszy się o więcej niż 2, a zatem ze zbioru jednoelementowego pod odjęciu n-1 mamy otrzymać 2n-2(n-1)=2 podzbiory co jest niemożliwe.
Dowód z tym odjęciem dwójki przebiegał tak:
1. Wszystkie zbiory, które zawierają dany element się w sobie parami zawierają.
2. Po odjęciu danego elementu mamy o 1 zbiór mniej (bo w zbiorze wypełnonym mamy wszystkie podzbiory elementowe).
3. Maksymalnie 1 ze zbiorów, które były przed odjęciem może być taki sam jak po odjęciu, bo inczej by nie spełniały warunków.
4. Odjęcie tego elementów nie powoduje tego, że inny podzbior spełniający warunki przed odjęciem nie będzie spełniał warunków po odjęciu.

[patry93]

limes123 - mógłbyś dokładniej opisać jak zrobiłeś zad. 8 ?