IBM Ponder This #077 · 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.

Solution

Best opened after a real attempt

To be added.