Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A ring has cells, numbered to clockwise. A robot starts at cell and each move takes it cells clockwise. Find the least number of moves after which the robot is on cell . Use the extended Euclidean algorithm on and ; the remainders you meet are Fibonacci numbers. Then find the least number of moves after which it is on cell , one cell anticlockwise of the start.
is solvable exactly when divides , and then it has solutions modulo :
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Given. Cell after moves: .
Plan. Solve with the extended Euclidean algorithm, then use .
Step 1. Divide. , , , , , , .
Step 2. Work back. Start from and replace each remainder by the line that made it. The numbers climb the Fibonacci list:
.
Step 3. Multiply out. and . The difference is , so the identity is right.
Step 4. Read off. Modulo the term is , so . The inverse of is .
Step 5. Cell 88. The same identity says . So moves bring the robot to cell .
Check. leaves , and leaves . Also , as it must be: the two answers are negatives of each other modulo .
Answer: moves to reach cell , and moves to reach cell .
Watch out. The most common slip in the back substitution is a lost sign. Always multiply out the identity, as in Step 3. Here a negative coefficient, , is turned into the positive inverse .
Log in to join the discussion.
Loading…