IMC 2009, Ημέρα 2, Θέμα 4
Let be a prime number and be the field of residues modulo . Let be the smallest set of polynomials with coefficients in such that
- the polynomials and are in , and
- for any polynomials and in the polynomial , which is the remainder of modulo , is also in .
How many polynomials are there in ?
Πρωτότυπο από το επίσημο PDF

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.
Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.
Επίσημη λύση
Solution. Note that both of our polynomials are bijective functions on : is the cycle and is the transposition (this follows from the formula and Fermat's little theorem). So any composition formed from them is also a bijection, and reduction modulo does not change the evaluation in . Also note that the transposition and the cycle generate the symmetric group ( is the transposition , and transpositions of consecutive elements clearly generate ), so we get all permutations of the elements of .
The set only contains polynomials of degree at most . This means that two distinct elements of cannot represent the same permutation. So must contain those polynomials of degree at most which permute the elements of . By minimality, has exactly these elements.
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 3. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.
Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.
Πώς πήγε;
Οι κινήσεις που σημειώνεις επιστρέφουν νωρίτερα στη διαλογή.