[Guest]

A ribbon comprises a line of squares numbered sequentially from 0 to n. A marker can initially be placed on any square. After positioning such a marker, it may be repositioned by moving it p squares to the right or q squares to the left, provided that one does not fall off the ribbon. The numbers p and q are mutually co-prime.

Show that n = p + q – 2 is the smallest value for n which permits all squares to be visited after a successive number of moves.

Edited November 10, 2009 by jerbil

[Guest]

One algorithm I thought of would be:

Call your staring position O at one end of the ribbon (if p>q O is on the left, otherwise O is on the right).

1. Move p squares.

2. Then repeatedly move q squares back as far as you can.

3. Repeat steps 1 & 2 until you get back to O.

Each time you do step 1 you will be on square (aq + b). b will be different each time you repeat the steps until you get back to O. As you move back (step 2) you will visit all the squares whose number has a remainder b when divided by q. The largest square you be on at the end of step 2 would be q-1. At the end of the next step 1 you will be on p+q-1.

Very close to the answer but it would appear I'm overlooking something somewhere. Any ideas?

[Guest]

You could choose to start on a square so that square q-1 was the last one you visited. This would make p+q-2 the largest square you needed to visit.

Nice puzzle gerbil.