Re: [math-fun] Vector puzzle
I don't think any inductive proof of Kleber's ilk is going to crack this ultra-annoying Asimov vector puzzle, because in the n=3 example with 8 vectors I gave, the minimum subset with 0-sum has cardinality=5, which note is greater than 2^(n-1). Ditto for the 4 vector example with n=2 and min subset cardinality=3. You can permute the columns and change the sign of any column... a fact which seems to have no use. There may be a solution via horrible OVERKILL: Rephrase it as an 0-1 integer programming problem, then show the linear program automatically has an 0-1 integer solution. (This would be equivalent to Asimov's desires.) It is however probably more interesting to go in the other direction: Use whatever Asimov's proof technique is, to discover a new class of linear programs which automatically have 0-1 integer solutions.
participants (1)
-
Warren Smith