Constructia unei functii definita pe o multime finita
Moderators: Laurian Filip, Beniamin Bogosel, Filip Chindea
-
Virgil Nicula
- Euler
- Posts: 622
- Joined: Fri Sep 28, 2007 11:23 pm
Constructia unei functii definita pe o multime finita
Fie o multime finita \( M \) de numere reale nenule cu \( n \) elemente. Exista o functie injectiva \( f:M\rightarrow M \) care verifica relatia \( f(x)+f^{-1}(x)=x \) pentru orice \( x\in M \). Sa se arate ca \( n \) este multiplu de \( 6 \). Sa se arate ca ipoteza este consistenta, adica sa se construiasca un exemplu de functie cu proprietatea mentionata in ipoteza.
Last edited by Virgil Nicula on Sat Sep 29, 2007 1:24 pm, edited 2 times in total.
-
Alin Galatan
- Site Admin
- Posts: 247
- Joined: Tue Sep 25, 2007 9:24 pm
- Location: Bucuresti/Timisoara/Moldova Noua
Rezolvarea ce am gasit-o este mai degraba de clasa a X-a, dar o postez.
Fie \( x\in M \). Intrucat multimea e finita, multimea \( \{x,f(x),f(f(x)),...,f^{r}(x),...\} \) este de asemenea finita, deci exista \( i\neq j \) astfel ca \( f^i(x)=f^j(x) \), unde \( f^r(x) \) inseamna \( fofofof..(x) \) de r ori.
Fiind bijectiva, avem ca \( f^{|i-j|}(x)=x \).
In concluzie, exista un n astfel ca in multimea \( \{x,f(x),f^{2}(x),...,f^{n-1}(x)\} \) toate elementele sa fie diferite si \( f^n(x)=x \) (n este numarul minim cu proprietatea \( f^n(x)=x \)). Pentru simplitate, voi numi multimea orbita lui x, si o voi nota \( <x> \).
Daca luam un alt element \( y\in M \) care nu se afla in \( <x> \), vrem sa aratam ca \( <x>\cap<y>=\emptyset \)
Presupunand prin absurd ca exista a, b astfel ca \( f^a(x)=f^b(y) \), din injectivitate obtinem ca \( f^{a-b}(x)=y \), deci \( y\in <x> \), absurd.
Multimea M fiind finita, vom putea crea un numar finit de astfel de orbite, care partitioneaza multimea M.
Vom arata ca fiecare orbita in parte are numar de elemente divizibil cu 6.
Ne uitam la <x>. Ipoteza se rescrie \( f(f(x))-f(x)+x=0 \), deci \( f^{m+2}(x)-f^{m+1}(x)+f^{m}(x)=0 \) pentru orice m natural.
Fie sirul \( a_m=f^m(x) \)
Deci \( a_{m+2}-a_{m+1}+a_m=0 \).
Ecuatia caracteristica este \( r^2-r+1=0 \) cu radacini \( cos(\frac{\pi}{3})\pm isin(\frac{\pi}{3}) \).
Deci \( a_m=a\cdot cos(m\frac{\pi}{3})+b\cdot sin(m\frac{\pi}{3}) \).
Stim ca \( a_n=a_0 \). Presupunem prin absurd ca n nu e divizibil cu 6.
Fie \( t\in Z \), 0<t<6, \( n\equiv t (mod 6) \).
Avem \( a_n=a_t \) (datorita periodicitatii lui sin si cos).
Deci \( a_t=a_0 \). Mai mult, \( a_6=a_0 \).
Fie \( d=(t,6) \), cu \( d\neq 6 \), deci \( d\in\{1,2,3\} \). Deci exista a,b intregi astfel ca \( ta+6b=d \).
\( a_{ta}=a_0 \) si \( a_{6n}=a_0 \), deci \( a_{ta+6n}=a_0 \).
Deci \( a_d=a_0 \)
Daca d=1 avem \( a_1=a_0 \) deci f(x)=x, deci f(f(x))=f(x)=x, \( \Rightarrow 0=f(f(x))-f(x)+x=x-x+x=x \), absurd deoarece numerele sunt pozitive.
Daca d=2, avem \( a_2=a_0 \), deci \( f(f(x))=x \).
\( 0=f(f(x))-f(x)+x=x-f(x)+x\Rightarrow f(x)=2x\Rightarrow x=f(f(x))=f(2x) \).
\( 0=f(f(2x))-f(2x)+2x=f(x)-x+2x=2x-x+2x\Rightarrow x=0 \), absurd.
Daca d=3, avem \( a_3=a_0 \) deci \( f(f(f(x)))=x \).
\( 0=f(f(f(x)))-f(f(x))+f(x)=x-f(f(x))+f(x) \).
De asemenea, \( f(f(x))-f(x)+x=0 \)
Adunand cele doua relatii obtinem 2x=0, absurd.
Deci presupunerea ca n nu e divizibil cu 6 e falsa, deci orbita are cardinal multiplu de 6.De aici concluzia.
Exemplul il cautam ca fiind orbita lui 1.
Alegem a=b=1 si obtinem multimea \( M=\{cos(m\frac{\pi}{3})+sin(m\frac{\pi}{3})|0\leq m < 6\} \).
Se poate observa ca toate elementele sunt distincte, deci \( |M|=6 \).
Functia o alegem \( f(cos(m\frac{\pi}{3})+sin(m\frac{\pi}{3}))=cos((m+1)\frac{\pi}{3})+sin((m+1)\frac{\pi}{3}) \).
[Edit:] Stie cineva vreo solutie fara ecuatii caracteristice?
Fie \( x\in M \). Intrucat multimea e finita, multimea \( \{x,f(x),f(f(x)),...,f^{r}(x),...\} \) este de asemenea finita, deci exista \( i\neq j \) astfel ca \( f^i(x)=f^j(x) \), unde \( f^r(x) \) inseamna \( fofofof..(x) \) de r ori.
Fiind bijectiva, avem ca \( f^{|i-j|}(x)=x \).
In concluzie, exista un n astfel ca in multimea \( \{x,f(x),f^{2}(x),...,f^{n-1}(x)\} \) toate elementele sa fie diferite si \( f^n(x)=x \) (n este numarul minim cu proprietatea \( f^n(x)=x \)). Pentru simplitate, voi numi multimea orbita lui x, si o voi nota \( <x> \).
Daca luam un alt element \( y\in M \) care nu se afla in \( <x> \), vrem sa aratam ca \( <x>\cap<y>=\emptyset \)
Presupunand prin absurd ca exista a, b astfel ca \( f^a(x)=f^b(y) \), din injectivitate obtinem ca \( f^{a-b}(x)=y \), deci \( y\in <x> \), absurd.
Multimea M fiind finita, vom putea crea un numar finit de astfel de orbite, care partitioneaza multimea M.
Vom arata ca fiecare orbita in parte are numar de elemente divizibil cu 6.
Ne uitam la <x>. Ipoteza se rescrie \( f(f(x))-f(x)+x=0 \), deci \( f^{m+2}(x)-f^{m+1}(x)+f^{m}(x)=0 \) pentru orice m natural.
Fie sirul \( a_m=f^m(x) \)
Deci \( a_{m+2}-a_{m+1}+a_m=0 \).
Ecuatia caracteristica este \( r^2-r+1=0 \) cu radacini \( cos(\frac{\pi}{3})\pm isin(\frac{\pi}{3}) \).
Deci \( a_m=a\cdot cos(m\frac{\pi}{3})+b\cdot sin(m\frac{\pi}{3}) \).
Stim ca \( a_n=a_0 \). Presupunem prin absurd ca n nu e divizibil cu 6.
Fie \( t\in Z \), 0<t<6, \( n\equiv t (mod 6) \).
Avem \( a_n=a_t \) (datorita periodicitatii lui sin si cos).
Deci \( a_t=a_0 \). Mai mult, \( a_6=a_0 \).
Fie \( d=(t,6) \), cu \( d\neq 6 \), deci \( d\in\{1,2,3\} \). Deci exista a,b intregi astfel ca \( ta+6b=d \).
\( a_{ta}=a_0 \) si \( a_{6n}=a_0 \), deci \( a_{ta+6n}=a_0 \).
Deci \( a_d=a_0 \)
Daca d=1 avem \( a_1=a_0 \) deci f(x)=x, deci f(f(x))=f(x)=x, \( \Rightarrow 0=f(f(x))-f(x)+x=x-x+x=x \), absurd deoarece numerele sunt pozitive.
Daca d=2, avem \( a_2=a_0 \), deci \( f(f(x))=x \).
\( 0=f(f(x))-f(x)+x=x-f(x)+x\Rightarrow f(x)=2x\Rightarrow x=f(f(x))=f(2x) \).
\( 0=f(f(2x))-f(2x)+2x=f(x)-x+2x=2x-x+2x\Rightarrow x=0 \), absurd.
Daca d=3, avem \( a_3=a_0 \) deci \( f(f(f(x)))=x \).
\( 0=f(f(f(x)))-f(f(x))+f(x)=x-f(f(x))+f(x) \).
De asemenea, \( f(f(x))-f(x)+x=0 \)
Adunand cele doua relatii obtinem 2x=0, absurd.
Deci presupunerea ca n nu e divizibil cu 6 e falsa, deci orbita are cardinal multiplu de 6.De aici concluzia.
Exemplul il cautam ca fiind orbita lui 1.
Alegem a=b=1 si obtinem multimea \( M=\{cos(m\frac{\pi}{3})+sin(m\frac{\pi}{3})|0\leq m < 6\} \).
Se poate observa ca toate elementele sunt distincte, deci \( |M|=6 \).
Functia o alegem \( f(cos(m\frac{\pi}{3})+sin(m\frac{\pi}{3}))=cos((m+1)\frac{\pi}{3})+sin((m+1)\frac{\pi}{3}) \).
[Edit:] Stie cineva vreo solutie fara ecuatii caracteristice?