Putnam 2018/A4

Συντονιστής: Demetres

Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7947
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Putnam 2018/A4

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Δεκ 05, 2018 10:37 am

Έστω πρώτοι μεταξύ τους θετικοί ακέραιοι m,n και έστω

\displaystyle a_k = \left\lfloor \frac{mk}{n} \right\rfloor - \left\lfloor \frac{m(k-1)}{n} \right\rfloor

για k = 1, 2, \dots, n. Έστω g,h στοιχεία μιας ομάδας G ώστε

\displaystyle gh^{a_1} gh^{a_2} \cdots gh^{a_n} = e,

όπου e το ταυτοτικό στοιχείο.

Να δειχθεί ότι gh = hg.



Λέξεις Κλειδιά:
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7947
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Putnam 2018/A4

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Δεκ 07, 2018 4:42 pm

Ωραίο.

Θα το δείξω με επαγωγή στο m+n. Είναι προφανές όταν m=n=1 αφού a_1 = 1, άρα gh = e που δίνει h = g^{-1} και άρα και hg = e = gh. Για το επαγωγικό βήμα ελέγχουμε δύο περιπτώσεις.

Περίπτωση 1: Αν m >n θέτω m' = m-n, n' = n. Τότε a_k' = a_k - 1 για κάθε k. Θέτω g' = gh και h' = h. Τότε

\displaystyle  e = gh^{a_1} gh^{a_2} \cdots gh^{a_n} = gh{a_1'+1} \cdots gh^{a_n'+1} = g' (h')^{a_1'} \cdots g' (h')^{a_n'}

Από την επαγωγική υπόθεση έχουμε g'h' = h'g'. Δηλαδή ghh = hgh οπότε και gh=hg.

Περίπτωση 2: Αν m < n θέτω m' = m, n' = n-m. Θέτω g' = g και h' = gh.

Επειδή m < n, κάθε a_k ισούται είτε με 1 είτε με 0. Στη παράσταση gh^{a_1} \cdots gh^{a_n} αντικαθιστώ κάθε εμφάνιση του gh^{a_k} με g' αν a_k = 0 και με h' αν a_k = 1 για να πάρω μια παράσταση στα g',h' η οποία είναι ίση με e.

Π.χ. για n=7,m=3 έχουμε ggghgghggh = e. Η μετατροπή δίνει gg'h'g'h'g'h' = e που είναι ακριβώς η παράσταση που παίρνουμε για την περίπτωση n'=4,m'=3. Θέλουμε να δείξουμε ότι αυτό δεν είναι τυχαίο αλλά συμβαίνει πάντα. Είναι πιο δύσκολο από την πρώτη περίπτωση διότι τα a_k' δεν σχετίζονται τόσο εύκολα με τα a_k.


Έστω ότι στο βήμα k έγραψα το g' για r-οστή φορά. Αυτό σημαίνει ότι έγραψα και k-r φορές το h'. Για να γράψω όμως τόσες φορές το h' πρέπει ακριβώς k-r φορές να είχα a_i = 1 για 1 \leqslant i \leqslant k. Άρα \displaystyle  \left\lfloor \frac{mk}{n}\right\rfloor = k - r. Επειδή a_k = 0 έχουμε επιπλέον ότι \displaystyle  \left\lfloor \frac{m(k-1)}{n}\right\rfloor = k - r.

Από το \displaystyle  \left\lfloor \frac{mk}{n}\right\rfloor = k - r παίρνουμε \displaystyle \frac{mk}{n} < k-r+1 που είναι ισοδύναμο με το \displaystyle  \frac{m(r-1)}{n-m} < k-r+1

Από το \displaystyle  \left\lfloor \frac{m(k-1)}{n}\right\rfloor = k - r παίρνουμε \displaystyle \frac{m(k-1)}{n} \geqslant k-r που είναι ισοδύναμο με το \displaystyle  \frac{m(r-1)}{n-m} \geqslant k-r

Έχουμε λοιπόν ότι

\displaystyle  a_1' + a_2' + \cdots + a_{r-1}' = \left\lfloor \frac{m(r-1)}{n-m}\right\rfloor = k - r

Αυτό σημαίνει πως όταν γράψω το r-οστό g' έχω γράψει ακριβώς k-r = a_1' + \cdots + a_{r-1}' φορές το h'. Δηλαδή

\displaystyle  g' (h')^{a_1'} \cdots g' (h')^{a_{n'}} = e

Εδώ πρέπει να δικαιολογήσω γιατί το g' (h')^{a_{n'}} είναι ο τελευταίος όρος της παράστασης. Το πλήθος των h' που γράφουμε είναι ίσο με a_1 + \cdots + a_n = m = m' = a_1' + \ cdots + a'_{n'}. Επίσης, το πλήθος των g' είναι ίσο με n-m = n'.

Από την επαγωγική υπόθεση έχουμε g'h' = h'g'. Δηλαδή ggh = ghg οπότε και gh=hg.


Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης