Maths Olympiad Prep

Library / /6 of 8

Number theory Difficulty 6.6 National Olympiad Prove it Romania

Let P1P2PnP_1P_2\dots P_n be a regular nn-gon. A frog situated at a vertex PkP_k (1kn1 \le k \le n) can jump to one of the vertices Pk+2P_{k+2} or Pk3P_{k-3}, the indexes being considered modulo nn. Determine the set of positive integers n3n \ge 3 for which the frog can make nn jumps such that it visits all the vertices of the nn-gon and returns to its starting vertex.
Andrei Eckstein

Solution

If nn has the given property, denote by aa the number of jumps of type PkPk+2P_k \mapsto P_{k+2}, and let bb be the number of jumps of type PkPk3P_k \mapsto P_{k-3}. Then a+b=na+b = n and n2a3bn \mid 2a-3b, which leads to n5an \mid 5a and n5bn \mid 5b. As 0a,bn0 \le a, b \le n, we must have either a=0a = 0, b=nb = n, or b=0b = 0, a=na = n, or 5n5 \mid n. By only making jumps of type PkPk+2P_k \mapsto P_{k+2}, the frog can visit all the vertices if and only if nn is odd; making only jumps of type PkPk3P_k \mapsto P_{k-3}, the frog visits all the vertices if and only if 3n3 \nmid n. In conclusion, if nn has the given property, then either it is not a multiple of 22, or it is not a multiple of 33, or it is a multiple of 55.

Conversely, we have seen that if 6n6 \nmid n, then the frog can visit all the vertices by making jumps of a single type.

All that is left is to give an example of a way to choose the frog's jumps in the case when 5n5 \mid n.

There are several such examples. One of them is: the frog jumps PkPk+2P_k \mapsto P_{k+2} (mod 55) if 5k5 \nmid k and PkPk3P_k \mapsto P_{k-3} (mod 55) if 5k5 \mid k.

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.