CombinatoricsDifficulty 5.6AIME, harderFind the answerUnited States
Problem:
An ant starts at the point (0,0) in the Cartesian plane. In the first minute, the ant faces towards (1,0) and walks one unit. Each subsequent minute, the ant chooses an angle θ uniformly at random in the interval [−90∘,90∘], and then turns an angle of θ clockwise (negative values of θ correspond to counterclockwise rotations). Then, the ant walks one unit. After n minutes, the ant's distance from (0,0) is dn. Let the expected value of dn2 be an. Compute the closest integer to 10n→∞limnan.
A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.
Solution
Solution:
Let αk be a random variable that represents the turn made after step k, choosing αk uniformly at random on the complex plane among the arc of the unit circle containing 1 from −i to i. It is well known that E[αk]=π2. We have that an=i=1∑nj=1∑nE[k=1∏i−1αkk=1∏j−1αk−1] Separating the sum based on ∣i−j∣, an=n+2t=1∑n−1(n−t)E[α1⋯αt]=n+2t=1∑n−1(n−t)(π2)t Since terms with large t get very small, we can write n→∞limnan=n→∞lim1+2t=1∑∞(1−nt)(π2)t=1+2t=1∑∞n→∞lim(1−nt)(π2)t=1+2t=1∑∞(π2)t This gives that x=π−2π+2. To estimate this quantity we use the approximation π≈22/7, which gives us x≈22−1422+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.