IBM Research | Ponder This | April 2002 challenges
Skip to main content

Ponder This

April 2002

<<March April May>>

Ponder This Challenge:

This month's puzzle is based on a suggestion by John G. Fletcher.

Consider a small integer k and a large positive integer N.
Start with a vector (x(1),x(2),...,x(k)) of nonnegative integers between 0 and N, inclusive; call that an "initial state for k and N". Let a "step" be the process of replacing each entry by the absolute value of the difference between that entry and its right-hand neighbor (where x(1) is x(k)'s right-hand neighbor).
That is, let y(i) = |x(i)-x(i+1)| for i=1,2,...,k-1;
let y(k) = |x(k)-x(1)|; and then
let x(i) = y(i) for i=1,2,...,k.
The vector (8,9,2,6) becomes, after one step, (1,7,4,2),
since 1=|8-9|, 7=|9-2|, 4=|2-6|, and 2=|6-8|.

Define a "final state" to be a state where there is some integer j such that all x(i) are either 0 or j.
(This includes the possibility that all x(i) are 0.)
Applying a "step" to a "final state" will again yield a "final state" with the same value of j.

It's not hard to see that for each initial state, a finite number of steps will lead to a final state. For a given k and N, different initial states will take longer than others to reach a final state. Define the "lifetime" of an initial state to be the number of steps required to reach a final state.
The lifetime of (8,9,2,6) is 6: successive steps give (1,7,4,2),(6,3,2,1), (3,1,1,5), (2,0,4,2), (2,4,2,0), (2,2,2,2), which is a final state.

The problem (part 1):
For each k between 1 and 12, decide whether there exist constants c(k)>0 and d(k), such that for each N large enough, there is an initial state for k and N whose lifetime is at least c(k)*N-d(k).
(Notation: c(k) is a constant c which depends on k; it is not c times k.)
Your answer will be of the form:
"For k=3,4,11, the answer is no, and here is why: ... .
For k=1,2,5,6,7,8,9,10,12, the answer is yes, and here is why: ... ."

The problem (part 2):
What about k=13?

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the

If you have any problems you think we might enjoy, please send them in. All replies should be sent to:


Challenge: 04/01/2002 @ 9:00 AM EST
Solution: 04/30/2002 @ 3:00 PM EST
List Updated: 04/30/2002 @2:40 PM EST

People who answered correctly:

Part 1 Correct

Vitaly Stakhovsky (4.5.2002 @ 11:00 AM EDT)
Joseph DeVincentis (4.5.2002 @ 11:00 AM EDT)
Jacques Willekens (4.5.2002 @ 2:00 PM EDT)
Devin Sezer (4.13.2002 @ 6:25 PM EDT)
Jean Flies (4.15.2002 @ 5:12 AM EDT)
Hassan Masum (4.23.2002 @ 2:00 PM EDT)
Christof Schmalenbach (4.26.2002 @11:00 AM EDT)
Corrado Falcolini (4.30.2002 @2:40 PM EDT)

Part 2 Correct
Vitaly Stakhovsky (4.5.2002 @ 2:00 PM EDT)
Jacques Willekens (4.8.2002 @ 10:00 AM EDT)
Jean Flies (4.15.2002 @ 5:12 AM EDT)
Hassan Masum (4.23.2002 @ 2:00 PM EDT)
Christof Schmalenbach (4.26.2002 @11:00 AM EDT)

Attention: If your name is posted here and you wish it removed please send email to the