IMC 2012/1/3

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

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

IMC 2012/1/3

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Σάβ Ιούλ 28, 2012 4:22 pm

Για ακέραιο n>1 συμβολίζουμε με S_n την ομάδα των μεταθέσεων των αριθμών 1,2,\ldots,n. Δύο παίκτες A και B παίζουν το εξής παιγνίδι: Με την σειρά επιλέγουν στοιχεία (ένα κάθε φορά) από την ομάδα S_n. Απαγορεύεται να επιλεχθεί στοιχείο το οποίο έχει επιλεχθεί προηγουμένως. Το παιγνίδι τελειώνει όταν τα επιλεγμένα στοιχεία παράγουν την S_n. Ο παίκτης που κάνει την τελευταία επιλογή χάνει. Η πρώτη επιλογή γίνεται από τον A. Ποιος παίκτης έχει στρατηγική νίκης;


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

Re: IMC 2012/1/3

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Σάβ Ιούλ 28, 2012 6:56 pm

Όμορφο.

Για n=2 ο A κερδίζει επιλέγοντας το (1 \, 2). Για n = 3 πάλι κερδίζει ο A επιλέγοντας το (1 \, 2 \, 3). O B για να μην χάσει αμέσως πρέπει να επιλέξει ένα από τα 1,(1\, 3 \,2). Ο A τότε επιλέγει το άλλο και κερδίζει.

Θα δείξουμε ότι για n \geqslant 4 κερδίζει ο B με την ακόλουθη στρατηγική: Αν στην πρώτη του κίνηση ο A επιλέξει έν στοιχείο άρτιας τάξης τότε ο B σε κάθε του κίνηση επιλέγει ένα στοιχείο που να ανήκει στην ομάδα που παράγουν τα μέχρι τώρα επιλεγμένα στοιχεία. Αυτό μπορεί να το κάνει επειδή σε κάθε στιγμή η ομάδα θα έχει άρτια τάξη και πριν την κίνηση του B θα έχουν επιλεχθεί περιττός αριθμός στοιχείων. Αν ο A επιλέξει στοιχείο \pi περιττής τάξης τότε ο B επιλέγει ένα στοιχείο \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 και i,j δυο στοιχεία του πρώτου κύκλου τότε μπορούμε να πάρουμε \rho = (i \, j). Αν k=1 και ο \pi δεν περιέχει όλα τα στοιχεία του \{1,2,\ldots,n\}, π.χ. δεν περιέχει το n, τότε παίρνουμε \rho = (1 \, 2).

Μπορούμε λοιπόν χωρίς βλάβη της γενικότητας να υποθέσουμε ότι \pi = (1 \, 2 \, \ldots \, n) και άρα ο n είναι περιττός. [Εδώ είναι και το μόνο σημείο όπου η απόδειξή μου δυσκολεύει. Δεν ξέρω αν η επίσημη λύση έχει πιο απλή απόδειξη.]

Έστω n = pr όπου p περιττός πρώτος ο οποίος διαιρεί τον n. Έστω επίσης a γεννήτορας της πολλαπλασιαστικής ομάδας των αριθμών \bmod p. Είναι γνωστό ότι το a έχει τάξη p-1. Θεωρούμε το σύνολο G όλων των μεταθέσεων \tau για τις οποίες υπάρχουν k \in \{1,\ldots,p-1\} και d \in \{0,1,\ldots,p-1\} ώστε αν \tau(x) = y τότε y \equiv a^kx + d \bmod p. Το G είναι κλειστό στην σύνθεση συναρτήσεων αφού αν 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}. Οπότε η G αποτελεί ομάδα. Παρατηρούμε ότι \pi \in G. Η τάξη της G ισούται με p(p-1)(r!)^p αφού έχουμε p επιλογές για το d, p-1 επιλογές για το a και με αυτά γνωστά, για κάθε σύνολο r φυσικών που αφήνουν το ίδιο υπόλοιπο \bmod p έχουμε r! επιλογές για το που θα πάει το κάθε ένα από αυτά. Οπότε η G περιέχει τουλάχιστον ένα στοιχείο \rho τάξης 2 αφού 2|p-1. Τέλος G είναι γνήσια υποομάδα του 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 έχουμε p! > p(p-1) αφού τότε p > 3. Οπότε παίρνοντας αυτό το \rho τελειώσαμε.


Απάντηση

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

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

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