## April 2002

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 ponder@il.ibm.com.

*If you have any problems you think we might enjoy, please send them in. All replies should be sent to:* ponder@il.ibm.com

**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 ponder@il.ibm.com.