June 2012 - mathfun@mailman.xmission.com

Re: [math-fun] Vector puzzle
by Dan Asimov 29 Jun '12

29 Jun '12

P.S. The very poorly run company Earthlink unfortunately condensed the 40 lines I left before the solution to only about 10 lines -- with no warning to me. (It really needed to save 30 or maybe 60 characters that badly???) Sorry about that, and I hope the problem was not spoiled for anyone who didn't want to see a solution. --Dan ________________________________________________________________________________________ It goes without saying that .

2 2

[math-fun] vector puzzle
by Warren Smith 28 Jun '12

28 Jun '12

>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.

2 1

Re: [math-fun] vector puzzle
by Dan Asimov 27 Jun '12

27 Jun '12

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) ??? --Dan ________________________________________________________________________________________ It goes without saying that .

2 1

[math-fun] Heron's formula/Cayley-Menger determinant
by Henry Baker 27 Jun '12

27 Jun '12

The Cayley-Menger determinant form for Heron's formula of the area of a triangle is well known: http://mathworld.wolfram.com/HeronsFormula.html -16 (Triangle Area)^2 = (Determinant "I") |0 a b c| |a 0 c b| |b c 0 a| = |c b a 0| (Determinant "II") |0 1 1 1| |1 0 cc bb| |1 cc 0 aa| = |1 bb aa 0| (c - b - a) (c - b + a) (c + b - a) (c + b + a) = (|c| - |b| - |a|) (|c| - |b| + |a|) (|c| + |b| - |a|) (|c| + |b| + |a|) where a,b,c are the (real) triangle side lengths, and aa=a*a=|a|^2, bb=b*b=|b|^2, cc=c*c=|c|^2. Determinant II is obtained from Determinant I by pre & post multiplication by real diagonal matrices, and vice versa. E.g., see Muir's Theory of Determinants, p.44. I know that determinantal identities are a dime a dozen, but here's one which I believe is new: This time, instead of using a,b,c for the (real) triangle side lengths, I use a,b,c for the _complex_ triangle side _vectors_, arranged head-to-tail so that a+b+c=0, and a',b',c' are the complex conjugates of a,b,c, respectively. Then, -16 (Triangle Area)^2 = (Determinant "III") |0 a b c | |a 0 c' b'| |b c' 0 a'| |c b' a' 0 | (Determinant "IV") |0 1 1 1 | |1 0 cc' bb'| |1 cc' 0 aa'| |1 bb' aa' 0 | Note that Determinant IV is _real_ and is _identical_ to Determinant II, because aa'=|a|^2, bb'=|b|^2, cc'=|c|^2. Determinants III and IV are interconvertible using pre & post multiplication by diagonal matrices with _complex_ entries. We also note that while Determinant IV = II = I can be factored, Determinant III cannot, because |a|=sqrt(aa'), |b|=sqrt(bb'), |c|=sqrt(cc') are not necessarily rational. Matrix III is also a rare example of a _symmetric_ complex matrix that is _not Hermitian_.

1 0

[math-fun] vector puzzle
by Warren Smith 27 Jun '12

27 Jun '12

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.

1 1

Re: [math-fun] reverse-engineering Galton boards
by James Propp 27 Jun '12

27 Jun '12

Dan Asimov rightly points out that I should say what I mean by a Galton board, since some of you may not have heard of it. We feed a marble into a router at the top of the device (call the router A1) that randomly routes a marble either down and left (to a router we'll call B1) or down and right (to a router we'll call B2). B1 routes marbles randomly to either C1 or C2, while B2 routes marbles randomly to either C2 or C3. And so on. The nth router in some row routes marbles either to the left (to the nth router in the next row) or to the right (to the n+1st router in the next row). If this is still unclear, let me know, and I'll try to include an ASCII art sketch or find an image and explanation on the web. Note that another word for a Galton board is a quincunx. A more suggestive and apt name would be "That thingy that they have at science museums that's supposed to demonstrate Gaussian distributions (but sometimes doesn't because balls' momentum can lead to fatter tails)". Jim Propp

4 9

Re: [math-fun] Vector puzzle
by Dan Asimov 27 Jun '12

27 Jun '12

***SPOILER WARNING*** I wrote: << For some integer n > 0 you have all 2^n vectors of dimension n whose entries are +1 or -1. Of course the sum of all 2^n of these vectors is the 0 vector. Then your three-year-old child changes some of the entries of some of these vectors to 0. Show that there is still a nonempty subset of the new set of 2^n vectors that sums to the 0 vector. >> A solution to the puzzle, due to Alon Amit, is described 40 lines below. --Dan ------------------------------------------------------------------------------------------- Here "modified vector" refers to a vector in the set of vectors after it has been somewhat mangled by the three-year-old. (Any of these may of course be 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: v(k+1) := v(k) + u(k). 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, we must have v(k) = v(k+r) for some k >=0, r >= 1. Then v(k+r) - v(k) is a sum of modified vectors that sums to the 0 vector. ------------------------------------------------------------------------------------------- ________________________________________________________________________________________ It goes without saying that .

1 0

[math-fun] miscellaneous CF identity
by Bill Gosper 27 Jun '12

27 Jun '12

For some unclear region of (a,b,i,j,k) space, Out[239]= -a i - (1 + a - j) (1 + a - k) + ContinuedFractionK[-(1 + n) (1 - j + n) (1 - k + n) (2 + a + i - j - k + n), -a i + (2 - j + n) (2 - k + n) + (1 + n) (2 + a + i - j - k + n), {n, b, \[Infinity]}] == -b i - (1 + b - j) (1 + b - k) + ContinuedFractionK[-(1 + n) (1 - j + n) (1 - k + n) (2 + b + i - j - k + n), -b i + (2 - j + n) (2 - k + n) + (1 + n) (2 + b + i - j - k + n), {n, a, \[Infinity]}] E.g., In[247]:= List @@ (%239 /. ContinuedFractionK -> cfk) /. {a -> -6.9, b -> -10.5, i -> \[Pi], j -> E, k -> Sqrt[69.], \[Infinity] -> 69} /. cfk -> ContinuedFractionK Out[247]= {-264.992, -264.992} (69 terms was probably excessive. Temporarily switching to cfk is because ContinuedFractionK takes forever to do nothing. How can they keep shipping this nonsense?) Perplexingly, choosing j and k to terminate the continued fractions at 6 and 5 terms, In[245]:= Factor /@ Simplify[%239 /. {n, x_, \[Infinity]} -> {n, x, x + 8} /. j -> b + 6 /. k -> a + 5] Out[245]= ((-5 + a - b) (-4 + a - b) (-3 + a - b) (-2 + a - b) (-1 + a - b) (a - b) (1 + a - b) (2 + a - b) (3 + a - b) (4 + a - b) (-9 + i) (-8 + i) (-7 + i) (-6 + i) (-5 + i) (-4 + i) (-3 + i) (-2 + i) (-1 + i) i)/((72576 + 151200 a + 105840 a^2 + 30240 a^3 + 3024 a^4 - 39600 i - 82500 a i - 57750 a^2 i - ... 85 b^3 i^5 + 60 a b^3 i^5 - 10 a^2 b^3 i^5 - 15 b^4 i^5 + 5 a b^4 i^5 - b^5 i^5)) == 0 I.e., failure except for a finite set of i or a or b. --rwg

1 0

[math-fun] vector puzzle
by Warren Smith 26 Jun '12

26 Jun '12

I first solve a related but easier puzzle. My related puzzle is, you start with the 2^n vectors with entries +1 or -1. Child changes some subset of entries to 0s. Then I will sketch proof that the new set of 2^n vectors always contains either two disjoint subsets with equal sums, or two with sums that are negatives of each other. (Asimov had wanted only the latter.) It's easy once you see this trick. You just consider the number of possible ways to select two disjoint subsets, which is doubly-exponentially huge, namely 3^(2^n). Then you consider the possible vector sums they could have. This number of possibilities is way smaller, namely at most 2^((n+1)*n). This makes it obvious if n is large enough then necessarily two subsets must exist with equal or negated vector-sums (regardless of what that child had done). On the other hand, if n is too small for this proof to work, then you have a small problem you can solve by brute force (computer?). I'd pretty much already shown Asimov was right when n<=3 by hand (although I admit "pretty much" is not a real proof) which would suffice. QED. OK, now, what about Asimov's original harder form of the puzzle? Perhaps it can be solved with the same kind of trick, but you'll need to add some new ingredient also.

1 0

[math-fun] Vector puzzle
by Dan Asimov 26 Jun '12

26 Jun '12

I recently heard this cute puzzle: << For some integer n > 0 you have all 2^n vectors of dimension n whose entries are +1 or -1. Of course the sum of all 2^n of these vectors is the 0 vector. Then your three-year-old child changes some of the entries of some of these vectors to 0. Show that there is still a nonempty subset of the new set of 2^n vectors that sums to the 0 vector. >> --Dan

6 9