Did you count your hops?

Number Theory Level 5

Hoppy the Rabbit lives on the vertices of a regular 2015-gon with vertices labelled $1,2,3,4\dots 2015$ . Hoppy lives on vertex 1, and he wishes to visit every vertex this year. To do this he buys a $k$ -hopping machine. The $k$ -hopping machine allows Hoppy to hop from his current vertex (assume it has number $v$ ) to the vertex with the number $v+k$ . If $v+k>2015$ it sends him to vertex $v+k-2015$ instead. The $k$ hopping machines exist for $k=1,2,3\dots 2015$ . What is the sum of the values of $k$ for which the $k$ -hopping machine allows Hoppy to reach all of the vertices, starting at vertex 1 and hopping a finite number of times?

The answer is 1450800.

1 solution

Jorge Fernández
Sep 8, 2015

The values of $k$ so that the $k$ -hopping machine allows Hoppy to reach every vertex are those so that $k$ and $2015$ are coprime. Notice there are $\varphi(2015)=4\cdot 12 \cdot 30$ such values of $k$ . Now notice we can pair them up in pairs that add $2015$ . that is because if $k$ and $2015$ are coprime then so are $2015-k$ and $2015$ . There are $2\cdot12\cdot30$ pairs, and each add $2015$ . Therefore the answer is $2015\cdot2\cdot12\cdot30=1450800$

Did you count your hops?

The answer is 1450800.

1 solution

0 pending reports