Evil child Julian says f(n)>n by preserving the all-ones vector, and in every other vector zeroing everything but one of the -1s. But in fact, f(n)=2^n ! Have the evil child zero everything before the last +1 in each vector (leaving (-1,…,-1) alone), and suppose that the nonempty subset S sums to 0. Since none of the modified vectors has a 0 in the last position, one of the modified vectors in S must have a -1 in the last position. Then its second-to-last position is nonzero, so there must be some (possibly the same) modified vector in S with a -1 in the second-to-last position. Continuing like this, there must be a modified vector in S with first entry -1, which could only be (-1,…,-1). In order for the sum to equal zero, there must be a modified vector in S with first entry +1. This must be (1,-1…,-1). This gives a sum of (0,-2,…,-2), so there have to be (at least) two modified vectors in S with second entry 1, and since there are only two such modified vectors (the original vectors must have had -1s in all but the first two positions and second entry +1), we must include them both. The sum of the vectors so far is (0,0,-4,…,-4). To get rid of that first -4, we need to include in S all four of the modified vectors which are equal to (0,0,1,-1,…,-1) (those that began life as (±1,±1,1,-1,…-1)), which gives us a running sum of (0,0,0,-8,…,-8). Continuing like this, we must include in S all eight (0,0,0,1,-1,…,-1)s, all sixteen of those with fifth entry +1, etc. Every modified vector must have a +1 in some position or be (-1,…,-1), so S contains all 2^n modified vectors. --Julian --------------------
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. _______________________________________________