Maths Olympiad Prep

Library / /1103 of 1394

Combinatorics Difficulty 5.6 AIME, harder Find the answer United States

Problem:

An ant starts at the point (0,0)(0,0) in the Cartesian plane. In the first minute, the ant faces towards (1,0)(1,0) and walks one unit. Each subsequent minute, the ant chooses an angle θ\theta uniformly at random in the interval [90,90]\left[-90^\circ, 90^\circ\right], and then turns an angle of θ\theta clockwise (negative values of θ\theta correspond to counterclockwise rotations). Then, the ant walks one unit. After nn minutes, the ant's distance from (0,0)(0,0) is dnd_n. Let the expected value of dn2d_n^2 be ana_n. Compute the closest integer to
10limnann. 10 \lim _{n \rightarrow \infty} \frac{a_n}{n} .

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:

Let αk\alpha_{k} be a random variable that represents the turn made after step kk, choosing αk\alpha_{k} uniformly at random on the complex plane among the arc of the unit circle containing 11 from i-i to ii. It is well known that E[αk]=2π\mathbb{E}\left[\alpha_{k}\right]=\frac{2}{\pi}. We have that
an=i=1nj=1nE[k=1i1αkk=1j1αk1] a_{n}=\sum_{i=1}^{n} \sum_{j=1}^{n} \mathbb{E}\left[\prod_{k=1}^{i-1} \alpha_{k} \prod_{k=1}^{j-1} \alpha_{k}^{-1}\right]
Separating the sum based on ij|i-j|,
an=n+2t=1n1(nt)E[α1αt]=n+2t=1n1(nt)(2π)t a_{n}=n+2 \sum_{t=1}^{n-1}(n-t) \mathbb{E}\left[\alpha_{1} \cdots \alpha_{t}\right]=n+2 \sum_{t=1}^{n-1}(n-t)\left(\frac{2}{\pi}\right)^{t}
Since terms with large tt get very small, we can write
limnann=limn1+2t=1(1tn)(2π)t=1+2t=1limn(1tn)(2π)t=1+2t=1(2π)t \lim _{n \rightarrow \infty} \frac{a_{n}}{n}=\lim _{n \rightarrow \infty} 1+2 \sum_{t=1}^{\infty}\left(1-\frac{t}{n}\right)\left(\frac{2}{\pi}\right)^{t}=1+2 \sum_{t=1}^{\infty} \lim _{n \rightarrow \infty}\left(1-\frac{t}{n}\right)\left(\frac{2}{\pi}\right)^{t}=1+2 \sum_{t=1}^{\infty}\left(\frac{2}{\pi}\right)^{t}
This gives that
x=π+2π2. x=\frac{\pi+2}{\pi-2} .
To estimate this quantity we use the approximation π22/7\pi \approx 22 / 7, which gives us
x22+142214=4.5 x \approx \frac{22+14}{22-14}=4.5

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.