16
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You can model this as a random walk, which is probably no more than 5 lines of work. $\endgroup$ – MathIsLife12 Jan 24 at 4:25
  • $\begingroup$ The official answer is almost complete and pretty easy to follow, except for the "it is not too hard" part. But that would come naturally if you draw the boundaries. $\endgroup$ – Quang Hoang Jan 24 at 4:26
  • $\begingroup$ @QuangHoang: I added a Desmos graph for the "it is not too hard" part which should help illustrate why alpha is less than beta is less than pi $\endgroup$ – Presh Jan 24 at 4:41
  • 1
    $\begingroup$ @MathIsLife12: True. I came across Pearson's famous mosquito random walk while researching but didn't see any simple formulas for random unit vectors. $\endgroup$ – Presh Jan 24 at 4:44
  • 2
    $\begingroup$ The official solution is the most rigorous, because the gaps are computational in nature, rather than logical. AoPS Solution 1 is lacking because it doesn't formalize why the walk (hops?) amounts to addition or subtraction of complex numbers in the way it claims. AoPS Solution 2 is simply wrong; it makes an implicit assumption about the uniformity of the probability distribution of the position after the third jump that cannot be substantiated because it is incorrect. $\endgroup$ – heropup Jan 24 at 4:55
10
$\begingroup$

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\|$.

Rhombus and circle

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$:

Right triangles and circle

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.

$\endgroup$
  • $\begingroup$ This is precisely the reasoning that is missing from the original, terse "proof"--which is more like a skeleton or outline of a proof. +1 $\endgroup$ – heropup Jan 24 at 6:56
  • $\begingroup$ Fantastic! Thanks for finding the thread on AoPS too, the answer by Zimbalono is very useful. $\endgroup$ – Presh Jan 24 at 8:18
2
$\begingroup$

I have just arranged a given soultion(The official solution).

enter image description here

$\endgroup$
  • $\begingroup$ Excellent! Yours is even better as you illustrate alpha from pi to 2pi which was not in the official solution and would confuse some people. $\endgroup$ – Presh Jan 27 at 0:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.