uniolympiads English

IMC 2009, Ημέρα 2, Θέμα 4

Let pp be a prime number and Fp\mathbb{F}_p be the field of residues modulo pp. Let WW be the smallest set of polynomials with coefficients in Fp\mathbb{F}_p such that

  • the polynomials x+1x + 1 and xp−2+xp−3+⋯+x2+2x+1x^{p-2} + x^{p-3} + \dots + x^2 + 2x + 1 are in WW, and
  • for any polynomials h1(x)h_1(x) and h2(x)h_2(x) in WW the polynomial r(x)r(x), which is the remainder of h1(h2(x))h_1(h_2(x)) modulo xp−xx^p - x, is also in WW.

How many polynomials are there in WW?

Πρωτότυπο από το επίσημο PDFLet p be a prime number and F p be the field of residues modulo p. Let W be the smallest set of polynomials with coefficients in F p such that • the polynomials x + 1 and x p−2 + x p−3 + · · · + x 2 + 2x + 1 are in W , and • for any polynomials h 1 (x) and h 2 (x) in W the polynomial r(x), which is the remainder of h 1 (h 2 (x)) modulo x p − x, is also in W . How many polynomials are there in W ? 2

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

Solution. Note that both of our polynomials are bijective functions on Fp\mathbb{F}_p: f1(x)=x+1f_1(x) = x+1 is the cycle 0→1→2→⋯→(p−1)→00 \to 1 \to 2 \to \cdots \to (p-1) \to 0 and f2(x)=xp−2+xp−3+⋯+x2+2x+1f_2(x) = x^{p-2} + x^{p-3} + \cdots + x^2 + 2x + 1 is the transposition 0↔10 \leftrightarrow 1 (this follows from the formula f2(x)=xp−1−1x−1+xf_2(x) = \frac{x^{p-1}-1}{x-1} + x and Fermat's little theorem). So any composition formed from them is also a bijection, and reduction modulo xp−xx^p - x does not change the evaluation in Fp\mathbb{F}_p. Also note that the transposition and the cycle generate the symmetric group (f1k∘f2∘f1p−kf_1^k \circ f_2 \circ f_1^{p-k} is the transposition k↔(k+1)k \leftrightarrow (k+1), and transpositions of consecutive elements clearly generate SpS_p), so we get all p!p! permutations of the elements of Fp\mathbb{F}_p.

The set WW only contains polynomials of degree at most p−1p-1. This means that two distinct elements of WW cannot represent the same permutation. So WW must contain those polynomials of degree at most p−1p-1 which permute the elements of Fp\mathbb{F}_p. By minimality, WW has exactly these p!p! elements.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 3. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;