Maths Olympiad Prep

Library / /110 of 144

Algebra Difficulty 8.6 Shortlist Find the answer

Let r>1r>1 be a rational number. Alice plays a solitaire game on a number line. Initially there is a red bead at 00 and a blue bead at 11. In a move, Alice chooses one of the beads and an integer kZk \in \mathbb{Z}. If the chosen bead is at xx, and the other bead is at yy, then the bead at xx is moved to the point xx' satisfying xy=rk(xy)x'-y=r^k(x-y).

Find all rr for which Alice can move the red bead to 11 in at most 20212021 moves.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Consider the setup of Alice's solitaire game on the number line. Initially, there is a red bead at position 0 0 and a blue bead at position 1 1 . During each move, Alice chooses an integer k k and a bead to move. If the red bead is at position x x and the blue bead at position y y , the chosen bead at x x will be moved to the new position x x' such that:

xy=rk(xy). x' - y = r^k (x - y).

Initially, the red bead is at x=0 x = 0 and the blue bead at y=1 y = 1 , hence the difference is xy=1 x - y = -1 .

The objective is to determine all values of r r for which the red bead can be moved to 1 1 in at most 2021 moves.

### Analysis

The condition for moving the red bead from 0 to 1 can be expressed mathematically. We want the final position of the red bead, after a series of moves, to be equal to the position of the blue bead, y=1 y = 1 .

1. Expression of Move:
xy=rk(xy) x' - y = r^k (x - y) . Hence, the red bead's new position x x' is:
x=y+rk(xy). x' = y + r^k (x - y).
For the red bead (initially at 0) to reach 1, we need:
x=1. x' = 1.
Substituting the initial position (x=0 x = 0 , y=1 y = 1 ), the condition becomes:
1=1+rk(1), 1 = 1 + r^k(-1),
0=rk, 0 = -r^k,
which is not feasible. So what we need instead is:
rk=1. r^k = 1.

2. **Possible Values of r r **:
For rk=1 r^k = 1 , r r should be such that this product yields a neutral condition after a sequence of operations. Observing that r>1 r > 1 is bounded rationally, we note that:

- Geometric Interpretation:
Moving the red bead means repeatedly scaling the distance between the beads by rk r^k . Achieving rk=a+1a r^k = \frac{a+1}{a} where a a is an integer allows the conditions to be met such that one can achieve the bead's movement to completely cover the original difference-scaled path within a limited number of moves.

- Given the constraint that Alice has 2021 moves, exploring the maximum limit of moves to perform reveals that a a must be such that a1010 a \leq 1010 to satisfy the constraints with 2021 2021 discrete increments potentially covering entire path.

3. Conclusion:
Therefore, for all r r values described by the fraction:
r=a+1a r = \frac{a+1}{a}
where a1010 a \leq 1010 , the condition is met within the given move constraints.

{r=a+1a,a1010} \boxed{\left\{ r = \frac{a+1}{a}, a \leq 1010 \right\}}
This characterization allows transitioning the red bead from 0 to 1 in precisely 2021 \leq 2021 moves for the specified values of r r .

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.