Competition problem — Combinatorics

Library / /268 of 348

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. Spacing and $ signs are ignored.

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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.