A frog trainer places one frog at each vertex of an equilateral triangle $ABC$ of unit sidelength. The trainer can make one frog jump over another along the line joining the two, so that the total length of the jump is an even multiple of the distance between the two frogs just before the jump. Let $M$ and $N$ be two points on the rays $AB$ and $AC$, respectively, emanating from $A$, such that $AM = AN = \ell$, where $\ell$ is a positive integer. After a finite number of jumps, the three frogs all lie in the triangle $AMN$ (inside or on the boundary), and no more jumps are performed. Determine the number of final positions the three frogs may reach in the triangle $AMN$. (During the process, the frogs may leave the triangle $AMN$, only their nal positions are to be in that triangle.)
Problem
Source: RMM Shortlist 2016 C2
Tags: combinatorics, Equilateral Triangle, Equilateral
02.07.2021 02:26
Answer: $\frac{\lfloor\frac{l+2}{2}\rfloor\lfloor\frac{l+4}{2}\rfloor(\lfloor\frac{l+1}{2}\rfloor\lfloor\frac{l+3}{2}\rfloor)^2}{8}$ Proof: We look at the coordinate system for which $A=(0,0), B=(1,0)$ and $C=(0,1)$ (hexagonal grid). It is easy to see that $A, B$ and $C$ will always stay on the grid and that their coordinates $\pmod 2$ are invariant. Now it easy to check that there are $\frac{\lfloor\frac{l+2}{2}\rfloor\lfloor\frac{l+4}{2}\rfloor}{2}$ points in $AMN$ that are congruent $A \pmod 2$ and $\frac{\lfloor\frac{l+1}{2}\rfloor\lfloor\frac{l+3}{2}\rfloor}{2}$ that are congruent to $B$ and $C$ $\pmod 2$ each. So there are at most $\frac{\lfloor\frac{l+2}{2}\rfloor\lfloor\frac{l+4}{2}\rfloor(\lfloor\frac{l+1}{2}\rfloor\lfloor\frac{l+3}{2}\rfloor)^2}{8}$ final positions. Let us now prove that all triangles $DEF$ that are congruent $ABC \pmod2$ can be reached. First notice that $\frac{Area(DEF)}{Area(ABC)}$ is odd. If a frog jumps over another one, so that the length of the jump is exactly two times the distance between them, then this jump can be reversed. With that knowledge let us perform these kind of jumps on $DEF$ to reach a triangle for which two of its frogs have the same y-coordinate. Note that these jumps do not change the area of $DEF$. Let the y-coordinates of $D, E, F$ be $d, e, f$. Assume $min\{|d-e|, |e-f|, |f-d|\}=|d-e|>0$. Then these jumps can be performed on $D$ and $E$ so that $f\in[d', e']$. Then $|d'-f| or |e'-f|$ is smaller than $|d-e|$. Continuing this you can reach the wanted position. Now assume $d=e$. Let the x-coordinates of $D, E, F$ be $p, q, r$ with p<q. If $q-p$ is even then $\frac{Area(DEF)}{Area(ABC)}$ is also which can not be. Let $E'=(p-1, d)$. Because $q-p+1$ is even $DEF$ can be reached from $DE'F$. So we can assume that $q-p=1$. That means that we can perform reversible jumps on $D$ and $E$ so that $p$ or $q$ equals $r$. Then with the same logic as above we can assume that |f-d|=1. So all that remains to be proved is that any unit triangle that is congruent to $ABC \pmod2$ can be reached which is easily achievable by letting 2 of the frogs jump over the other one with twice the distance repeatedly.