Let us look on a $p\times p$ board (the $(\mathbb{F}_p)^2$ plane) with a single piece on the down left corner $(0,0)$. This is a special piece that has $3$ legal moves:
- Moving one step up $\pmod p$
- Moving one step to the right $\pmod p$
- Moving x steps to the right and y steps up $\pmod p$, where $1\leq x,y \leq p-1$
I am trying to prove that the piece can get to any square on the board (except back to the original $(0,0)$ square) in at most $p-1$ legal moves. I have a proof when $x=y=1$ and when $x+y=0$. Can you help with the other cases?
Thanks
This is not always possible. For a counterexample let $p=7$, $(x,y)=(6,2)$ and pick $(u,v)=(5,3)$ as the square you want to reach. Try as you may, you will need at least $8$ moves (for a proof see the argument below).
However, I can prove that this can always be done, if we make the extra assumption that $x+y\not\equiv 1\pmod p$.
The various ways of using moves of the 3 types, say $a_i$ moves if type $i$, $i=1,2,3$, amount to studying the set of solutions $(a_1,a_2,a_3)\in\Bbb{F}_p^3$ of the underdetermined system $$ a_1(0,1)+a_2(1,0)+a_3(x,y)=(u,v). \qquad(*) $$ We easily see that $a_3\in\Bbb{F}_p$ can be chosen any which way want, and it determines the solution uniquely. So the solutions of $(*)$ are parametrized by $t\in\Bbb{F}_p$ as $$ (a_1,a_2,a_3)=(v-ty,u-tx,t).\qquad(**) $$ Let's denote by $|a|$, $a\in\Bbb{F}_p$, the "integer value" of an element $a$, so $|a|$ will be an integer in the range $[0,p-1]$. The number of moves required by the solution $(**)$ is thus $$ S(t)=|v-ty|+|u-tx|+|t|. $$
An averaging argument follows. Let's begin by calculating the sum of all these possibilities $$ \sum_{t=0}^{p-1}S(t)=\sum_{t=0}^{p-1}|v-ty|+\sum_{t=0}^{p-1}|u-tx|+\sum_{t=0}^{p-1}|t|. $$ Because you assumed that neither $x$ nor $y$ is $\equiv 0\pmod p$, all three sums on the r.h.s. have all the numbers $0,1,\ldots,p-1$ as terms in some order. For example, $|v-ty|\equiv v-ty\pmod p$, so pairwise non-congruent choices for $t$ lead to non-congruent, and hence distinct, values of $|v-ty|$.
Therefore we can conclude that $$ \sum_{t=0}^{p-1}S(t)=\frac32p(p-1). $$ We view this as saying that, with the parameter $t$ varying, the average number of moves that you need in different solutions of $(*)$ is $3(p-1)/2$.
Let's look at the distribution of the move counts $S(t)$. We seee that $$ S(t)=|v-ty|+|u-tx|+|t|\equiv (u-tx)+(v-ty)+t=u+v-t(x+y-1)\pmod p. $$ So if we assume that $x+y\not\equiv1\pmod p$, it follows that $S(t)\not\equiv S(t')$ whenever $t\not\equiv t'$. In particular the numbers $S(t), t=0,1,\ldots,p-1$, are all distinct in this case! We can deduce that at least one of them is $<p$. For otherwise their sum would be at least $p+(p+1)+\cdots+(2p-1)=p(3p-1)/2>3p(p-1)/2$ contradicting the earlier result about their average.
Unfortunately, when $x+y\equiv1\pmod p$ things can go South. In the earlier example case $p=7$, $(x,y)=(6,2)$, $(u,v)=(5,3)$ we easily see that $S(t)=8$ for all but a single choice of $t$ with the exceptional value being $S(6)=|4|+|5|+|6|=15$. The average is still as predicted, because $(6\cdot8+1\cdot15)/7=9=3(7-1)/2$. Observe that, again in accordance with the earlier calculations, here all the move counts $S(t)$ are congruent to $u+v=8$ modulo $7$.