Maths Olympiad Prep

Library / /39 of 86

Combinatorics Difficulty 6.5 National Olympiad Prove it United States

Problem:

At the start of this problem, six frogs are sitting with one at each of the six vertices of a regular hexagon. Every minute, we choose a frog to jump over another frog using one of the two rules illustrated below. If a frog at point FF jumps over a frog at point PP, the frog will land at point FF' such that FF, PP, and FF' are collinear and:
- using Rule 11, FP=2FPF'P = 2FP.
- using Rule 22, FP=FP/2F'P = FP / 2.

Figure 1

Rule 1

Figure 2

Rule 2

It is up to us to choose which frog to take the leap and which frog to jump over.

a. If we only use Rule 1, is it possible for some frog to land at the center of the original hexagon after a finite amount of time?

b. If both Rule 1 and Rule 2 are allowed (freely choosing which rule to use, which frog to jump, and which frog it jumps over), is it possible for some frog to land at the center of the original hexagon after a finite amount of time?

Solution

Solution:

a.
Assign coordinate axes making a 120120^{\circ} angle so that the center of the hexagon is at (0,0)(0,0), the rightmost frog is at (1,0)(1,0), and the top left frog is at (0,1)(0,1). Then, the remaining four frogs are at (1,1)(1,1), (1,0)(-1,0), (0,1)(0,-1), and (1,1)(-1,-1). At each jump, if two frogs' coordinates differ by (x,y)(x, y), then the jumping frog moves (3x,3y)(3x, 3y). That is, each coordinate changes by a multiple of three. However, the goal has both coordinates divisible by three, and none of the frogs start with both coordinates divisible by three, so it cannot be done.

b.
One solution method is to repeat the coordinate method of the previous problem, but now encountering fractions when we use Rule 2. Since the jumping frog now moves (3x/2,3y/2)(3x/2, 3y/2) when the frogs are separated by (x,y)(x, y), looking at the first coordinate a frog's jump will now be
pqpq+3qx2q=2p+3qx2q \frac{p}{q} \rightarrow \frac{p}{q} + \frac{3qx}{2q} = \frac{2p + 3qx}{2q}
If pp is not divisible by 33 before this jump, the numerator of this new fraction is still not divisible by 33. Since the frogs start with at least one coordinate's numerator not divisible by 33, the frogs can never reach a location where both coordinates have numerators that are divisible by 33.

Alternatively, each time Rule 2 is used, simply double all the coordinates before making the jump. This cannot change whether a frog can reach the origin, and it ensures that the coordinates remain integers and that the jumps are all by a multiple of 33, so the same argument for Rule 1 still works.

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.