IMC 2022 · Day 1 · P3

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

The answer is $f(p) \equiv 0 \mod 3$

for $p = 3$, $f(p) \equiv 1 \mod 3$ for $p = 3k + 1$, and $f(p) \equiv -1 \mod 3$ for $p = 3k - 1$.

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

Note that $f(p)$ is the constant term of the Laurent polynomial $(x + 1 + 1/x)^{p-1}$ (the moves to right, to left and staying are in natural correspondence with $x$, $1/x$ and 1.) Thus, working with power series over $\mathbb{F}_p$ we get (using the notation $[x^k] P(x)$ for the coefficient of $x^k$ in $P$) $$\begin{align*} 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{align*}$$ and expanding $(1 - x^3)^{-1} = \sum x^{3k}$ we get the answer.