Dan Asimov: Warren brings up the very interesting question: For any such "0-modification" of the set {-1,1}^n (i.e., so that some components of some vectors become 0, the rest remaining unchanged), what is the smallest number f(n) such that there is always a nonempty subset S of modified vectors summing to the 0 vector, with #(S) <= f(n) ???
-- 1. In the Amit proof the initial vector which Asimov had taken as all 1's, could instead be taken to be anything... basically, we can change the signs of all the Jth entries of each vector, for any particular J, and do this repeatedly for different J, before we begin Amit's proof. So there are really 2^n different such proofs and we can ask which one yields the smallest 0-sum set. How much does that help? I do not know. If we believed that the map from v(j) to v(j+1) used in the Amit Alon proof acted like a random map on a 2^n-element state space, then we would expect a cycle of length 2^(n/2) roughly, hence subset size upper bounded by this. I see little reason to believe that, though. 2. Another thing is, in my old solution of a modified easier version of Asimov's vector puzzle -- where I asked merely that two distinct subsets exist whose sums were either equal or negations -- that proof method had the advantage that you could get bounds on the size of the two subsets. Specifically, the number of ways to choose a subset of cardinality <= S each is roughly 2^(n*S) / S! and the number of possible vector sums (identifying negations) is at most roughly (1/2) * (2*S+1)^n so if we ask for the threshold S at which the former first exceeds the latter, we get S=3 for large n. 3. That suggests the conjecture that f(n) remains bounded as n-->infinity. 4. However, we could instead conjecture that f(n) grows unboundedly; and hope to prove it by creating a good strategy for the evil child. We have f(1)=2 and earlier posts showed f(2)>=3 and f(3)>=5.