IMC 2012/1/3

#1

Για ακέραιο n>1

συμβολίζουμε με S_n

την ομάδα των μεταθέσεων των αριθμών $1,2,\ldots,n$ . Δύο παίκτες

και

παίζουν το εξής παιγνίδι: Με την σειρά επιλέγουν στοιχεία (ένα κάθε φορά) από την ομάδα S_n

. Απαγορεύεται να επιλεχθεί στοιχείο το οποίο έχει επιλεχθεί προηγουμένως. Το παιγνίδι τελειώνει όταν τα επιλεγμένα στοιχεία παράγουν την S_n

. Ο παίκτης που κάνει την τελευταία επιλογή χάνει. Η πρώτη επιλογή γίνεται από τον

. Ποιος παίκτης έχει στρατηγική νίκης;

#2

Όμορφο.

Για n=2

ο

κερδίζει επιλέγοντας το $(1 \, 2)$ . Για n = 3

πάλι κερδίζει ο

επιλέγοντας το $(1 \, 2 \, 3)$ . O

για να μην χάσει αμέσως πρέπει να επιλέξει ένα από τα $1,(1\, 3 \,2)$ . Ο

τότε επιλέγει το άλλο και κερδίζει.

Θα δείξουμε ότι για $n \geqslant 4$ κερδίζει ο

με την ακόλουθη στρατηγική: Αν στην πρώτη του κίνηση ο

επιλέξει έν στοιχείο άρτιας τάξης τότε ο

σε κάθε του κίνηση επιλέγει ένα στοιχείο που να ανήκει στην ομάδα που παράγουν τα μέχρι τώρα επιλεγμένα στοιχεία. Αυτό μπορεί να το κάνει επειδή σε κάθε στιγμή η ομάδα θα έχει άρτια τάξη και πριν την κίνηση του

θα έχουν επιλεχθεί περιττός αριθμός στοιχείων. Αν ο

επιλέξει στοιχείο $\pi$ περιττής τάξης τότε ο

επιλέγει ένα στοιχείο $\rho$ άρτιας τάξης με $\langle \pi, \rho \rangle \neq S_n$ και μετά στις επόμενες κινήσεις επιλέγει ένα στοιχείο που να ανήκει στην ομάδα που παράγουν τα μέχρι τώρα επιλεγμένα στοιχεία.

Αρκεί λοιπόν να δείξουμε πως για κάθε $n \geqslant 4$ και κάθε $\pi \in S_n$ περιττής τάξης υπάρχει $\rho$ άρτιας τάξης με $\langle \pi, \rho \rangle \neq S_n$ . Γράφουμε το $\pi$ σαν γινόμενο $\pi_1 \cdots \pi_k$ ανά δύο ξένων μεταξύ τους κύκλων. Αν k > 1

και

δυο στοιχεία του πρώτου κύκλου τότε μπορούμε να πάρουμε $\rho = (i \, j)$ . Αν k=1

και ο $\pi$ δεν περιέχει όλα τα στοιχεία του $\{1,2,\ldots,n\}$ , π.χ. δεν περιέχει το

, τότε παίρνουμε $\rho = (1 \, 2)$ .

Μπορούμε λοιπόν χωρίς βλάβη της γενικότητας να υποθέσουμε ότι $\pi = (1 \, 2 \, \ldots \, n)$ και άρα ο

είναι περιττός. [Εδώ είναι και το μόνο σημείο όπου η απόδειξή μου δυσκολεύει. Δεν ξέρω αν η επίσημη λύση έχει πιο απλή απόδειξη.]

Έστω n = pr

όπου

περιττός πρώτος ο οποίος διαιρεί τον

. Έστω επίσης

γεννήτορας της πολλαπλασιαστικής ομάδας των αριθμών $\bmod p$ . Είναι γνωστό ότι το

έχει τάξη

. Θεωρούμε το σύνολο

όλων των μεταθέσεων $\tau$ για τις οποίες υπάρχουν $k \in \{1,\ldots,p-1\}$ και $d \in \{0,1,\ldots,p-1\}$ ώστε αν $\tau(x) = y$ τότε $y \equiv a^kx + d \bmod p$ . Το

είναι κλειστό στην σύνθεση συναρτήσεων αφού αν $y \equiv a^kx + d \bmod p$ και $z \equiv a^{k'}y + d' \bmod p$ τότε $z \equiv a^{k+k'}x + (a^k d + d') \bmod p$ . Επίσης είναι κλειστό παίρνοντας αντίστροφα στοιχεία αφού αν $y \equiv a^kx + d \bmod p$ τότε $x \equiv a^{p-1-k}y - da^{p-1-k}$ . Οπότε η

αποτελεί ομάδα. Παρατηρούμε ότι $\pi \in G$ . Η τάξη της

ισούται με p(p-1)(r!)^p

αφού έχουμε

επιλογές για το

,

επιλογές για το

και με αυτά γνωστά, για κάθε σύνολο

φυσικών που αφήνουν το ίδιο υπόλοιπο $\bmod p$ έχουμε

επιλογές για το που θα πάει το κάθε ένα από αυτά. Οπότε η

περιέχει τουλάχιστον ένα στοιχείο $\rho$ τάξης

αφού

. Τέλος

είναι γνήσια υποομάδα του S_n

αφού
$\displaystyle{(pr)! = r! \times ((r+1) \cdots (2r-1)(2r)) \times \cdots \times ((p-1)r+1) \cdots ((p-1)r+(r-1))(pr) \geqslant p!r^p}$
με ισότητα αν και μόνο αν r=1

. Οπότε για r > 1

έχουμε $(pr)! > p!r^p \geqslant p(p-1)r^p$ ενώ για r =1

έχουμε

αφού τότε

. Οπότε παίρνοντας αυτό το $\rho$ τελειώσαμε.

IMC 2012/1/3

IMC 2012/1/3

Re: IMC 2012/1/3

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