September 2004
ANSWER:
Part 1:
A solution will exist if and only if K and N are both powers of the same prime integer P.
The "only if" part is similar to the proof from July 2004. If K and N are not both powers of the same prime integer P, and both are at least 2, then we must have two different primes P,Q, where K is a multiple of P, and N is a multiple of Q. Start with a vector V whose entries V(1) and V(1+(N/Q)) are different mod P. For any W, it is possible to find a rotation amount J such that V'=V+Rot(J,W) still has V'(1) and V'(1+(N/Q)) different mod P. So the genie can always keep us from winning.
We will construct a solution for N=P^S and K=P^T, where P is a prime. We will use parentheses for the index within a vector V, and square brackets for the time of a move, so that V(x)[i] will be the value of the x position in V at time i, and V[i] will denote the vector at time i.
Let K=N=P be a prime. On move number i, between 0 and P^P-1, let P^m be the largest power of P dividing i. Select a monic integer polynomial Q(x) of degree m, reduced mod P. (That is, the coefficient of x^m is 1, and no higher power of x appears.) Define W by W(x)[i]=Q(x) mod P for x=0,1,...,P-1.
For example, if P=3, m=0, the only choice for Q is Q(x)=1, so Q(0)=1, Q(1)=1, Q(2)=1, and W=(1,1,1).
If P=3, m=1, we have three choices for Q: Q(x)=x, Q(x)=x+1, or Q(x)=x+2.
The choices for W would be (0,1,2), (1,2,0), or (2,0,1). If P=3, m=2,
we have nine choices for Q: Q(x)=x^2+Ax+B, A,B=0,1,2.
W can be (0,1,1), (1,2,2), (2,0,0), (0,2,0), (1,0,1), (2,1,2), (0,0,2), (1,1,0), or (2,2,1). For P=3, m=3,
any choice will work for W. In the following string: daabaabaacaabaabaacaabaabaa,
let "a" denote m=0 (our choice of W is fixed),
"b" denote m=1 (three choices for W),
"c" denote m=2 (nine choices for W),
and "d" denote m=3 (W is free).
An important feature is that if W represents a monic polynomial Q(x) of degree m, with m<P, then Rot(J,W) also represents a monic polynomial of degree m, namely Q(x+J).
Now consider two moves, at times i and j, with i<j between 0 and P^P-1 inclusive. The base-P representations of i and j first differ in the m position (for some m between 0 and P-1), and they differ by t (for some t between 1 and P-1). Then we know that between these two moves we have used a monic polynomial of degree m exactly t times, and the other times we have used polynomials of lower degree. Then the difference between V(x)[j] and V(x)[i] is a polynomial whose leading coefficient is t*x^m; in particular, it is nonzero. So the vectors V[i] and V[j] are different. That means the P^P vectors V[i] at times i=0,1,...,P^P-1 are all different. Therefore one of them is 0, since there are only P^P possibilities.
So if N=K=P, we have solved the problem, with a sequence of length K^N=P^P.
We will induct on N first, then on K, to find sequences that work for any N=P^S and K=P^T; these sequences will always have length K^N.
Suppose we have a sequence W1 that works for (N=P^{S-1}, K=P). We will construct a sequence W that works for (N'=P^S, K=P). The vector V has an index z that ranges from 0 to N'-1=P^S-1; let z=x*N+y, where x ranges from 0 to P-1, and y ranges from 0 to N-1. At time i, let m be the highest power of N dividing i, and suppose i=a*N^{P-1}+...+c*N^m, where c is nonzero. Set W(x*N+y)[i]=W1(y)[c]*x^m (mod P).
Why does this work? For each y between 0 and N-1 and each time i, think of the function taking x to W(x*N+y). This can be expressed as a polynomial of degree at most P-1 (mod P). At time steps i divisible by N^{P-1}, the coefficient of x^{P-1} changes, with a pattern given by some rotation of W1(y)[i/N^{P-1}]. At other times, the coefficient of x^{P-1} does not change, because we are adding a lower degree polynomial. By the properties of W1, we will eventually get the coefficients of x^{P-1} to work out right. Then in the next N^{P-1} moves (before the next time that i is divisible by N^{P-1}), we keep track of the coefficients of x^{P-2}, and eventually get those right. The process is similar to the solution of the July 2004 puzzle.
So we have produced a sequence of length K^N that works when K=P and N=P^S.
Now we induct on K.
If we have a sequence W1 that works for (N=P^S, K=P), and a sequence W2 that works for (N=P^S, K=P^{T-1}), we create a sequence W that works for (N=P^S, K=P^T). Namely, W will have K^N=P^{N*T}=(P^N)*(P^{N*(T-1)}) steps. At time steps which are multiples of P^{N*(T-1)} will be the sequence W1. In between each two elements of W1, we will take the sequence W2, drop the first element (its position will be taken by the element of the sequence W1), and multiply by P. To find out when we win, we look at the initial values of V mod P to determine a game with (N=P^S, K=P), and figure out when W1 would have won that game. The intervening elements of W2 have been multiplied by P, so they don't matter in this reduced game. Now we know which segment of length (P^{N*(T-1)}) to look at, and it is easy to see that somewhere in this particular W2 sequence, we will win the game. So, by induction, when N=P^S and K=P^T, we win with a sequence of length K^N=P^{(P^S)*T}.
Part 2:
If N=Q*2^L where Q is odd and 2^L is a power of 2, then M is at least (N+2^L)/2 = (2^L)*(Q+1)/2. For each integer S between 0 and 2^L-1, consider the Q positions whose addresses are equivalent to S mod 2^L. Since Q is odd, there is a majority of at least (Q+1)/2 sharing the same value. Build a vector V' of length 2^L with V'(S) denoting this majority value. Consider a sequence of moves W' that wins with N'=2^L and K=2. Convert each move W' to a move W on vectors of length N, by just putting Q copies of W' in a row. On the move where W' has won, our real game has at least (Q+1)/2 entries equal to 0 in each of 2^L residue classes.
In experiments with small N (up to 13), we have not found any larger values of M than those predicted by this analysis. But we don't know these to be the right values of M.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com