Partial solutions were also received from Joshua Durham, Ray Kremer.  Additional partial solutions were submitted by Jure Velkavrh and Ivan Lisac, Maxim Ovsjanikov, Philippe Fondanaiche, Burkart Venzke.

Let's start with a sequence  n₁, n₂ ,..., n_kwhich can be moved to all zeroes.  In each move, one of the entries is made zero; I'll say that entry was cleared by the move.

It's easy to see that the following "rules" must be followed:

1. each entry n_i must be no greater than i after each move,
2. if there are two entries which may be cleared, it's the smaller of the two which must be cleared.

and was increased one time for each time every time that a higher entry was cleared.  Hence  is the number of times the i 'th entry had the value i, i.e.

As an example, consider the case k = 8.  We start with q₈ = 1, n₈ = 8.  Then 7q₇ =  n₇ +q₈, which gives q₇ = 1, n₇ = 7. We proceed to 6q₆ = n₆ + q₇ +q₈, and q₆ = 1, n₆ = 4. Similarly, q₅ = 1, n₅ = 2. Now it gets interesting.  We next have 4q₄ =  n₄ + q₅ + q₆ +q₇ + q₈ = n₄ + 4, and q₄ = 2, n₄ = 4.  Completing the calculations gives q₃ = 3, n₃ = 3; q₂ = 5, n₂ = 1; q₁ = 2, n₁ = 1.  The unique longest sequence of length 8 which can be cleared is therefore 1,1,3,4,2,4,6,8.

The total number of moves required is the sum either of n_i 's or of the  q_i's, both sums being, of course, equal; in the above example this number is 29.   I know of no closed form for this number, but would love to hear of one.

Note that the formula above for computing the entries can be easily automated and programmed into even the simplest of programmable calculators.

You are visitor number 3632 to this page.
Page last updated 18 October 1999.