[MIX][Teoria liczb][Równania funkcyjne] 10 zadań

[ares41]

1. Wykazać, że jeśli \(\displaystyle{ n>4, \ n\in\NN}\) to istnieją \(\displaystyle{ a,b>1}\) takie, że \(\displaystyle{ a+b=n}\) oraz \(\displaystyle{ \frac{\phi(a)}{a} + \frac{\phi(b)}{b} >1}\).

2. Pokazać, że dla każdego \(\displaystyle{ n\in\NN}\) zachodzi \(\displaystyle{ \frac{\sigma(n!)}{n!} \ge \sum_{k=1}^{n} \frac{1}{k}}\)

3. Znaleźć wszystkie surjekcje \(\displaystyle{ f:\NN \rightarrow \NN}\) takie, że dla każdego \(\displaystyle{ n\in\NN}\) zachodzi \(\displaystyle{ f(n) \ge n+(-1)^n}\)

4. Zdefiniujmy ciąg \(\displaystyle{ \{K_n\}_{n \ge 1}}\) następująco:
\(\displaystyle{ K_1=2,\ K_2=8, \ K_{n+2}=3K_{n+1}-K_n+5(-1)^n}\). Wykazać, że jeżeli \(\displaystyle{ K_n}\) jest liczbą pierwszą to \(\displaystyle{ n}\) musi być potęgą trójki.

5. Niech \(\displaystyle{ p \ge 3}\) będzie liczbą pierwszą. Ciąg \(\displaystyle{ \{a_n\}_{n \ge 1}}\) dany jest następująco: \(\displaystyle{ a_n=n,\ 0 \le n \le p-1\ ; \ a_n=a_{n-1}+a_{n-p},\ n \ge p}\). Obliczyć \(\displaystyle{ a_{p^3}\pmod{p}}\)

6. Niech \(\displaystyle{ m \ge 2, m\in \NN}\). Znaleźć najmniejszą liczbę całkowitą \(\displaystyle{ n>m}\) taką, że dla dowolnego podziału zbioru \(\displaystyle{ \{m,m+1,...,n\}}\) na dwa podzbiory, przynajmniej jeden zawiera trzy liczby \(\displaystyle{ a,b,c}\) takie, że \(\displaystyle{ c=a^b}\)

7. Wykazać, że dla dowolnego całkowitego \(\displaystyle{ a_1>1}\) istnieje rosnący ciąg liczb całkowitych dodatnich \(\displaystyle{ a_1,a_2,a_3,...}\) taki, że \(\displaystyle{ a_1+a_2+...+a_n|a_1^2+a_2^2+...+a_n^2}\) dla każdego \(\displaystyle{ n\in\NN}\)

8. Niech \(\displaystyle{ \mu:\NN \rightarrow \CC,\ \mu(n)= \sum_{k\in R_n}\left(\cos \frac{2k\pi}{n} + i \sin\frac{2k\pi}{n} \right)}\), gdzie \(\displaystyle{ R_n=\{k\in\NN|1 \le k \le n, \ \mbox{gcd}(k,n)=1\}}\). Wykazać, że \(\displaystyle{ \mu(n)\in\ZZ}\) dla każdego \(\displaystyle{ n\in\NN}\).

9. Znaleźć wszystkie trójki liczb naturalnych \(\displaystyle{ (a,b,c)}\) takich, że \(\displaystyle{ a!b!=a!+b!+c!}\)

10. Znaleźć wszystkie funkcje \(\displaystyle{ f:\ZZ \setminus \{0\} \rightarrow \QQ}\) takie, że dla dowolnych \(\displaystyle{ x,y\in\ZZ \setminus \{0\}}\) zachodzi \(\displaystyle{ f\left( \frac{x+y}{3} \right)= \frac{f(x)+f(y)}{2}}\)

[Ponewor]

Rozwiązanie rekurencji w 4:    

\(\displaystyle{ K_{n}=\left(\frac{3+\sqrt{5}}{2}\right)^{n}+\left(\frac{3-\sqrt{5}}{2}\right)^{n}+\left( -1\right)^{n}}\)

Zastrzeżenia do 5.:    

Czy ciąg jest w ogóle poprawnie zdefiniowany?

7.:    

Nietrudno sprawdzić, że warunki zadania spełnia ciąg \(\displaystyle{ a_{i}=\left(a_{1}-1\right)^{i-1}\cdot a_{1}}\)

9.:    

Najpierw załóżmy, że są parami różne. Mamy \(\displaystyle{ L=a!b!=a!+b!+c!=R}\). Zarówno \(\displaystyle{ L}\) jak i \(\displaystyle{ R}\) są naturalne, więc dla każdego \(\displaystyle{ p}\), mamy \(\displaystyle{ v_{p}\left( L\right)= v_{p}\left( R\right)}\).
\(\displaystyle{ v_{p}\left( L\right)=v_{p}\left( a!b!\right)=v_{p}\left( a!\right)+v_{p}\left( b!\right)= \sum_{i=1}^{\infty}\left[ \frac{a}{p^{i}}\right] + \sum_{i=1}^{\infty}\left[ \frac{b}{p^{i}}\right]}\)
Tymczasem
\(\displaystyle{ v_{p}\left( R\right)=v_{p}\left( a!+b!+c!\right)=\min \left( v_{p}\left( a!\right), \ v_{p}\left( b!\right), \ v_{p}\left( c!\right)\right)=v_{p}\left( \min \left(a!, \ b!, c! \right)\right)=v_{p}\left( \left( \min \left(a, \ b, c \right)\right)! \right)}\)
No to najpierw \(\displaystyle{ a=\min \left(a, \ b, c \right)}\), wtedy
\(\displaystyle{ v_{p}\left( R\right)=v_{p}\left(a!\right)= \sum_{i=0}^{\infty}\left[ \frac{a}{p^{i}}\right]}\)
A skoro \(\displaystyle{ v_{p}\left( L\right)= v_{p}\left( R\right)}\), to \(\displaystyle{ b=1}\), a skoro \(\displaystyle{ a}\) jest najmniejsze, to \(\displaystyle{ a=1}\), a wtedy rozwiązań nie ma. Role \(\displaystyle{ a}\) i \(\displaystyle{ b}\) są symetryczne, niech więc teraz \(\displaystyle{ c}\) będzie najmniejsze.
Mamy więc \(\displaystyle{ \sum_{i=1}^{\infty}\left[ \frac{a}{p^{i}}\right] + \sum_{i=1}^{\infty}\left[ \frac{b}{p^{i}}\right] = \sum_{i=1}^{\infty}\left[ \frac{c}{p^{i}} \right]}\)
Jednak to nie działa właśnie dlatego, że \(\displaystyle{ c}\) jest najmniejsze.
Zatem pewne dwie z tych liczb są równe. Niech \(\displaystyle{ a=b}\). Mamy \(\displaystyle{ \left( a!\right) ^{2}=2a!+c! \Leftrightarrow a! \left( a!-2\right)=c!}\)
Nie może być \(\displaystyle{ a>c}\), bo wtedy \(\displaystyle{ \left( a-c\right)! \cdot {a \choose k} \cdot \left( a!-2\right) =1}\). Zatem \(\displaystyle{ c \ge a}\). Niech \(\displaystyle{ c=a+k}\), oraz niech \(\displaystyle{ a \ge 4}\). Patrzymy teraz na \(\displaystyle{ v_{p}\left( 2\right)}\). Bo zauważmy, że \(\displaystyle{ 2 \parallel a!-2}\). Mamy więc
\(\displaystyle{ v_{2}\left( a!\left(a!-2\right)\right)=v_{2}\left(a!\right)+v_{2}\left(a!-2\right)= \sum_{i=1}^{\infty}\left[\frac{a}{2^{i}} \right]+1=v_{2}\left(c!\right)= \sum_{i=1}^{\infty}\left[ \frac{c}{2^{i}}\right]=\sum_{i=1}^{\infty}\left[ \frac{a+k}{2^{i}}\right] \ge \sum_{i=1}^{\infty}\left[ \frac{a}{2^{i}}\right]+\sum_{i=1}^{\infty}\left[ \frac{k}{2^{i}}\right] \Rightarrow 1 \ge \sum_{i=1}^{\infty}\left[ \frac{k}{2^{i}}\right]}\)
Stąd widać, że \(\displaystyle{ k=0, \ 1, \ 2, \ 3}\).
Gdy \(\displaystyle{ k=0}\), mamy \(\displaystyle{ a!-2=1 \Leftrightarrow a!=3}\), czyli brak rozwiązań.
Gdy \(\displaystyle{ k=1}\), mamy \(\displaystyle{ a!-2=a+1 \Leftrightarrow a!=a+3}\), jednak dla \(\displaystyle{ a\ge 4}\), lewa strona jest wyraźnie większa.
Gdy \(\displaystyle{ k=2}\), mamy \(\displaystyle{ a!-2=\left( a+1\right)\left(a+2 \right) \Leftrightarrow a!=a^{2}+3a+4}\), jednak dla \(\displaystyle{ a\ge 5}\), lewa strona jest wyraźnie większa, zaś dla \(\displaystyle{ a=4}\) równość nie zachodzi.
Gdy \(\displaystyle{ k=3}\), mamy \(\displaystyle{ a!-2=\left( a+1\right)\left(a+2 \right)\left( a+3\right) \Leftrightarrow a!=a^{3}+6a^{2}+11a+8}\), jednak dla \(\displaystyle{ a\ge 6}\), lewa strona jest wyraźnie większa, zaś dla \(\displaystyle{ a=4, \ 5}\) równość nie zachodzi.
Zatem \(\displaystyle{ a=1, \ 2, \ 3}\) i jest tu rozwiązanie \(\displaystyle{ \left( 3, \ 3, \ 4\right)}\) .
Teraz niech \(\displaystyle{ a=c}\). Mamy równanie \(\displaystyle{ a!b!=2a!+b!}\) równoważne \(\displaystyle{ \left(a!-1\right)\left( b!-2\right)=2}\), co łatwo widać rozwiązań nie ma.
Zatem jedyne rozwiązanie to \(\displaystyle{ \left( 3, \ 3, \ 4\right)}\)

10. + wątpliwości:    

\(\displaystyle{ f\left( x\right)= f\left( \frac{3x}{3} \right)=f\left( \frac{2x+x}{3} \right)=\frac{f\left( 2x\right)+f\left( x\right) }{2} \Leftrightarrow f\left( x\right) =f\left( 2x\right)}\)
a to nam automatycznie indukuje \(\displaystyle{ f\left( 2^{n}x\right) =f\left( x\right)}\)
\(\displaystyle{ f\left( 3x\right)= f\left( \frac{9x}{3} \right)=f\left( \frac{8x+x}{3} \right)=\frac{f\left( 8x\right)+f\left( x\right) }{2}= \frac{f\left( x\right)+f\left( x\right) }{2}=f\left( x\right)}\)
oznaczmy \(\displaystyle{ f\left( 1\right)=a}\), dowiedziemy przez indukcję, że dla dodatnich \(\displaystyle{ x}\) zachodzi \(\displaystyle{ f\left( x\right) =a}\).
Mamy \(\displaystyle{ f\left( 3\right)=f\left( 2\right)=f\left( 1\right)=a}\)
Niech teza zachodzi dla wszystkich dodatnich aż do \(\displaystyle{ x}\):
\(\displaystyle{ f\left( x+1\right)= f\left( \frac{3\left(x+1\right)}{3} \right)=f\left( \frac{3x+3}{3} \right)=\frac{f\left( 3x\right)+f\left( 3\right) }{2}= \frac{f\left( x\right)+f\left( 3\right) }{2}=\frac{a+a }{2}=a}\)
Gdy oznaczymy \(\displaystyle{ f\left( -1\right)=b}\), to analogicznie dowiedziemy, że dla ujemnych \(\displaystyle{ f\left( x\right)=b}\).
No i na koniec:
\(\displaystyle{ a =f\left( 1\right)=f\left( \frac{3}{3}\right)=f\left( \frac{-1+4}{3} \right)=\frac{f\left( -1\right)+f\left( 4\right) }{2}=\frac{b+a}{2} \Leftrightarrow a=b}\)
Zatem rozwiązania i łatwo sprawdzić, że to prawda, to funkcje stałe \(\displaystyle{ f\left( x\right)=a}\), gdzie \(\displaystyle{ a}\) jest dowolną liczbą wymierną. BTW nigdzie nie wykorzystałem tego, że \(\displaystyle{ a \in \QQ}\). Czyżby coś było nie tak?

[kubek1]

2.:    

Niech \(\displaystyle{ A}\) - zbiór dzielników \(\displaystyle{ n!}\). Oczywiście \(\displaystyle{ B:=\{\frac{n!}{1},\frac{n!}{2},...,\frac{n!}{n}\} \subseteq A}\). Z tego już mamy tezę, bo:
\(\displaystyle{ \frac{\sigma(n!)}{n!}=\frac{ \sum_{d \in A} d }{n!} \ge \frac{ \sum_{d \in B} d }{n!}=\frac{ \sum_{k=1}^{n} \frac{n!}{k} }{n!}=\sum_{k=1}^{n} \frac{1}{k}}\)

[Wojteg]

8:

Ukryta treść:    

Zauważmy, że:

\(\displaystyle{ \[\sum\limits_{k = 1}^n {\left( {\cos \frac{{2k\pi }}{n} + i\sin \frac{{2k\pi }}{n}} \right)} = \sum\limits_{k = 1}^n {\xi _n^k = \left\{ \begin{array}{l}
1,\,\,\,\,\,\,n = 1\\
0,\,\,\,\,\,n \ge 2
\end{array} \right.} \]}\)

Każdy pierwiastek z jedynki n-tego stopnia jest pierwiastkiem pierwotnym z jedynki d-tego stopnia dla jakiegoś d|n.

\(\displaystyle{ \[\sum\limits_{d|n} {\mu (d) = } \sum\limits_{k = 1}^n {\xi _n^k = \left\{ \begin{array}{l}
1,\,\,\,\,\,\,n = 1\\
0,\,\,\,\,\,n \ge 2
\end{array} \right.} \]}\)

A więc \(\displaystyle{ $\mu (n)$}\) jest funkcja Mobiusa.

[ares41]

Zastrzeżenia do 5.:    

Czy ciąg jest w ogóle poprawnie zdefiniowany?

Ukryta treść:    

Jak odgrzebię tą kartkę, z której przepisywałem to sprawdzę i potwierdzę na 100%, ale raczej tak to szło. Co miałoby być niepoprawne ?

10. + wątpliwości:    

\(\displaystyle{ f\left( x\right)= f\left( \frac{3x}{3} \right)=f\left( \frac{2x+x}{3} \right)=\frac{f\left( 2x\right)+f\left( x\right) }{2} \Leftrightarrow f\left( x\right) =f\left( 2x\right)}\)
a to nam automatycznie indukuje \(\displaystyle{ f\left( 2^{n}x\right) =f\left( x\right)}\)
\(\displaystyle{ f\left( 3x\right)= f\left( \frac{9x}{3} \right)=f\left( \frac{8x+x}{3} \right)=\frac{f\left( 8x\right)+f\left( x\right) }{2}= \frac{f\left( x\right)+f\left( x\right) }{2}=f\left( x\right)}\)
oznaczmy \(\displaystyle{ f\left( 1\right)=a}\), dowiedziemy przez indukcję, że dla dodatnich \(\displaystyle{ x}\) zachodzi \(\displaystyle{ f\left( x\right) =a}\).
Mamy \(\displaystyle{ f\left( 3\right)=f\left( 2\right)=f\left( 1\right)=a}\)
Niech teza zachodzi dla wszystkich dodatnich aż do \(\displaystyle{ x}\):
\(\displaystyle{ f\left( x+1\right)= f\left( \frac{3\left(x+1\right)}{3} \right)=f\left( \frac{3x+3}{3} \right)=\frac{f\left( 3x\right)+f\left( 3\right) }{2}= \frac{f\left( x\right)+f\left( 3\right) }{2}=\frac{a+a }{2}=a}\)
Gdy oznaczymy \(\displaystyle{ f\left( -1\right)=b}\), to analogicznie dowiedziemy, że dla ujemnych \(\displaystyle{ f\left( x\right)=b}\).
No i na koniec:
\(\displaystyle{ a =f\left( 1\right)=f\left( \frac{3}{3}\right)=f\left( \frac{-1+4}{3} \right)=\frac{f\left( -1\right)+f\left( 4\right) }{2}=\frac{b+a}{2} \Leftrightarrow a=b}\)
Zatem rozwiązania i łatwo sprawdzić, że to prawda, to funkcje stałe \(\displaystyle{ f\left( x\right)=a}\), gdzie \(\displaystyle{ a}\) jest dowolną liczbą wymierną. BTW nigdzie nie wykorzystałem tego, że \(\displaystyle{ a \in \QQ}\). Czyżby coś było nie tak?

Ukryta treść:    

Nie mam wzorcówki, ale liczyłem tak samo.

[Zordon]

Zad 1

Ukryta treść:    

Zależy z jak silnych twierdzeń z teorii liczb można korzystać. Ograniczę się do postulatu Bertranda i prostego szacowania \(\displaystyle{ \phi(n)\geq \frac{\sqrt{n}}{2}}\)
Weźmy liczbę pierwszą \(\displaystyle{ p}\) taką, że \(\displaystyle{ \frac{n}{2}<p<n}\).
Mamy \(\displaystyle{ \frac{\phi(n-p)}{n-p}>\frac{1}{2\sqrt{n-p}}>\frac{1}{2\sqrt{2}\sqrt{n}}}\)
Zatem \(\displaystyle{ \frac{\phi(p)}{p}+\frac{\phi(n-p)}{n-p}=\frac{p-1}{p}+\frac{\phi(n-p)}{n-p}>1-\frac{2}{n}+\frac{1}{2\sqrt{2}\sqrt{n}}>1}\) dla (nawet nie tak bardzo) dużych \(\displaystyle{ n}\).

edit:
w istocie wystarczy tutaj twierdzenie dużo słabsze od postulatu Bertranda:
w przedziale \(\displaystyle{ [n^{1/2+\epsilon},n]}\) istnieje liczba pierwsza.
Wystarczy nam to dla dowolnego \(\displaystyle{ \epsilon>0}\).

[Ponewor]

Co miałoby być niepoprawne ?

Ach już nic, po prostu wczoraj wieczorem nie umiałem tego po ludzku przeczytać. Wszystko jest w porządku.

-- 17 sie 2013, o 13:41 --

Zad 1

Ukryta treść:    

dla (nawet nie tak bardzo) dużych \(\displaystyle{ n}\).

mianowicie dla \(\displaystyle{ n>32}\), to zostawia całkiem sporo do ręcznego sprawdzenia

[yorgin]

3:    

Albo nie widzę czegoś ukrytego w tym zadaniu, albo wychodzi mi tylko jedna surjekcja dana warunkiem z zadania, ale z równością., a więc

\(\displaystyle{ f(n)=n+(-1)^n}\)

[ares41]

3:    

Albo nie widzę czegoś ukrytego w tym zadaniu, albo wychodzi mi tylko jedna surjekcja dana warunkiem z zadania, ale z równością., a więc

\(\displaystyle{ f(n)=n+(-1)^n}\)

Ukryta treść:    

Prosimy więc o dowód, że więcej nie ma

[Msciwoj]

3.:    

Założenia mówią nam, że każda liczba naturalna musi być wartością naszej funkcji. Zatem w szczególności, musi nią być \(\displaystyle{ 0}\). Jednakże \(\displaystyle{ f(0) \ge 1}\) oraz \(\displaystyle{ f(k) \ge 2}\) dla \(\displaystyle{ k \ge 2}\). Zatem, oczywiście \(\displaystyle{ f(1)=0}\). Jedynkę też nasza funkcja musi gdzieś przyjmować, a ponieważ \(\displaystyle{ f(1)}\) jest zajęte, a dalej już muszą być większe wartości, zatem \(\displaystyle{ f(1)=0}\), bo akurat może.

Załóżmy teraz, że \(\displaystyle{ f(n)=n +(-1)^{n}}\) dla wszystkich \(\displaystyle{ n}\) od \(\displaystyle{ 0}\) do jakiegoś \(\displaystyle{ 2k-1}\). Udowodnimy, że \(\displaystyle{ f(2k) = 2k +1; f(2k+1) = 2k}\).

Istotnie, wartości te nie zostały przyjęte wcześniej, a gdzieś przyjęte być muszą. Mamy jednak \(\displaystyle{ f(2k+2) \ge 2k+3 > 2k+1}\), oraz \(\displaystyle{ f(m) \ge m -1 > 2k+1}\) dla każdego \(\displaystyle{ m \ge 2k+3}\). Oznacza to, że wszystkie wartości funkcji dla argumentów większych od \(\displaystyle{ 2k+1}\) są większe od \(\displaystyle{ 2k}\). A ponieważ \(\displaystyle{ f(2k) \ge 2k+1}\), to w istocie musi być \(\displaystyle{ f(2k+1) = 2k}\) i, z tego samego powodu \(\displaystyle{ f(2k) = 2k +1}\).
Co kończy dowód.

[yorgin]

Ukryta treść:    

Prosimy więc o dowód, że więcej nie ma

Ukryta treść:    

Mój dowód przebiega analogicznie do tego podanego przez Msciwoja, więc nie będę powtarzać tego samego drugi raz.

I jednak nie było ukrytego dna, powinienem okazać więcej pewności przy rozwiązywaniu tego zadania