Un grup finit G cu n elemente este generat de doua elemente a si b. Sa se arate ca putem construi un sir \( (x_k )_{1 \le k \le 2n} \) cu 2n elemente astfel incat fiecare element din G apare de exact 2 ori si astfel incat \( x_{k+1}=ax_k \) sau \( x_{k+1}=bx_k \) pentru fiecare \( k = \overline {1,n},x_{n+1}=x_1 \).
Putnam 1990
O problema ce se poate rezolva "informatic"
Moderators: Bogdan Posa, Beniamin Bogosel, Marius Dragoi
-
Theodor Munteanu
- Pitagora
- Posts: 98
- Joined: Tue May 06, 2008 5:46 pm
- Location: Sighetu Marmatiei
O problema ce se poate rezolva "informatic"
La inceput a fost numarul. El este stapanul universului.
Indiciu :
Sa privim elementele grupului \( G \) ca si varfurile unui graf orientat. In acest graf, avem o linie de la \( X \) la \( Y \) daca \( Y=aX \) sau \( Y=bX \).
Observam ca orice varf are un numar egal de muchii care intra si care ies (mai exact 2) si ca graful este conectat (deoarece \( a \) si \( b \) genereaza grupul). Din aceste doua observatii rezulta ca graful are un ciclu Eulerian.
Sa privim elementele grupului \( G \) ca si varfurile unui graf orientat. In acest graf, avem o linie de la \( X \) la \( Y \) daca \( Y=aX \) sau \( Y=bX \).
Observam ca orice varf are un numar egal de muchii care intra si care ies (mai exact 2) si ca graful este conectat (deoarece \( a \) si \( b \) genereaza grupul). Din aceste doua observatii rezulta ca graful are un ciclu Eulerian.
Graful se numeste Cayley graph.turcas wrote:Indiciu :
Sa privim elementele grupului \( G \) ca si varfurile unui graf orientat. In acest graf, avem o linie de la \( X \) la \( Y \) daca \( Y=aX \) sau \( Y=bX \).
Frumoasa rezolvarea
