PART 1.
the pair of integer(N,K) has the form(P^a,P^b) where P is prime,and a,b is integer)

first any pairs except this form can't make such a sequence.

result 1:if (x*y,k) can make such a sequence for a win,then (x,k)can also make a sequence. because if S1S2S3..... is the sequence for (x*y,k), we only look at the bit with interval y in each Si,and restrict the genie can only do Rot(w,y*i),and so we obtain a seqence for (x,k)


result 2:if (x,k*d) can make such a sequence for a win,then (x,k)can also make a sequence.this can be obtained by restricting the entries in mod k.

result 3:if GCD(n,k)=1, there is no such a sequence for (n,k).
obviously, the vector 000...0 , 1111...1 ,2222...2, ......will surely be changed to 000...00 .
consider two other vector X=x1x2x3...., Y=y1y2y3.....
if X+Rot(Y,j) can reach to 0000..00 or 1111...11 or 222..22 or....,then X as the initial vector can surly be changed to 000..0.
so:
x1+y1=x2+y2=x3+y3....=xn+yn
x1+y2=x2+y3=x3+y4....=xn+y1
then
y1-y2=y2-y3=........ =yn-y1=t (mod k)
(y1-y2)+(y2-y3)+....(yn-y1)=nt=0 (mod k)
note that (n,k)=1,t has no solution between 1 and k-1.
so there is no other vector can surely reach to these status.

According to result1,2,3,we can say that (N,K) must have form(P^a,P^b)



Then we prove for(P^a,P^b), we can make a sequence to garantee a win.
we establish the relationship between this problem and vector difference.

for a vector A=a1a2a3a4.....an
we define differece D1(A)=(a1-a2)(a2-a3)....(an-a1)
D2(A)=D(D1(A)),and so on.
result 1:
if Di(A)=000..00 for all vector A in C,there is a sequence which can garantee all vector in S changed to 000..00.
proof:
Basis:trivally,if all A in C satisfy D1(A)=000..00 , all vector in C can be led to 000..00
Induction:suppose Di(A)=000..00 for all vector A in C,there is a sequence which can garantee all vector in C changed to 000..00.
given a vector B=b1b2b3...bn,Di+1(B)=0000..00 but Di(B)<>000..00
we can easily see the following as Dn(B-Rot(B,j))=Dn(B)-Dn(Rot(B,j))=0:
(b1-b1)(b2-b2)..(bn-bn) is in C.
(b1-b2)(b2-b3)..(bn-b1) is in C.
....
(b1-bn)(b2-b1)..(bn-bn-1) is in C.
this time we find that (-B)=(-b1)(-b2)(-b3)...(-bn) is vector which can surly lead B to set C,no matter how the genie rotate (-B)
suppose S1S2S3....Sd is the sequence for vector set C,then S1S2...Sd(-B)S1S2...Sd will lead all element in C+{B} to 000..00 (where (-B)=(-b1)(-b2)(-b3)...(-bn) )
repeat this process for all B which Dn+1(B)=000..000, we can obtain this result.

result 2:
for the integer pair(P^a,P), for all such vectors A, D_P^a(A)=000...000
proof:
the ith digit of D_p^a(a1a2a3.....an) is ai-C(p^a,1)*a(i+1)+C(p^a,2)*a(i+2)-C(p^a,3)*a(i+3)+.......-ai=0(mod P^b) because C(P^a,i)=0(mod P).
where C(x,y) is Binomial coefficent.

result 3
if all vector A in the pair (p^a,p^x)) x<b have Dn(A)=000..00, for all vector A' in pair (p^a,p^b) there exists n' such that Dn'(A')=000..00
proof
given A' in pair(p^a,p^b),we can see Dn(A') has this form, all entries is 0 or multiple of p. if we continue to do the difference, it is equivalent to do the difference in (p^a,p), and will finally get 000..00.


from result 2 and 3,we know for all vector A in (p^a,p^b), there exist a n that Dn(A)=000..00. And using result 1,we can get that for pair of (P^a,P^b),there must be a sequence for a win.


PART 2:

when N<>2^k M=f(N) when f(N)>N/2.
M=N-f(N) otherwise.

where f(x)is the number of zero in row x in pascal triangle mod 2.

f(x) can be calculate by using Lucas identity:
n,k are represented in p-ary number system.
n=n1n2n3...nr
k=k1k2k3...kr
then C(n,k)=C(n1,k1)*C(n2,k2)*....C(nr,kr) mod P

we represent x in binary-system. o1(x) donates the number of 1's in this representation.
f(x)=x-2^o1(x-1)

Jian Li