I searched the problem on AoPS, and found this thread from 2016.
The solution by Zimbalono there (post #13) is worth looking at as well. The last figure probably calls for some more explanation, but it's pretty good overall.
To fill the gap in the AoPS wiki solution:
WLOG, let $a=(1,0)$. Then, since $\|b\|=\|c\|=1$, the vectors $b+c$ and $b-c$ are orthogonal. This means the four points $a+(b+c)$, $a+(b-c)$, $a-(b+c)$, and $a-(b-c)$ form a rhombus centered at $(1,0)$. This rhombus has side length $2=2\|b\|=2\|c\|$.
In generic position (with probability $1$), one of each of the pairs $\pm(b+c)$ and $\pm(b-c)$ point inward from $(1,0)$ with negative $x$ coordinate, and one each point outward. We claim that (aside from a probability-0 case that puts both on the circle) exactly one of the two inward vertices of the rhombus lies inside the circle.
It is easy to see that at most one can be inside the circle - the distance between the two points is equal to the circle's diameter, so one must be outside. To show that there is one inside, draw in the segments from $A$ to those vertices, and extend them to meet the circle. Because of the right angle, the intersections with the circle are endpoints of a diameter, also of length $2$:
Now we have two right triangles with the same hypotenuse length and the same right angle. Going from the one with vertices on the circle to the one that shares vertices with the rhombus, we must lengthen one leg and shorten the other leg. The lengthened leg pushes its endpoint outside the circle, while the shortened leg pulls its endpoint inside the circle. We have one vertex of the rhombus inside the circle, and we're done.
My figures were done in Asymptote - code available on request, if you want to tinker with things.
Assume $n = 1$. In this case, there are three cases for the number of flies $k$:
- The frog did not move, $k \mod 3 = 0$
- The frog moved left, $k \mod 3 = 1$
- The frog moved right, $k \mod 3 = 2$
In order to arrive at $k \mod 3 = 0$ for $n = 2$, one and only one move can be taken from each of these states: do not move, move right, and move left, respectively. The same is true for $k \mod 3 = 1$ and $k \mod 3 = 2$, so we find three different paths for each of these. A similar reasoning can be used to extend these paths to a length of three, four, etc. In the end, we find that there are $\frac{3^n}{3} = 3^{n-1}$ paths of length $n$ for which the number of caught flies $k$ is divisible by three.
As a hint for (iii): first consider the number of paths $T_{n-1}$ of length $n - 1$ resulting in an even number of flies, and multiply by two, since there are two "even moves"; then consider the number of paths $O_{n-1} = 3^{n-1} - T_{n-1}$ of length $n - 1$ resulting in an odd number of flies, and multiply by one, since there is only one "odd move". This will result in a recurrence relation for the number of paths $T_n$, with $T_1 = 2$. Can you take it from here?
Best Answer
Where these terms come from: the idea is to modify the problem to get an equivalent experiment.
Simply following the word problem, we could choose jumps $a,b,c$ uniformly from the unit circle and then end up at $a+b+c$.
Instead, we could choose $b$ in two steps: first choose an angle $\theta \in [0,\pi)$, then flip a coin to let $b$ be one of $e^{i\theta}$ or $-e^{i\theta}$. This is also uniform on the unit circle. We could do the same thing for $c$.
If, using the second method, we choose the angles for $b$ and $c$, but wait to choose the sign until the end, then we are flipping two coins to choose between $\{a+b+c, a+b+(-c), a+(-b)+c, a+(-b)+(-c)\}$.
Why exactly one of these is in the unit circle: I can't promise this is the best argument, but here's one. We'll show that at most one of these points is in the unit circle, then show that at least one is in the unit circle.
The four points are the vertices of a rhombus with sides parallel to $2b$ and $2c$, which is centered at $a$. Here's a typical picture:
Assume none of the corners are on the boundary of the unit circle, which holds with probability $1$. Then two adjacent corners can't both be in the circle, because they're two units apart. Two opposite corners can't both be in the circle, because the midpoint between them (which is $a$) would also be in the circle. So at most one of these four points is in the unit circle.
On the other hand, from $a$, the four directions $b+c, b-c, -b+c, -b-c$ are perpendicular, so two of them point into the circle; without loss of generality, say that it's $b+c$ and $b-c$. Now consider the following two right triangles:
Both right triangles have hypotenuse $2$: the first one because $|(a+b+c)-(a+b-c)| = |2c|=2$, and the second one because its hypotenuse is a diameter of the unit circle. So the first right triangle has a side that's shorter than the corresponding side of the second one. This means one of its vertices lies on the side of the second right triangle, and is in the interior of the circle, QED.