Forum matematyczne: miliony postów, setki tysięcy tematów, dziesiątki tysięcy użytkowników - pomożemy rozwiązać każde zadanie z matematyki https://matematyka.pl/
Niech \(\displaystyle{ a_{2k}=2}\) i \(\displaystyle{ a_{2k+1}=1}\). Ciąg ten wydaje się spełniać warunki.
[Teoria liczb] zestaw mola
: 3 cze 2010, o 16:08
autor: mol_ksiazkowy
Zadanie 15
Ukryta treść:
Gdyz opuscilem zalozenie iz \(\displaystyle{ a_n}\) ma byc scisle rosnacy i wyszlo nieco inne zadanie. Niestety nie mam juz teraz mozliwosci poprawic .
[Teoria liczb] zestaw mola
: 3 cze 2010, o 17:07
autor: Elvis
Mam nadzieję, że nikt nie obrazi się za podanie tylko części rozwiązania. W 23. mianowicie mam tylko wzór rekurencyjny. Edit: No, może już nie tylko.
Ponadto z tożsamości \(\displaystyle{ {n \choose k} = {n \choose n-k}}\) wynika, że \(\displaystyle{ W_n}\) ma symetryczne współczynniki, co z kolei oznacza \(\displaystyle{ W_n(x) = x^n W(x^{-1})}\). Różniczkując obie strony, mamy \(\displaystyle{ W_n'(x) = n x^{n-1} W_n(x^{-1}) - x^{n-2}W_n'(x^{-1})}\). Podstawiając \(\displaystyle{ x=1}\), otrzymujemy \(\displaystyle{ W_n'(1) = nW_n(1)-W_n'(1)}\), czyli \(\displaystyle{ W_n'(1)=\frac{n}{2}W_n(1)}\).
Zbierzmy to do kupy. \(\displaystyle{ (xW_n(x))' = W_n(x) + xW_n'(x)}\), więc \(\displaystyle{ (xW_n(x))'(1) = W_n(1)+W_n'(1)=\frac{n+2}{2}W_n(1)}\). To z kolei daje rekurencję: \(\displaystyle{ W_{n+1}(1) = 1 + \frac{1}{n+1} \cdot \frac{n+2}{2}W_n(1) \\
S_{n+1} = 1 + \frac{n+2}{2n+2}S_n}\)
Gdybyśmy teraz mieli jakąś hipotezę co do wzoru jawnego, to moglibyśmy ją sprawdzić, ale nie mam pomysłu.
Edit: No dobra. Oczywiście \(\displaystyle{ S_0=1}\). Łatwo sprawdzić, że ciąg \(\displaystyle{ S_n = \frac{n+1}{2^n} \sum_{k=0}^n \frac{2^k}{k+1}}\) spełnia ten warunek i rekurencję, więc jest szukanym ciągem. Zastanowię się jeszcze, jak to zwinąć, ale to już chyba nie jest takie okropne.
Edit2: Mam dość przykry w realizacji pomysł. Chcemy obliczyć sumę \(\displaystyle{ \sum_{k=0}^n \frac{2^k}{k+1}}\). W tym celu określmy wielomian \(\displaystyle{ P(x) = \sum_{k=0}^n \frac{2^k}{k+1} x^{k+1}}\); będziemy chcieli obliczyć jego wartość w jedynce. Ma on tę miłą własność, że \(\displaystyle{ P'(x) = \sum_{k=0}^n (2x)^k = \frac{(2x)^{n+1}-1}{2x-1}}\). Oto, co wypluwa Wolphram, kiedy mu się to podrzuci do scałkowania:
... 28%282x%29^%28n%2B1%29-1%29%2F%282x-1%29
Pozostaje dopasować stałą tak, aby \(\displaystyle{ P(0)=0}\) i podstawić \(\displaystyle{ x=1}\). Otrzymamy jakiś beznadziejny (ale skończony) napis, który potem możemy podać w jawnym wzorze na \(\displaystyle{ S_n}\).
Edit3: Współczynnik \(\displaystyle{ \frac{n+2}{2n+2}}\) w rekurencji jest o tyle ciekawy, że dla \(\displaystyle{ n}\) parzystego \(\displaystyle{ \sum_{k=0}^n \frac{(-1)^k}{{n \choose k}} = \frac{2(n+1)}{n+2}}\). Być może jest to jakaś inna droga.
Zadanie 49:
Niech \(\displaystyle{ f(x) = (x+1)^n = \sum_{k=1}^n {n \choose k} x^k}\). Oczywiście lewa strona równości to \(\displaystyle{ \Re f(i)}\) (symbole Newtona znikają dla \(\displaystyle{ k}\) nieparzystego, dla \(\displaystyle{ k}\) parzystego mamy na przemian 1 i -1). Skupmy się więc na obliczeniu tego.
Najpierw moduł: \(\displaystyle{ |f(i)|=|i+1|^n = \sqrt{2}^n}\). Argument: \(\displaystyle{ \arg f(i) = n \arg(i+1) = n \cdot \frac{\pi}{4}}\). Zatem \(\displaystyle{ \Re f(i) = |f(i)| \cos(\arg f(i)) = \sqrt{2}^n \cos(n \cdot \frac{\pi}{4})}\). Chcemy więc otrzymać \(\displaystyle{ \cos(n \cdot \frac{\pi}{4}) = \frac{1}{\sqrt{2}}}\), co jest równoważne \(\displaystyle{ n \equiv \pm 1 \ (\hbox{mod 8})}\).
Zadanie 26:
Zauważmy, że: \(\displaystyle{ \sqrt{2} \leq \frac{m+2n}{m+n} \iff 2(m+n)^2 \leq (m+2n)^2 \iff m^2 \leq 2n^2 \iff \frac{m}{n} \leq \sqrt{2}}\)
Dowodzi to, że \(\displaystyle{ \sqrt{2}}\) leży gdzieś pomiędzy tymi dwoma liczbami. Oczywiście wszystkie te nierówności są ostre.
PS. Chętnie poznałbym wynik zadania 23, bo otrzymane przeze mnie są wyjątkowo paskudne. Mógłbyś mi, molu, przesłać na PW?
-- 4 czerwca 2010, 22:27 --
A propos 23:
Ukryta treść:
Jeśli kogoś to interesuje, to można tę samą rekurencję wyprowadzić w prostszy, ale bardziej obliczeniowy sposób, posługując się algorytmem siostry Celine.
-- 5 czerwca 2010, 22:22 --
Zadanie 12:
Implikacja \(\displaystyle{ d|a,b,c \Rightarrow d|ab+c,bc+a,ca+b}\) jest oczywista.
Załóżmy zatem, zatem, że \(\displaystyle{ d|ab+c,bc+a,ca+b}\). Z założenia \(\displaystyle{ \hbox{nwd}(a^2-1,b^2-1,c^2-1)=1}\) wynika, że możemy b.s.o. przyjąć \(\displaystyle{ \hbox{nwd}(d,c^2-1)=1}\) (*). Z określenia \(\displaystyle{ d}\) mamy \(\displaystyle{ d|(bc+a)+(ca+b)=(c+1)(a+b)}\), zatem \(\displaystyle{ d|a+b}\) (*). To z kolei daje \(\displaystyle{ d|(ca+b)-(a+b)=a(c-1)}\), czyli \(\displaystyle{ d|a}\) (*). To już właściwie koniec, bo \(\displaystyle{ d|(a+b)-a=b}\) i \(\displaystyle{ d|(ab+c)-ab=c}\).
-- 5 czerwca 2010, 23:15 --
Zadanie 44:
Powtórzę to, co powiedziano na omówieniu na finale.
Równanie \(\displaystyle{ x^2+x+1 \equiv 0 \ (\hbox{mod} \ p)}\) ma rozwiązanie wtedy i tylko wtedy gdy jego wyróżnik, równy \(\displaystyle{ -3}\), jest resztą kwadratową modulo \(\displaystyle{ p}\). Sprawdźmy zatem: \(\displaystyle{ \left( \frac{-3}{p} \right) = \left( \frac{-1}{p} \right) \left( \frac{3}{p} \right) = (-1)^{\frac{p-1}{2}} \left( \frac{p}{3} \right) (-1)^{\frac{p-1}{2} \cdot \frac{3-1}{2}} = \left( \frac{p}{3} \right)}\)
Zatem ma dla \(\displaystyle{ p \equiv 1 \ (\hbox{mod} \ 3)}\), nie ma dla \(\displaystyle{ p \equiv 1 \ (\hbox{mod} \ 3)}\). Ręcznie sprawdzamy, że dla \(\displaystyle{ p=2}\) nie ma, a dla \(\displaystyle{ p=3}\) ma.
-- 5 czerwca 2010, 23:15 --
Zadanie 44:
Powtórzę to, co powiedziano na omówieniu na finale.
Równanie \(\displaystyle{ x^2+x+1 \equiv 0 \ (\hbox{mod} \ p)}\) ma rozwiązanie wtedy i tylko wtedy gdy jego wyróżnik, równy \(\displaystyle{ -3}\), jest resztą kwadratową modulo \(\displaystyle{ p}\). Sprawdźmy zatem: \(\displaystyle{ \left( \frac{-3}{p} \right) = \left( \frac{-1}{p} \right) \left( \frac{3}{p} \right) = (-1)^{\frac{p-1}{2}} \left( \frac{p}{3} \right) (-1)^{\frac{p-1}{2} \cdot \frac{3-1}{2}} = \left( \frac{p}{3} \right)}\)
Zatem ma dla \(\displaystyle{ p \equiv 1 \ (\hbox{mod} \ 3)}\), nie ma dla \(\displaystyle{ p \equiv 1 \ (\hbox{mod} \ 3)}\). Ręcznie sprawdzamy, że dla \(\displaystyle{ p=2}\) nie ma, a dla \(\displaystyle{ p=3}\) ma.
[Teoria liczb] zestaw mola
: 17 lip 2010, o 23:59
autor: XMaS11
İntegral pisze:Znajdzie się odważny, żeby rozwiązać zadanie 92. dla \(\displaystyle{ p>3}\)?
Gdyby wszystkie liczby \(\displaystyle{ a,b,c}\) były podzielne przez \(\displaystyle{ p}\), dostalibyśmy że \(\displaystyle{ p}\) jest sumą trzech ułamków, co jest niemożliwe, bo \(\displaystyle{ p>3}\). Przyjmijmy więc, że \(\displaystyle{ c}\) nie dzieli się przez \(\displaystyle{ p}\). Niech \(\displaystyle{ k}\) będzie wykładnikiem, w którym \(\displaystyle{ p}\) dzieli \(\displaystyle{ a}\). Podobnie definiujemy \(\displaystyle{ l}\) dla \(\displaystyle{ b}\). Równanie z treści jest równoważne z \(\displaystyle{ (abc)^2=p((ab)^2+(bc)^2+(ca)^2)}\). Załóżmy, że \(\displaystyle{ k \neq l}\). Wówczas lewa strona jest podzielna przez \(\displaystyle{ p}\) w wykładniku \(\displaystyle{ 2(k+l)}\), a prawa \(\displaystyle{ 1+min{2k,2l}}\). Liczby te są różnej parzystości, co jest niemożliwe, zatem \(\displaystyle{ k=l}\). Kładąc \(\displaystyle{ p^kx=a}\) i \(\displaystyle{ p^ky=b}\) dostajemy: \(\displaystyle{ p^{4k}(xyc)^2=p(p^{4k}(xy)^2+p^{2k}(xc)^2+p^{2k}(yc)^2)}\), czyli \(\displaystyle{ p^{2k-1}(c^2-p)(xy)^2=c^2(x^2+y^2)}\).
Łatwo sprawdzic, że \(\displaystyle{ (x,y) \neq (1,1)}\), co daje \(\displaystyle{ (xy)^2>x^2+y^2}\).
Zatem : \(\displaystyle{ c^2>p^{2k-1}(c^2-p)}\), tym bardziej \(\displaystyle{ c^2>p(c^2-p)}\) \(\displaystyle{ c^2>pc^2-p^2}\) \(\displaystyle{ p^2>pc^2-c^2}\) \(\displaystyle{ p^2>c^2(p-1)}\) \(\displaystyle{ c^2< \frac{p^2}{p-1}}\). Oczywiście jednak \(\displaystyle{ \frac{1}{p} > \frac{1}{c^2}}\), zatem \(\displaystyle{ p+2> \frac{p^2}{p-1} > c^2 > p}\), zatem \(\displaystyle{ c^2=p+1}\), skad \(\displaystyle{ (c-1)(c+1)=p}\), ale \(\displaystyle{ p}\) jest pierwsze, zatem \(\displaystyle{ c=2}\), co jest niemożliwe.
Zatem wyjściowe równanie dla liczb pierwszych \(\displaystyle{ p}\) większych od 3 nie ma rozwiązań.-- 18 lipca 2010, 08:13 --Dodam jeszcze, że po podstawieniu \(\displaystyle{ ab=x \ bc=y \ ca=z}\) dostajemy : \(\displaystyle{ p= \frac{x^2+y^2+z^2}{xyz}}\), a jedyne wartości całkowite jakie może przyjąc wyrażenie po prawej stronie to 1 i 3. Co było jako zadanie w tym roku na Zwardoniu.
[Teoria liczb] zestaw mola
: 31 sie 2010, o 20:27
autor: Elvis
Dla rozruszania coś prostszego.
Zadanie 76:
1T, 2N, 3T, 4T
Dla \(\displaystyle{ f_1}\) nie ma czego dowodzić, pod warunkiem, że \(\displaystyle{ p}\) jest pierwsze (w przeciwnym przypadku nie jest nawet multi).
Dla \(\displaystyle{ f_2}\) mamy \(\displaystyle{ f_2(p)=p^2+1}\), \(\displaystyle{ f_2(p^2)=p^4+p^2+1}\), więc nie jest strong multi. Jest natomiast multi, bo dla \(\displaystyle{ n = \prod p_i^{a_i}}\), \(\displaystyle{ f_2(n) = \prod \frac{p_i^{2a_i+1}-1}{p_i^2-1}}\).
Dla \(\displaystyle{ f_3}\) znowu nie ma czego dowodzić, bo przy podanych warunkach \(\displaystyle{ \omega(mn)=\omega(m)+\omega(n)}\) oraz \(\displaystyle{ \omega(p^k)=1=\omega(p)}\).
Ostatni przykład jest odrobinę ciekawszy, chociaż użycie funkcji Moebiusa trochę na wyrost. Zerują się wszystkie składniki oprócz tych niepodzielnych przez większy od 1 kwadrat; te ze względu na podniesienie funkcji do kwadratu liczą się normalnie. Dla \(\displaystyle{ n = \prod p_i^{a_i}}\), \(\displaystyle{ f_4(n) = \prod (1+p_i)}\). Stąd już widać, że jest strong multi.
[Teoria liczb] zestaw mola
: 30 lip 2011, o 15:46
autor: mol_ksiazkowy
Zadanie 46
Ukryta treść:
Nie ma takich liczb. Bowiem gdy \(\displaystyle{ 4ab-a-b=c^2}\) , tj \(\displaystyle{ (4a-1)(4b-1)=4c^2+1}\), to biorąc dowolny dzielnik pierwszy \(\displaystyle{ p}\) liczby \(\displaystyle{ 4a-1}\) (\(\displaystyle{ p>2}\)) mamy: \(\displaystyle{ (2c)^2 \equiv -1 \ (mod \ p)}\) i : \(\displaystyle{ (2c)^{p-1} \equiv 1 \ (mod \ p)}\) małe tw. Fermata, tj. \(\displaystyle{ 1 \equiv (2c)^{p-1} = ( (2c)^2 )^{\frac{p-1}{2}} \equiv (-1)^{\frac{p-1}{2}}}\)
a stad \(\displaystyle{ p \equiv 1 \ (mod \ 4)}\), skoro \(\displaystyle{ p}\) był wzięty dowolnie, więc \(\displaystyle{ 4a-1 \equiv 1 \ (mod \ 4)}\) tj sprzeczność.
-- 2 sierpnia 2011, 11:40 --
zadanie 62 b
Ukryta treść:
istnieją \(\displaystyle{ p=37}\) i \(\displaystyle{ x=148}\), aby sie o tym przekonać wystarczy zbadać wyrożnik \(\displaystyle{ \Delta= p(p+2960)}\) równania \(\displaystyle{ x^2+px-740p=0}\) (równoważnego z \(\displaystyle{ \frac{x^2}{740-x}=p}\), o ile \(\displaystyle{ x \neq 740}\)), musi byc on (ten wyróżnik) kwadratem, a więc \(\displaystyle{ 2960+p}\) musi dzielić się przez \(\displaystyle{ p}\), tj \(\displaystyle{ 2960}\) musi też się przez \(\displaystyle{ p}\) dzielić, ale \(\displaystyle{ 2960}\) ma dzielniki pierwsze : \(\displaystyle{ 2, 5, 37}\) i tylko ten ostatni jest dobry
-- 2 sierpnia 2011, 12:36 --
62 a
Ukryta treść:
gdy \(\displaystyle{ a=2p}\) to \(\displaystyle{ x=p}\)
-- 3 sierpnia 2011, 11:30 --zadanie 40 a
Ukryta treść:
(Uwaga: rozwiązanie gdy \(\displaystyle{ x,y}\) są w \(\displaystyle{ N}\)) gdy \(\displaystyle{ x=y}\) to \(\displaystyle{ x=y=1}\). Niech \(\displaystyle{ x >y}\) (symetria) wtedy \(\displaystyle{ 3y+1 <3x}\)
a więc sa dwie możliwości (gdyż \(\displaystyle{ 3y+1}\) jest podzielne przez \(\displaystyle{ x}\)): \(\displaystyle{ 3y+1=x}\) albo \(\displaystyle{ 3y+1=2x}\)
Jesli \(\displaystyle{ 3y+1=x}\) to \(\displaystyle{ \frac{3x+1}{y} = 9+ \frac{4}{y}}\) tj. \(\displaystyle{ y=1 , \ x=4}\), \(\displaystyle{ y=2 \ x=7}\), \(\displaystyle{ y=4 \ x=13}\)
Jesli \(\displaystyle{ 3y+1=2x}\) to \(\displaystyle{ \frac{2(3x+1)}{2y}=4+ \frac{y+5}{2y}}\) tj. \(\displaystyle{ y=1 , \ x=2}\), \(\displaystyle{ y=5 \ x=8}\),
PS. w \(\displaystyle{ Z}\) bedzie wiecej rozwiazan, np \(\displaystyle{ x=-5 \ y=-7}\)
[Teoria liczb] zestaw mola
: 8 sie 2011, o 11:19
autor: mol_ksiazkowy
ad 27 b
Ukryta treść:
nieskonczenie wiele realizacji \(\displaystyle{ s=2}\) uzyka sie np dla \(\displaystyle{ n=100k+12}\) gdzie \(\displaystyle{ k=0,1,2,3,...}\)
[Teoria liczb] zestaw mola
: 8 sie 2011, o 19:15
autor: Simon86
zad. 37
Ukryta treść:
Skoro liczby \(\displaystyle{ a,b}\) mają być różnymi liczbami naturalnymi to różnica c\(\displaystyle{ }\) pomiędzy nimi również jest liczbą naturalną. przyjmijmy że \(\displaystyle{ b>a}\) więc możemy napisać że: \(\displaystyle{ b = a +c}\)
Reszta z dzielenia: \(\displaystyle{ \frac{c^{2} - 4}{a^{2} + ac + 2}}\) musi być zerem zgodnie z treścią zadania.
\(\displaystyle{ \frac{c^{2} - 4}{a^{2} + ac + 2} = 0}\)
\(\displaystyle{ c^{2} - 4 = 0}\)
Ponieważ \(\displaystyle{ c}\) jest liczbą naturalną to w tym przypadku mamy jedno rozwiązanie \(\displaystyle{ c = 2}\)
tym samym dla \(\displaystyle{ b = a+2}\)
\(\displaystyle{ \frac{a^{2}+b^{2}}{ab+2} = 2}\)
natomiast \(\displaystyle{ \frac{2\left( a^{2}+b^{2}\right) }{ab+2} = 2^{2}}\)
więc \(\displaystyle{ \frac{2\left( a^{2}+b^{2}\right) }{ab+2}}\) jest zawsze kwadratem dwójki dla wszystkich par liczb \(\displaystyle{ \left( a, a+2\right)}\) gdzie: \(\displaystyle{ a \in N}\) czyli np. \(\displaystyle{ \left( 1,3\right)}\) ; \(\displaystyle{ \left( 2,4\right)}\) itd.
[Teoria liczb] zestaw mola
: 10 sie 2011, o 12:08
autor: Brycho
1.
Ukryta treść:
Niech \(\displaystyle{ q=const}\).
Dla każdego n oznaczmy \(\displaystyle{ A_n= q^{(q+1)^{n}}}\) oraz \(\displaystyle{ a_n=(q+1)^{n+1}}\).
Dla \(\displaystyle{ n=0}\) mamy \(\displaystyle{ q+1 = A_0 +1=a_0 < a_1 = (q+1)^2}\), czyli teza jest spełniona.
Dla \(\displaystyle{ n=1}\) mamy
dla \(\displaystyle{ q=2}\): \(\displaystyle{ 9=A_1+1=a_1 <a_2=27}\),
dla \(\displaystyle{ q>2}\): \(\displaystyle{ A_1 +1= q^{(q+1)}+1 = (q+1)^2 \cdot \left[ (-q+1)+ \sum_{i=1}^{q} (-1)^{i+1}iq^{q-i} \right]=}\)\(\displaystyle{ =(q+1)^3 \cdot \left[ -\frac{1}{2}(q-\frac{2}{q+1}) + \sum_{i=1}^{q-1} (-1)^{i+1}\frac{i(i+1)}{2}q^{q-i-1} \right]}\), czyli teza również jest spełniona.
Załóżmy, że twierdzenie jest prawdziwe dla pewnego \(\displaystyle{ n\geq1}\), wykażemy twierdzenie dla \(\displaystyle{ n+1}\).
Mamy \(\displaystyle{ A_{n+1}+1=(A_n)^{(q+1)}+1=(A_n+1)\cdot \sum_{i=0}^{q} (-1)^i(A_n)^i :=(A_n+1)\cdot W}\).
Dla dowodu indukcyjnego wystarczy zatem udowodnić, że \(\displaystyle{ a_0|W}\) i \(\displaystyle{ a_1\nmid W}\).
Z założenia indukcyjnego wiemy, że \(\displaystyle{ A_1\equiv-1 (\mod a_1)}\). Podnosząc tę zależność stronami do potęgi \(\displaystyle{ q+1}\) mamy kolejno \(\displaystyle{ A_2\equiv-1 (\mod a_1)}\), \(\displaystyle{ A_3\equiv-1 (\mod a_1)}\), ..., \(\displaystyle{ A_n\equiv-1 (\mod a_1)}\).
Zatem \(\displaystyle{ W = \sum_{i=0}^{q} (-1)^i(A_n)^i \equiv \sum_{i=0}^{q} (-1)^i(-1)^i \equiv q+1 (\mod a_1)}\), co kończy krok indukcyjny i rozwiązanie zadania.
[Teoria liczb] zestaw mola
: 14 sie 2011, o 13:55
autor: mol_ksiazkowy
zadanie 45
Ukryta treść:
Gdy \(\displaystyle{ n}\) czyni zadość warunkom zadania, to obliczając wyrażenia \(\displaystyle{ \frac{{n+1 \choose k}}{{n \choose k}}= \frac{n-k}{k+1}}\) widać, że ułamki: \(\displaystyle{ \frac{n}{1}, \ \frac{n-1}{2} ,... ,\frac{n-k}{k+1} , ... \ \frac{2}{n-1}, \ \frac{1}{n}}\)
można zapisać w nieskracalnej formie, tj. o liczniku i mianowniku nieparzystym.
Liczba \(\displaystyle{ n}\) musi być nieparzysta, (bo \(\displaystyle{ {n \choose 1}=n}\)), tj. \(\displaystyle{ n=2^mk - 1}\)
przy czym \(\displaystyle{ k}\) jest nieparzyste, zas \(\displaystyle{ m>0}\)
Rozwiązaniem są liczby \(\displaystyle{ n=2^m-1}\) gdyż \(\displaystyle{ \frac{n-(2^m-1)}{2^m}=k-1}\) jest parzyste (\(\displaystyle{ k>1}\))
i na odwrót: gdy \(\displaystyle{ n=2^m-1}\), to \(\displaystyle{ k+1=2^qr}\) (\(\displaystyle{ r}\) jest nieparzyste) i: \(\displaystyle{ \frac{n-k}{k+1}= \frac{2^{m-q}-r}{r}}\)
Przykłąd: gdy \(\displaystyle{ n=7}\) to \(\displaystyle{ {7 \choose 0}, {7 \choose 1}, {7 \choose 2}, {7 \choose 3}, {7 \choose 4}, {7 \choose 5}, {7 \choose 6}, {7 \choose 7}}\)
są równe \(\displaystyle{ 1, \ 7, \ 21, \ 35, \ 35, \ 21, \ 7, \ 1}\)
zadanie 37 komentarz
Ukryta treść:
Jednakże skad \(\displaystyle{ \frac{c^2-4}{a^2+ac+2}=0}\) ? ! ten ulamek musi wyrazac liczbe calkowita.... ?!
[Teoria liczb] zestaw mola
: 22 gru 2012, o 14:47
autor: Panda
Dobry mix zawsze warto odkopać:
68 całkowicie inaczej:
Dowód jest oparty o bardzo proste przejścia, ale trochę rozległy ze względu na przepisywanie warunków na model grafowy.
Niech \(\displaystyle{ A=\{a_{1},a_{2},...,a_{n}\}}\) to nasz zbiór, przyjmijmy \(\displaystyle{ a_{1}<a_{2}<...<a_{n}}\). Załóżmy, że \(\displaystyle{ n>2}\) i zbiór spełnia zadaną własność.
Określmy dla \(\displaystyle{ i=1,2,...,n-1}\) funkcje \(\displaystyle{ f_{i}(x) = \frac{a_{i}^{2}}{x-a_{i}},D_{f_i}=\mathbb{Z}^{+} \cap (a_{i},+\infty)}\).
Niech także \(\displaystyle{ g_{a}(x) = \frac{x^{2}}{a-x},\, a \in \mathbb{Z}^+ ,\, D_g=\mathbb{Z}^{+} \cap (0,a)}\).
Na początek kilka prostych lematów:
1. \(\displaystyle{ \forall{i}}\) funkcja \(\displaystyle{ f_i}\) jest ściśle malejąca, natomiast \(\displaystyle{ g}\) ściśle rosnąca.
Dowód prosty.
2. \(\displaystyle{ \forall{i}}\) jeśli \(\displaystyle{ f_i(x) = y}\) i \(\displaystyle{ f_i(y) = x}\), to \(\displaystyle{ x=y}\).
Dowód: rozpisujemy wzory i dzielimy stronami, dostajemy: \(\displaystyle{ \frac{x-a}{y-a} = \frac{x}{y}}\), co po wymnożeniu daje \(\displaystyle{ x=y}\).
3. \(\displaystyle{ \forall{i}}\) jeśli \(\displaystyle{ f_i(x)=a_i}\), to \(\displaystyle{ x=2a_i}\).
Dowód: Proste przekształcenia.
Zdefiniujmy następnie dla \(\displaystyle{ k=1,2,...,n-1}\) graf skierowany \(\displaystyle{ G_k = (V_k,E_k)}\), gdzie \(\displaystyle{ V_k =
\{v_{1},v_{2},...,v_{n}\}}\) i \(\displaystyle{ (v_{i},v_{j}) \in E_{i} \Leftrightarrow f_{k}(a_{i}) = a_{j}}\).
(Będą nas jednak interesować tylko \(\displaystyle{ G_1}\) i trochę \(\displaystyle{ G_2}\).)
Na mocy lematów i założeń:
\(\displaystyle{ (a)}\) Stopień wyjściowy każdego wierzchołka \(\displaystyle{ v_{i}}\) grafu \(\displaystyle{ G_{k}}\), przy czym \(\displaystyle{ i>k}\), wynosi \(\displaystyle{ 1}\), a każdego innego \(\displaystyle{ 0}\) (funkcja \(\displaystyle{ f_{i}}\) nie jest dla nich określona). \(\displaystyle{ (b)}\) Stopień wejściowy każdego wierzchołka wynosi \(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\) - bo różnowartościowość \(\displaystyle{ f_{i}}\), lemat 1.). \(\displaystyle{ (c)}\)\(\displaystyle{ \forall{i}}\) jeśli \(\displaystyle{ i<j, v_{i} \rightarrow v_{l},v_{j} \rightarrow v_{k}}\), to \(\displaystyle{ k<l}\) (\(\displaystyle{ f}\) malejąca). \(\displaystyle{ (d)}\) Nie ma cykli długości \(\displaystyle{ 2}\) (lemat 2.) \(\displaystyle{ (e)}\) Jeśli \(\displaystyle{ (v_{n},v_{1}) \in E_{1}}\), to \(\displaystyle{ (v_{n},v_{2}) \not \in E_{2}}\) - fakt wynika z lematu 3 - nie może zajść jednocześnie \(\displaystyle{ a_{n} = 2a_{1}}\) i \(\displaystyle{ a_{n} = 2a_{2}}\). \(\displaystyle{ f)}\) Również, jeśli \(\displaystyle{ (v_{n},v_{1}) \in E_{1}}\), to \(\displaystyle{ (v_{n},v_{1}) \not \in E_{2}}\) - to natomiast wynika z różnowartościowości \(\displaystyle{ g}\) (przeczyłaby jej równość \(\displaystyle{ g_{a_{n}}(a_{1}) = g_{a_{n}}(a_{2}) = a_{1}}\)).
Pokażemy, że w tak zdefiniowany \(\displaystyle{ G_{1}}\) jest ścieżką prostą.
Dalej mówić będę tylko o krawędziach z \(\displaystyle{ G_{1}}\).
Rozważmy, dokąd może prowadzić krawędź z \(\displaystyle{ v_{n}}\). Gdyby nie prowadziła do \(\displaystyle{ v_{1}}\) ani do \(\displaystyle{ v_{2}}\), na mocy \(\displaystyle{ (c)}\) stopień wejściowy \(\displaystyle{ v_{2}}\) wynosiłby \(\displaystyle{ 0}\), a to jest sprzeczne.
Jeśli \(\displaystyle{ v_{n} \rightarrow v_{2}}\), to, jak łatwo stwierdzić, \(\displaystyle{ (c)}\) i \(\displaystyle{ (d)}\) pociągają za sobą także \(\displaystyle{ v_{2} \rightarrow v_{n-1}\rightarrow v_{3} \rightarrow ... v_{k}}\) dla jakiegoś \(\displaystyle{ k}\). Gdyby bowiem było inaczej, np. \(\displaystyle{ v_{2} \rightarrow v_{n-t}}\) dla \(\displaystyle{ t>1}\), to do \(\displaystyle{ v_{n-1}}\) nie miał by już kto wejść, a to by było sprzeczne.
Ale dla wierzchołka \(\displaystyle{ v_{k}}\) nie ma już dobrego kandydata na następnika, więc otrzymaliśmy sprzeczność.
Zatem mamy \(\displaystyle{ v_{n} \rightarrow v_{1}}\).
Rozważmy teraz \(\displaystyle{ G_{2}}\) (istnieje, bo \(\displaystyle{ n>2}\)). Wiemy, że w tym grafie nie ma krawędzi \(\displaystyle{ (v_{n},v_{1})}\) na mocy \(\displaystyle{ (f)}\), zatem możemy go rozważać analogicznie do \(\displaystyle{ G_{1}}\) i otrzymamy \(\displaystyle{ v_{n} \rightarrow v_{2}}\), a to jest sprzeczne z \(\displaystyle{ (e)}\).
Otrzymaliśmy sprzeczność z \(\displaystyle{ n>2}\).
Dla \(\displaystyle{ n=2}\) musi być \(\displaystyle{ f_{1}(a_{2}) = a_{1}}\), czyli \(\displaystyle{ a_{2} = a_{1}}\). Jak łatwo sprawdzić, wszystkie zbiory postaci \(\displaystyle{ \{k;2k\}}\) spełniają warunki zadania.
[Teoria liczb] zestaw mola
: 22 gru 2012, o 15:44
autor: Ponewor
3. - coś nie tak z treścią:
Z założenia \(\displaystyle{ a_{j} \in \mathbb{Z} \Rightarrow ja_{j} \in \mathbb{Z}}\). Układy wyjątkowe istnieją dla każdego \(\displaystyle{ k}\) i \(\displaystyle{ n}\). Wyznaczenie ich nie jest możliwe.
Z 2 równania dostajemy \(\displaystyle{ z \mid 3 \iff z = \pm 3 \vee z = \pm 1}\), rozpatrując wszystkie 4 przypadki dostajemy brak całkowitych rozwiązań.
17:
\(\displaystyle{ 2a^2+a = 3b^2+b \iff 2(a^2-b^2)+a-b = b^2 \iff (a-b)(2a+2b+1) = b^2}\), podobnie wyznaczamy \(\displaystyle{ a^2 = 3(a^2-b^2)+a-b \iff a^2 = (a-b)(3a+3b+1)}\), mnożąc stronami dostajemy \(\displaystyle{ (ab)^2 = (a-b)^2(2a+2b+1)(3a+3b+1)}\), ale teraz jeżeli istnieje jakieś pierwsze \(\displaystyle{ p}\) takie, że \(\displaystyle{ p \mid 2a+2b+1 \wedge p \mid 3a+3b+1}\), to dzieli też różnicę tych liczb czyli \(\displaystyle{ p \mid a+b}\), ale wtedy \(\displaystyle{ p \mid 2a+2b+1 \Rightarrow p \mid 1}\) sprzeczność, więc \(\displaystyle{ (2a+2b+1,3a+3b+1) = 1}\), więc oba wyrażenia muszą być kwadratami liczb całkowitych, a stąd od razu \(\displaystyle{ a-b}\) również musi być kwadratem liczby całkowitej.
18:
Tutaj brakuje założenia, że \(\displaystyle{ p \neq q}\), w przeciwnym razie bierzemy \(\displaystyle{ a=1}\), wszystkie założenia zachodzą a teza nie. Jeżeli \(\displaystyle{ p \neq q}\) to:
\(\displaystyle{ \sum_{j=0}^{p-1} a^j \equiv 0\pmod{q} \Rightarrow a^p \equiv 1\pmod{q}}\), teraz jeżeli \(\displaystyle{ t = ord_q a}\), to mamy \(\displaystyle{ t \mid p}\), jeżeli \(\displaystyle{ t=1}\) to dostajemy \(\displaystyle{ a \equiv 1\pmod{q}}\), ale wtedy \(\displaystyle{ A \equiv \sum_{j=0}^{p-1} a_j \equiv p \equiv 0\pmod{q} \iff p=q}\) sprzeczność. Więc \(\displaystyle{ t=p}\), ale z mtf \(\displaystyle{ t \mid q-1 \iff p \mid q-1}\) cnd.
27:
Nie może. Załóżmy, że istnieją takie całkowite \(\displaystyle{ x,y}\), że \(\displaystyle{ 1 \le y \le 9}\), że \(\displaystyle{ x^2 \equiv 1111y \pmod{10^4} \Rightarrow x^2 \equiv y\pmod{5}}\), stąd wynika, że \(\displaystyle{ y \in \lbrace 1,4,6,9 \rbrace}\) (niezerowymi resztami kwadratowymi modulo 5 są \(\displaystyle{ 1,4}\)), ale mamy również \(\displaystyle{ x^2 \equiv 7y \pmod{16}}\), podstawiamy wszystkie 4 możliwe wartości \(\displaystyle{ y}\) i dostajemy w każdym przypadku nieresztę kwadratową modulo 16.
[Teoria liczb] zestaw mola
: 24 gru 2012, o 17:30
autor: Panda
7 bardzo szkicowo:
Pokażemy, że max to \(\displaystyle{ 50}\) elementów, osiągany np dla \(\displaystyle{ 51,52,...,100}\).
Weźmy sobie \(\displaystyle{ m=}\) minimum z \(\displaystyle{ S}\), następnie podzielmy zbiór \(\displaystyle{ \{1,2,...,100\}}\) na zbiory \(\displaystyle{ A_{0},A_{1},...,A_{m-1}}\) zawierający liczby dające dane reszty modulo \(\displaystyle{ m}\) i dla każdego zasadą szufladkową pokazujemy, że do \(\displaystyle{ S}\) może trafić z niego max podłoga z mocy - z powodu minimaności \(\displaystyle{ m}\). Wyjątkiem jest \(\displaystyle{ A_{0}}\), tu będzie sufit z połowy mocy, ale to nie przeszkadza.
Szczegóły wyjaśnię, jeśli ktoś nie widzi czegoś.
8 nie do końca:
\(\displaystyle{ a+bb \,|\, aab-1 \Leftrightarrow \\
a+bb \,|\, ab(a+bb) - (aab - 1) = abbb + 1 \Leftrightarrow \\
a+bb \,|\, bbb(a+bb) - (abbb+1) = b^{5} - 1}\)
Stąd dobierając dowolne \(\displaystyle{ b}\), dowolne \(\displaystyle{ d : d \,|\, b^{5}-1}\) i \(\displaystyle{ a = d - b^{2}}\) otrzymujemy zawsze - i tylko wtedy - szukaną trójkę. Np. każda para \(\displaystyle{ (b^{2}-b+1,b)}\) spełnia.
A wszystkich dzielników \(\displaystyle{ b^4 +1 + 4b(b^2+1) + 6b^2}\) nie umiem jawnie opisać.
11:
Weźmy najwcześniejszy rząd, w którym się powtórzyło coś nam coś w tablicy i niech ta liczba będzie równa \(\displaystyle{ l}\). W poprzednim się nie powtórzyła i są tam liczby całkowite, więc w poprzednim było jakieś \(\displaystyle{ k}\) i \(\displaystyle{ k^{2}-1}\). Teraz zauważmy, że skoro występuje \(\displaystyle{ k^{2}-1}\) mus, to \(\displaystyle{ 2k-2}\) rzędy temu wystąpiła liczba \(\displaystyle{ (k-1)^{2} = k^{2}-2k+1}\). Nie może być inaczej, bo zadna liczba z \(\displaystyle{ ((k-1)^{2},k^{2})}\) nie jest kwadratem. Zatem było \(\displaystyle{ 2k-2}\) ruchów wcześniej, a ponieważ dla \(\displaystyle{ t>1}\) jest \(\displaystyle{ t+1>t}\) i \(\displaystyle{ t^{2}>t}\), w tamtym rzędzie wystąpiło \(\displaystyle{ a: a \le k - (2k-2) = 2-k}\), a to jest sprzeczne, bo \(\displaystyle{ k>0}\), a \(\displaystyle{ n>1}\).
17:
Najpierw zauważmy, że \(\displaystyle{ a>b}\).
Przekształciwszy dostajemy łatwo, że \(\displaystyle{ b^{2} = (a-b)(2a+2b+1)}\). Dodając stronami \(\displaystyle{ a^{2}-b^{2}}\) otrzymujemy, że \(\displaystyle{ (a-b)(3a+3b+1) = a^{2}}\). Zauważmy, że \(\displaystyle{ (a,b) \,|\, (3a-3b) + (3a+3b+1) = 6a+1}\), ale też \(\displaystyle{ (a,b) \,|\, 6a}\), stąd \(\displaystyle{ (a,b) = 1}\). Weźmy teraz \(\displaystyle{ p \in \mathbb{P} : p\,|\,a-b}\). Daje nam to \(\displaystyle{ p \,|\, a^{2} \Rightarrow p \,|\, a}\), więc \(\displaystyle{ p \,|\, b}\), a to daje, że \(\displaystyle{ p = \pm 1}\), bo \(\displaystyle{ (a,b) = 1}\). A skoro \(\displaystyle{ a>b}\), to \(\displaystyle{ a-b=1}\), a więc \(\displaystyle{ 3a+3b+1 = a^{2}}\), co kończy dowód.