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.