Problem
of the
Week

PROBLEM 69

Starting with any finite sequence of non-negative integers,  S = n1, n2, n3,...,nk, we perform the following "move":

 If ni = i, replace ni by 0 and add 1 to each nj, where j < i.

You keep performing moves on resulting sequences until no more legal moves remain.   For example, starting with the sequence 1,1,3, you have the following possible chain of moves: 

1,1,3;   2,2,0;  3,0,0.

But you also have the following possible chain of moves:

 1,1,3;  0,1,3;  1,2,0;  0,2,0;  1,0,0;  0,0,0

So the sequence 1,1,3 can be moved to 0,0,0 in five moves.

Now the question:  From which sequence of length k can you eventually reach the sequence of all zeroes while making the most moves possible?  What is this chain of moves?

For further interest:   What happens if you want to make the fewest moves possible?

For the more adventurous:  Answer the same questions, but assume that you "play" on sequences of infinite length.


Go to the Problem of the Week Home Page

You are visitor number 3413 to this page.