HMMT November, 2017

Geometry Difficulty 5.4 AIME, harder Prove it United States

Problem:

Ashwin the frog is traveling on the $xy$ -plane in a series of $2^{2017}-1$ steps, starting at the origin. At the $n^{\text{th}}$ step, if $n$ is odd, then Ashwin jumps one unit to the right. If $n$ is even, then Ashwin jumps $m$ units up, where $m$ is the greatest integer such that $2^{m}$ divides $n$ . If Ashwin begins at the origin, what is the area of the polygon bounded by Ashwin's path, the line $x=2^{2016}$ , and the $x$ -axis?

Solution

Solution:

Notice that since $v_{2}(x)=v_{2}\left(2^{2017}-x\right)$ , the path divides the rectangle bonded by the coordinate axes and the two lines passing through Ashwin's final location parallel to the axes. The answer is therefore half of the product of the coordinates of Ashwin's final coordinates. The $x$ -coordinate is the number of odd number steps (which is $2^{2016}$ ). The $y$ -coordinate is the number of total powers of 2 in $\left(2^{2017}-1\right)!$ . The final answer is therefore $2^{2015} \cdot\left(2^{2017}-2018\right)$ .

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

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