Page 1 of 1
O problema ce se poate rezolva "informatic"
Posted: Fri Dec 18, 2009 2:29 pm
by Theodor Munteanu
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
Posted: Sun Dec 20, 2009 4:37 am
by turcas
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.
Posted: Sun Jan 10, 2010 4:27 pm
by spx2
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 \).
Graful se numeste
Cayley graph.
Frumoasa rezolvarea
