uniolympiads Ελληνικά

IMC 2022, Day 1, Problem 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.

Original from the official 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.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(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.

Transcribed from the official solutions, pages 3–4. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?