The problem
A frog makes $3$ jumps, each exactly $1$ meter long. The directions of the jumps are chosen independently at random. What is the probability that the frog's final position is no more than $1$ meter from its starting position?
Background
This problem comes from the AMC $12$ in the year $2010$. The contest is an invitational test in the US for secondary school to qualify for the Olympiad. It involves $25$ questions in $75$ minutes and problems can be solved without calculus.
I didn't get very far in my attempt, so I ultimately searched and found contributed solutions on the Art of Problem Solving.
I don't understand "solution $1$" and I am pretty sure "solution $2$" is incorrect.
Possible solution $1$: random additions/subtractions
Let $a$,$b$, and $c$ be complex numbers of magnitude one and let the frog start on the origin. Consider the 4 equally likely options of adding or subtracting $b$ and $c$
$$ {|a+b+c|,|a+b-c|,|a-b+c|,|a-b-c|} $$
The AoPS solution states "it is relatively easy" to show exactly $1$ of these has magnitude $1$ or less. If so, then out of $4$ possible options, there would be $1$ with magnitude $1$ or less, so the probability would be $1/4$ (the corrrect answer is indeed $1/4$, but this method does not satisfy me yet).
I did not understand this step, and someone asked the same question in a previous thread. It's not obvious to me, and I have no clue how you would go about showing this.
Is there an inequality that will help? I don't see how to simplify it. Also the official solution is much more complicated (see sketch below), which makes me think this solution is either elegant and overlooked or it is coincidentally the correct number but not the correct method.
(Upon further thought, it seems $a = (1, 0), b = (0, 1), c = (-1, 0)$ would be a counter-example as $|a + b + c| = 1 = |a – b + c|$ so both are within 1.)
Possible solution 2: geometric probability
The solution goes like this. Suppose the first jump is from the origin. So to be $1$ unit from the starting point, you need to be in the unit circle.
The next two jumps can be $2$ units after the first jump, equally likely to be in any angle. So the sample space of ending points is a circle of radius $2$ centered at the point of the first jump. This circle is also tangent to the unit circle.
Thus the sample space has an area of $4\pi$, of which the area of the unit circle is $\pi$. Hence the probability is $1/4$.
I am pretty sure this method is incorrect because I simulated $2$ jumps numerically. You do get a circle of $2$, but not all points are equally likely. There is clustering to the center of the circle and the circumference of the circle.
Plus if this method was true, it would seem that $3$ jumps should be a circle of radius $3$, but that would imply a totally different answer of $1/9$.
The official solution
I found a pdf on the following website, see problem $18$:
http://web2.slc.qc.ca/sh/Contest/AMC12_2010B-S.pdf
Let me try to summarize the method…
The idea is to set coordinates so the first jump is $(0, 0)$ and the second jump is $(1, 0)$. Let the starting point be $(\cos \alpha, \sin \alpha)$ and then the location after the third jump is $(1 + \cos \beta, \sin \beta)$.
It is not too hard to work out the condition for the third point to be within $1$ unit of the first point. Ignoring the measure $0$ cases of $\alpha = 0$ and $\alpha = \pi$, we need $\alpha \leq \beta \leq \pi$. We can limit to $0 \leq \alpha \leq \pi$ since the other half works out the same by symmetry. And we have $0 \leq \beta \leq 2\pi$.
(Check out this interactive graph on Desmos to see why $\alpha \leq \beta \leq \pi$: https://www.desmos.com/calculator/egwegf8utr)
Considering a rectangle $(\alpha, \beta)$ where all angles are equally likely, the sample space is the rectangle of area $2\pi$. The event to be within 1 is a triangle with area $\pi/2$, so the desired probability is $1/4$.
Are the AoPS solutions incomplete?
I would love if their "solution $1$" is correct as it's much easier to compute and it be more reasonable for an average time allotment of $3$ minutes/problem.
(Honestly you could give me unlimited time and I'm not sure I would have produced the official solution.)
What do you guys think?
Disclosure
I run the YouTube channel MindYourDecisions, and am considering this problem. If I make a video I'll credit anyone who offers helpful answers.
Best Answer
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.