uniolympiads English

IMC 2022, Ημέρα 2, Θέμα 6

Let p>2p > 2 be a prime number. Prove that there is a permutation (x1,x2,…,xp−1)(x_1, x_2, \dots, x_{p-1}) of the numbers (1,2,…,p−1)(1, 2, \dots, p-1) such that

x1x2+x2x3+⋯+xp−2xp−1≡2(modp).x_1 x_2 + x_2 x_3 + \dots + x_{p-2} x_{p-1} \equiv 2 \pmod p.
Πρωτότυπο από το επίσημο PDFLet p > 2 be a prime number. Prove that there is a permutation (x 1 , x 2 , ..., x p−1 ) of the numbers (1, 2, ..., p − 1) such that x 1 x 2 + x 2 x 3 + ... + x p−2 x p−1 ≡ 2 (mod p).

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

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

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

Επίσημη λύση

(proposed by Giorgi Arabidze, Tbilisi Free University, Georgia)

Hint:

Solution 1. We show such a permutation.

Let xi≡i−1(modp)x_i \equiv i^{-1} \pmod{p} for i=1,2,⋯ ,p−1i = 1, 2, \cdots, p-1. Then

∑i=1p−2xixi+1≡∑i=1p−21i⋅1i+1≡∑i=1p−2(1i−1i+1)≡1−1p−1≡p−2p−1≡2(modp)\sum_{i=1}^{p-2} x_i x_{i+1} \equiv \sum_{i=1}^{p-2} \frac{1}{i} \cdot \frac{1}{i+1} \equiv \sum_{i=1}^{p-2} \left(\frac{1}{i} - \frac{1}{i+1}\right) \equiv 1 - \frac{1}{p-1} \equiv \frac{p-2}{p-1} \equiv 2 \pmod{p}

Solution 2. We begin by noting that the identity permutation yields the value

1⋅2+2⋅3+⋯+(p−2)(p−1)=2⋅(p3)≡0(modp)1 \cdot 2 + 2 \cdot 3 + \cdots + (p-2)(p-1) = 2 \cdot \binom{p}{3} \equiv 0 \pmod{p}
as soon as p>3p > 3. The idea now is to perturb that permutation to obtain the desired value 2.

One thing we can do is to replace (i,i+1,i+2,i+3)(i, i+1, i+2, i+3) by (i,i+2,i+1,i+3)(i, i+2, i+1, i+3). Indeed, this will decrease the sum by 3. So if p≡2(mod3)p \equiv 2 \pmod{3}, we can just take the permutation (1,3,2,4,6,5,7,…,p−4,p−2,p−3,p−1)(1, 3, 2, 4, 6, 5, 7, \ldots, p-4, p-2, p-3, p-1) i.e. exchanging 3k−13k-1 and 3k3k whenever k=1,2,…,p−23k = 1, 2, \ldots, \frac{p-2}{3}. This means we decrease the sum p−23\frac{p-2}{3} times by 3, leading to a remaining sum of −(p−2)≡2(modp)-(p-2) \equiv 2 \pmod{p}.

If p≡1(mod3)p \equiv 1 \pmod{3}, this strategy does not work immediately. Instead, we can change (1,2,3,4,5)(1, 2, 3, 4, 5) to (1,4,3,2,5)(1, 4, 3, 2, 5) resulting in a decrement of the sum by 8. If we then exchange 3k3k and 3k+13k+1 for k=2,3,…,p−73k = 2, 3, \ldots, \frac{p-7}{3} as before, we get another p−103\frac{p-10}{3} times a decrement by 3, leading to a remaining sum of −8−p−103⋅3≡2(modp)-8 - \frac{p-10}{3} \cdot 3 \equiv 2 \pmod{p}.

Of course this only works if p≥13p \ge 13. It thus remains to consider the cases p=3p = 3 and p=7p = 7 by hand. For p=3p = 3, we just take (1,2)(1, 2) and for p=7p = 7 we can take (1,4,5,2,3,6)(1, 4, 5, 2, 3, 6).

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

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

Πώς πήγε;