Frogs

Let $B=X_N$. For $i<N$, define $G_i=\gcd(|X_{i+1}-B|,\ldots,|X_N-B|)$, and set $G_N=0$ for convenience. Since all initial coordinates are distinct, $G_{N-1}=0$, while $G_i>0$ for $i\le N-2$.

Let $S_i$ be the set of coordinates reachable by frog $i$. Then $S_N=\{B\}$. If , then . If , then is the set of all integers satisfying or . Moreover, every choice of pairwise distinct coordinates can be realized.

Proof of the reachable sets

Translate all coordinates by $-B$, placing frog $N$ at $0$. The greatest common divisor of the coordinates of the frogs with indices greater than $i$ is initially $G_i$ and remains invariant, because replacing by preserves . Every center of a jump by frog is therefore a multiple of , so a jump can only negate its coordinate modulo . This proves necessity.

The reachable sets have a strong nesting property. If $i<j$, then either $S_i\cap S_j=\varnothing$ or .

Proof of laminarity

For $i<j$, we have $G_i\mid G_j$, and is also a multiple of . Suppose the two sets intersect. Reducing the two residues and of modulo gives the two residues and of . Since , every coordinate of belongs to . The finite case and the singleton follow identically.

Process the frogs in the order $N,N-1,\ldots,1$. Place each frog at a coordinate of its reachable set that is not already used and has minimum absolute value. This greedy algorithm is optimal.

Proof of the greedy algorithm

Take an optimal assignment that already agrees with the greedy choices for all greater indices. For the current frog $i$, let $x$ be the greedy coordinate and let $y$ be its coordinate in the optimal assignment. The coordinate $y$ is not used by any greater index, so $|x|\le|y|$.

It remains to find the closest unused coordinate of each $S_i$. When $G_i>0$, let $m=2G_i$ and normalize a residue to . Its coordinates form the nonnegative stream and the negative stream . When , the negative stream starts at .