[math-fun] continuum version of vector problem
Hmm, ok, seems I did not make as craftmanlike a problem as I thought, sorry. DISCRETE VERSION: (2k)^n vectors, each n entries from +-{1,2,3,...,k}. Child replaces subset of vector entries by integers of same sign (or 0) and smaller absolute value. To prove: modified vectors still must have a nonempty subset which sums to 0-vector. SOLUTION: similar to the Alon Amit proof (which had been only for the case k=1). CONTINUUM VERSION: Real n dimensional vectors, each entry from real interval [-1,1]. I guess we had better exclude 0 though, otherwise the answer "use the 0-vector, which is immune to modification" kinds of screws things up. Child replaces subset of vector entries by reals of same sign (or 0) and smaller absolute value. To prove or disprove: modified vectors still must have a nonempty subset which sums to 0-vector. (NON)SOLUTION: Well... I should give you more time before reveal. But I believe I have a solution in which "sum" means what sum normally means, for any subset of cardinality which is either finite or countably infinite. I suspect one can also use same proof idea to work for where "sum" means "Lebesque integration" provided the child's mapping function obeys some kind of Lebesque-measurability postulates, but I'd need to bone up on that stuff. If the child's map function obeys other more restrictive postulates, then some other interesting stuff happens... -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
On 7/3/2012 11:38 AM, Warren Smith wrote:
Hmm, ok, seems I did not make as craftmanlike a problem as I thought, sorry.
DISCRETE VERSION: (2k)^n vectors, each n entries from +-{1,2,3,...,k}. Child replaces subset of vector entries by integers of same sign (or 0) and smaller absolute value. To prove: modified vectors still must have a nonempty subset which sums to 0-vector. SOLUTION: similar to the Alon Amit proof (which had been only for the case k=1).
CONTINUUM VERSION: Real n dimensional vectors, each entry from real interval [-1,1]. I guess we had better exclude 0 though, otherwise the answer "use the 0-vector, which is immune to modification" kinds of screws things up.
But if you exclude the 0 vector then the malicious child can just set all the vectors to zero except one; and then there is no remaining subset that sums to zero. I think you need to prohibit 0 as a substitution value. Brent Meeker
Child replaces subset of vector entries by reals of same sign (or 0) and smaller absolute value. To prove or disprove: modified vectors still must have a nonempty subset which sums to 0-vector. (NON)SOLUTION: Well... I should give you more time before reveal. But I believe I have a solution in which "sum" means what sum normally means, for any subset of cardinality which is either finite or countably infinite. I suspect one can also use same proof idea to work for where "sum" means "Lebesque integration" provided the child's mapping function obeys some kind of Lebesque-measurability postulates, but I'd need to bone up on that stuff. If the child's map function obeys other more restrictive postulates, then some other interesting stuff happens...
participants (2)
-
meekerdb -
Warren Smith