HMMT November

Combinatorics Difficulty 5.0 AIME, harder Find the answer

Ashwin the frog is traveling on the $x y$ -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?

Your answer

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

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: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.