September 2004
Puzzle for September 2004.
This month we have two more variants on the blindfold-and-tumblers problem, which appeared here in July 2004 and November 2002, originally in Martin Gardner's February 1979 column.
There are fixed positive integers N and K, each at least 2. We have an unknown vector V of length N of integers between 0 and K-1 inclusive. During each move, we propose another vector W of length N, of integers between 0 and K-1. A genie selects a secret integer J between 0 and N-1 and rotates W by J positions: Rot(W,J) is the last N-J entries of W, followed by the first J entries of W. The genie then replaces V by (V + Rot(W,J))(mod K). If the new value of V is all 0, we win; otherwise we continue to play.
Part 1 (from Joe Fendel):
For what pairs of integers (N,K) is there a fixed finite sequence of moves (a sequence of vectors W) such that if we apply this sequence in order, we are guaranteed to win by the time the sequence is finished? Prove that these pairs admit such a sequence, and that no other pairs do.
Part 2 (from Dan Dima):
Fix K=2. For each N, there is a largest integer M such that we can produce a sequence of vectors W and guarantee that if we apply this sequence in order, we will guarantee that on one of the moves, at least M elements of V are zero. (So we have a more relaxed definition of "winning".) What can you say about the relation between N and M?
This month we will entertain solutions for one or both parts.
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:
09/01/2004 @ 9:00 AM ET
Solution:
10/01/2004 @ 8:30 AM ET
List Updated:
09/01/2004 @ 9:00 AM ET
People who answered correctly:
Part I:
Patrick J. LoPresti (9.01.2004 @05:58:52 PM EDT)
Luke Pebody (9.02.2004 @04:24:26 AM EDT)
Hagen von Eitzen (9.02.2004 @08:08:03 AM EDT)
Jon Derryberry (9.09.2004 @04:58:21 PM EDT)
Michael Brand (9.12.2004 @04:34:42 PM EDT)
Daniel Bitin (9.12.2004 @05:38:16 PM EDT)
John G. Fletcher (9.12.2004 @06:05:20 PM EDT)
Dan Dima (9.13.2004 @01:31:29 PM EDT)
Clive Tong (9.14.2004 @04:46:55 PM EDT)
Li Jian (9.14.2004 @11:39:18 PM EDT)
Evgeniy Tarassov (9.17.2004 @11:58:37 AM EDT)
Hao Wu and hikaru (9.19.2004 @08:22:51 AM EDT)
Aditya K. Prasad (9.27.2004 @12:12:22 PM EDT)
Part II:
John G. Fletcher (9.12.2004 @06:05:20 PM EDT)
Michael Brand (9.19.2004 @04:57:10 AM EDT)
Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.