wow. Extremely simple puzzle, extremely simple solution, yet incredibly hard to think of the solution. Comments: 1. Essentially the same proof will show that the final set which vectors-sums to 0, has cardinality <= n+1. 2. This in turn can be used to see that the number of nonidentical 0-sum subsets must be at least (2^n)/(n+1). 3. Essentially the same proof will also show: given all (2*k)^n vectors with entries from {-k, 1-k, ..., -2, -1, 1, 2, ... k-1, k}, where note 0 is missing -- or actually any negation-symmetric 0-omitting set will do -- if the evil child changes an arbitrary subset of entries to decrease their absolute values, then the resulting modified set of vectors still has a nonempty subset with vector sum=0, and this set has cardinality <=k*n+1, and there are at least (2*k)^n / (k*n+1) nonidentical such 0-sum sets.
On 6/27/12, Warren Smith <warren.wds@gmail.com> wrote:
wow. Extremely simple puzzle, extremely simple solution, yet incredibly hard to think of the solution.
Comments: 1. Essentially the same proof will show that the final set which vectors-sums to 0, has cardinality <= n+1.
--sorry, (1) was just wrong.
2. This in turn can be used to see that the number of nonidentical 0-sum subsets must be at least (2^n)/(n+1).
--hence (2) also is wrong.
3. Essentially the same proof will also show: given all (2*k)^n vectors with entries from {-k, 1-k, ..., -2, -1, 1, 2, ... k-1, k}, where note 0 is missing -- or actually any negation-symmetric 0-omitting set will do -- if the evil child changes an arbitrary subset of entries to decrease their absolute values, then the resulting modified set of vectors still has a nonempty subset with vector sum=0.
--but this part of (3) still looks good.
participants (1)
-
Warren Smith