Puzzle: Consider the set of all 2n vectors in n dimensions, each of whose entries is either +1 or -1. (Of course, if you add them all up you get the all-zero vector.) An evil child maliciously replaces some subset of the n2n vector entries by zeros.
A. Prove that, no matter what the child does, some nonempty subset of the vectors still will exist that sums to the all-zero vector.
B. Suppose the child acts "maximally maliciously" trying to force the the cardinality of the smallest such 0-sum subset to be as great as possible. Let the minimum possible cardinality of a 0-sum subset, assuming maximally-malicious child, be called f(n). What is f(n)?
C. Now consider the set of all (2k)n vectors in n dimensions, each of whose entries is either +1,+2,+3,...,+k or -1,-2,-3,...,-k for some integer k≥1. (Again, of course, if you add them all up you get the all-zero vector.) An evil child maliciously replaces some subset of the vector entries by integers of smaller absolute value and the same sign (or zero). For example she might replace a -5 by either -3 or -4 or 0, but would not replace it by +3, +5, or -6. Prove that, no matter what the child does, some nonempty subset of the vectors still will exist that sums to the all-zero vector.
D. Now consider the continuum set of real n-dimensional vectors, each entry from real interval [-1,1] excluding 0. The evil child replaces a subset of vector entries by reals of same sign (or 0) and smaller absolute value. Prove or disprove: the vectors, after child modifies them, still must have a nonempty subset which sums to the 0-vector.
E. What if (in addition to the part D's rules) the child must replace x by y where y is a continuous function of x?
History of puzzle: Michael Brand posted puzzle A on an IBM research puzzle website on 02/03/2003 (he also had a solution). People who answered correctly within 1 month:
John G. Fletcher, Trevor Graffa, Airat Chanyshev, Peter Johansson, Steve Horvath, Stephen Martin, Swastik Kopparty, Klaus Hoffmann.
Puzzle B was posed by Dan Asimov in 2012 (and A re-posed by both Asimov and Ehud Friedgut in 2009), whereupon part A was solved by Alon Amit. Part B was solved by Julian Ziegler Hunts (then age 15) in only a few minutes solving time! The generalizations in parts C and D are by Warren D. Smith (although we admit the one in part C is rather cheap, and the solution for D is still somewhat sketchy).
Although the puzzle has little to do with voting/democracy, I could not resist it since it is remarkably simple to state and has remarkably simple solutions, but some of them are remarkably difficult to find.
Answer A: Here "modified vector" refers to a vector in the set of vectors after mangling by the child. (Any of these may of course equal the original unmodified vectors.) We inductively construct a sequence {v(k)} of n-vectors lying in {0,1}n
Let v(0) be the modified vector that started life as all +1's.
Given v(k), let u(k) be the modified vector that started life with -1's precisely in the same places that v(k) has its +1's. Now define:
Then v(k+1) must also lie in {0,1}n. This gives an infinite sequence of v(k) in {0,1}n. Since {0,1}n is finite, indeed has cardinality=2n, we must have v(k) = v(k+r) for some k≥0 and least r≥1. Then
is a sum of r modified vectors that sums to the all-0 vector. All the summands necessarily are distinct. Q.E.D.
Answer B: A quick proof that f(n)≥n+1 arises by preserving the all-ones vector, and in every other vector zeroing everything except one of the -1s.
But we can do much better. We prove f(n)=2n. Have the evil child zero everything before the last +1 in each vector except leaving (-1,-1,-1,...,-1,-1,-1) alone. Denote the least-cardinality nonempty subset of modified vectors summing to all-0 by "S." Since none of the modified vectors has a 0 in the last position, at least 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 a -1 in the third-to-last position... and so on... finally concluding there must be a modified vector in S with first entry = -1. This vector could only be (-1,-1,-1,...,-1,-1,-1). Hence in order for the full sum to equal zero, there must also be a modified vector in S with first entry +1. This must be (1,-1,-1,...,-1,-1,-1). This gives a sum-so-far of (0,-2,-2,-2,...,-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,-4,...,-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,-1,...,-1,-1,-1), i.e. those that began life as (±1,±1,1,-1,-1,-1,...,-1,-1,-1), which gives us a running sum of (0,0,0,-8,-8,-8,...,-8,-8,-8). Continuing like this, we must include in S all eight (0,0,0,1,-1,-1,-1,...-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,-1,...,-1,-1,-1), so S contains all 2n=1+2+4+8+...+2n-1+1 modified vectors. Q.E.D.
Answer C: We inductively construct a sequence {v(k)} of n-vectors lying in {0,1,2,...,k}n.
Let v(0) be the modified vector that started life as all +k's.
Given v(k), let u(k) be the modified vector that started life with extries that are the negatives of v(k)'s positive entries, and with all other (pre-modification) entries +1. Now define:
Then v(k+1) must also lie in {0,1,2,...,k}n. This gives an infinite sequence of v(k) in {0,1,2,...,k}n. Since {0,1,2,...,k}n is finite, indeed has cardinality=(k+1)n, we must have v(k) = v(k+r) for some k≥0 and least r≥1. Then
is a sum of r modified vectors that yields the all-0 vector. All the summands necessarily are distinct. Q.E.D.
Answer D: Regard a real number x with 0<x≤1 as being specified in binary by an infinite string of 0's and 1's after a binary "decimal point." This string is unique except for the possibility that some suffix 10000... could be replaced by 01111... and we fully-uniquify it by insisting on the former. Now have the Evil Child employ the following map x→A·F(x) for positive-real x≤1: Make the 2j!th bit of F(x) be the same as the jth bit of x for each j=1,2,3,..., and let all other bits of F(x) be 0. Finally, multiply F(x) by a fixed constant A with 0<A<1. For negative x, our Evil child will instead employ the map x→-B·F(-x) for some other fixed constant B with 0<B<1. Note this map is a strict-monotonic-increasing (but not continuous – it has jumps) function of x (which always decreases |x| if |x|>0) when -1≤x≤1.
What should A and B be? If we choose them at random uniformly from (0,1) then with a decent probability of success, all the below claims will work. The reals chosen by the child then all will lie on a Cantor-like set which has the same cardinality as the reals, but measure zero. Further, even if we "bloat" the "Jth level" of the Cantor set by expanding all its points into tiny real intervals of width 1.01×2-2(J+1)!, then the resulting set (which contains the entire Cantor set at level ∞ even though J is finite) will no longer have zero measure but its measure still (for any decently large J) will be very small both in an absolute and relative (density) sense. Now if we consider adding together any nonempty set of ≤J reals selected from this level-J-bloated Cantor set, then the resulting set of possible sums will still have very small measure which goes to zero extremely rapidly when J→∞. My point is that a factor-A scaling of the sum-of-≤J measure will, if A and B are chosen randomly, probably overlap nowhere with the factor-B scaling, in the J→∞ limit. You can argue this quantititively by considering all ≈2jj possible "blobs" in the 2-dimensional measure for AΣ1 × BΣ2, and arguing the blob-widths are ≤[1.01max(A,B)]j2-2j! and in general once j is large enough no blob should intersect any slope=1 diagonal line. Hence no sum of any finite – or even countably-infinite – nonempty multiset of child-modified positive reals, can exactly cancel any sum of any finite or countably-infinite nonempty multiset of child-modified negative reals. This in the finite-sum case is essentially because the Cantor set has measure=0, and the set of allowed sums of any finite set of Cantor-elements also has measure=0 and will in general exhibit zero overlap with the other measure=0 set (the B-scaling). Another way to see it is to argue that A/B will generically be irrational in which case any finite sum of Cantors times A (necessarily a rational multiple of A) cannot equal any finite sum times B. It's a bit trickier if we allow sums with a countably-infinite number of summands. (For example, "sums of rational numbers" where we allow a countable infinity of summands yields all real numbers, which have full measure even though the rationals have zero measure.) However, the quantitative density argument I just gave seems to take care of that objection thanks to me intentionally making 2j! be a very fast-growing function of j, provided we agree, in our countable-sums, to employ only a bounded number (or not-too-quickly-growing-with-J number) of level-J summands. That is, if we agree outside any ball about 0 of radius R, to use at most a number of summands that does not grow ridiculously fast (over doubly exponentially in 1/R... and we can change "doubly" to any larger number...) as R→0+.
Summary: We've shown how the child can stop any finite sum from being the 0-vector, and also that she can by the same strategy also stop a large class of countably-infinite sums (which we can restrict arbitrarily much...) from including the 0-vector. In particular, if the |summands| fall like o(1/m) for the mth summand, then no such sum can be 0. Q.E.D.
Answer E: Now what if the child's modification of a vector has to be a continuous function of that vector? In that case, we can apply a version of the the Alon Amit proof argument above, to map sums-of-modified-vectors lying within [0,1]n into others (by adding another summand which is a continuous function of the old sum). For an example of such a map F(v), add to the current vector v, the new vector which arose from the child's modification of the vector whose entries are the negative of v's corresponding entry. This map, being the composition of two continuous maps, is continuous, and it maps [0,1]n into itself. Hence by Brouwer's fixpoint theorem there must exist a fixpoint of this map, that is a vector v∈[0,1]n with F(v)=v, and indeed fixpoints of all possible orders k≥1, i.e. v such that F[k](v)=v for any particular integer number of iterations k≥1. If any such fixpoint is nontrivial (i.e. v≠0) then we are done: we have a finite sum of modified vectors that equals 0. But if not, i.e. the only fixpoint of any order is the all-zero-vector v=0, then the map F always decreases at least one coordinate and can never increase any coordinate. In that case we can define the "distance" between any two points P and Q to be dist(P,Q)=EuclideanDist(P,0)+EuclideanDist(Q,0) and then apply Banach's fixpoint theorem to see that starting from any v we must by iterating the map converge to the 0-vector, hence we get a countably-infinite sum whose limit exists and is zero (indeed we get an uncountable infinity of such countably-infinite sums). Q.E.D.