Matematyka.pl

Niech \(\displaystyle{ a_{2k}=2}\) i \(\displaystyle{ a_{2k+1}=1}\). Ciąg ten wydaje się spełniać warunki.

Gdyz opuscilem zalozenie iz \(\displaystyle{ a_n}\) ma byc scisle rosnacy i wyszlo nieco inne zadanie. Niestety nie mam juz teraz mozliwosci poprawic .

Niech \(\displaystyle{ W_n(x)=\sum_{k=0}^n \frac{1}{{n \choose k}} x^k}\). Wówczas \(\displaystyle{ S_n = W_n(1)}\).

Korzystając z tożsamości \(\displaystyle{ {n+1 \choose k+1} = \frac{n+1}{k+1} {n \choose k}}\), łatwo otrzymujemy \(\displaystyle{ W_{n+1}(x) = 1 + \frac{x}{n+1}(x W_n(x))'}\).

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.

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})}\).

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.

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.

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}\).

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.

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.

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.

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ść.

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

gdy \(\displaystyle{ a=2p}\) to \(\displaystyle{ x=p}\)

(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}\)

nieskonczenie wiele realizacji \(\displaystyle{ s=2}\) uzyka sie np dla \(\displaystyle{ n=100k+12}\) gdzie \(\displaystyle{ k=0,1,2,3,...}\)

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}\)

wtedy:

\(\displaystyle{ \frac{a^{2}+b^{2}}{ab+2} = \frac{2a^{2} + 2ac + c^{2}}{a^{2} + ac + 2} =
\frac{2a^{2} + 2ac + c^{2} + 4 - 4}{a^{2} + ac + 2} = \frac{2\left( a^{2} + ac + 2\right) + c^{2} - 4}{a^{2} + ac + 2} = 2 + \frac{c^{2} - 4}{a^{2} + ac + 2}}\)

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.

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.

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}\)

Jednakże skad \(\displaystyle{ \frac{c^2-4}{a^2+ac+2}=0}\) ? ! ten ulamek musi wyrazac liczbe calkowita.... ?!

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.

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.

\(\displaystyle{ \begin{cases} 4x^3+y^2 = 16 \\ z^2+yz = 3 \end{cases}}\)

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ń.

\(\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.

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.

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.

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ś.

\(\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ć.

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}\).

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.

indukcja i postulat bertranda