uniolympiads English

IMC 2022, Ημέρα 1, Θέμα 3

Let pp be a prime number. A flea is staying at point 00 of the real line. At each minute, the flea has three possibilities: to stay at its position, or to move by 11 to the left or to the right. After p−1p - 1 minutes, it wants to be at 00 again. Denote by f(p)f(p) the number of its strategies to do this (for example, f(3)=3f(3) = 3: it may either stay at 00 for the entire time, or go to the left and then to the right, or go to the right and then to the left). Find f(p)f(p) modulo pp.

Πρωτότυπο από το επίσημο PDFLet p be a prime number. A flea is staying at point 0 of the real line. At each minute, the flea has three possibilities: to stay at its position, or to move by 1 to the left or to the right. After p − 1 minutes, it wants to be at 0 again. Denote by f (p) the number of its strategies to do this (for example, f (3) = 3: it may either stay at 0 for the entire time, or go to the left and then to the right, or go to the right and then to the left). Find f (p) modulo p.

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

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

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

Επίσημη λύση

(proposed by Fedor Petrov, St. Petersburg)

Hint: Find a recurrence for f(p)f(p) or use generating functions.

Solution 1. The answer is f(p)≡0mod  3f(p) \equiv 0 \mod 3 for p=3p = 3, f(p)≡1mod  3f(p) \equiv 1 \mod 3 for p=3k+1p = 3k+1, and f(p)≡−1mod  3f(p) \equiv -1 \mod 3 for p=3k−1p = 3k-1.

The case p=3p = 3 is already considered, let further p≠3p \ne 3. For a residue ii modulo pp denote by ai(k)a_i(k) the number of Flea strategies for which she is at position ii modulo pp after kk minutes. Then f(p)=a0(p−1)f(p) = a_0(p-1). The natural recurrence is ai(k+1)=ai−1(k)+ai(k)+ai+1(k)a_i(k+1) = a_{i-1}(k) + a_i(k) + a_{i+1}(k), where the indices are taken modulo pp. The idea is that modulo pp we have a0(p)≡3a_0(p) \equiv 3 and ai(p)≡0a_i(p) \equiv 0. Indeed, for all strategies for pp minutes for which not all pp actions are the same, we may cyclically shift the actions, and so we partition such strategies onto groups by pp strategies which result with the same ii. Remaining three strategies correspond to i=0i = 0. Thus, if we denote xi=ai(p−1)x_i = a_i(p-1), we get a system of equations x−1+x0+x1=3x_{-1} + x_0 + x_1 = 3, xi−1+xi+xi+1=0x_{i-1} + x_i + x_{i+1} = 0 for all i=1,…,p−1i = 1, \ldots, p-1. It is not hard to solve this system (using the 3-periodicity, for example). For p=3k+1p = 3k+1 we get (x0,x1,…,xp−1)=(1,1,−2,1,1,−2,…,1)(x_0, x_1, \ldots, x_{p-1}) = (1, 1, -2, 1, 1, -2, \ldots, 1), and (x0,x1,…,xp−1)=(−1,2,−1,−1,2,…,2)(x_0, x_1, \ldots, x_{p-1}) = (-1, 2, -1, -1, 2, \ldots, 2) for p=3k+2p = 3k+2.

Solution 2. Note that f(p)f(p) is the constant term of the Laurent polynomial (x+1+1/x)p−1(x + 1 + 1/x)^{p-1} (the moves to right, to left and staying are in natural correspondence with xx, 1/x1/x and 11.) Thus, working with power series over Fp\mathbb{F}_p we get (using the notation [xk]P(x)[x^k]P(x) for the coefficient of xkx^k in PP)

f(p)=[xp−1](1+x+x2)p−1=[xp−1](1−x3)p−1(1−x)1−p=[xp−1](1−x3)p(1−x)−p(1−x3)−1(1−x)=[xp−1](1−x3p)(1−xp)−1(1−x3)−1(1−x)=[xp−1](1−x3)−1(1−x),\begin{aligned} f(p) = [x^{p-1}](1+x+x^2)^{p-1} &= [x^{p-1}](1-x^3)^{p-1}(1-x)^{1-p} = [x^{p-1}](1-x^3)^p(1-x)^{-p}(1-x^3)^{-1}(1-x) \\ &= [x^{p-1}](1-x^{3p})(1-x^p)^{-1}(1-x^3)^{-1}(1-x) = [x^{p-1}](1-x^3)^{-1}(1-x), \end{aligned}
and expanding (1−x3)−1=∑x3k(1-x^3)^{-1} = \sum x^{3k} we get the answer.

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

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

Πώς πήγε;