May 2015 - mathfun@mailman.xmission.com

[math-fun] Grid problem
by David Wilson 28 May '15

28 May '15

Let G1 = Z^2 be the grid of integer points in the plane R^2. Let G2 be the grid of points in R^2 gotten by rotating G1 by 45° about the origin. What is the smallest c for which there exists bijection f: G1óG2 with |P-f(P)| ≤ c for all P?

4 4

[math-fun] Four solid angles
by James Propp 28 May '15

28 May '15

How many of you already know (or can figure out) what four solid angles associated with a general tetrahedron add up to 4 pi? I've been told that George Polya, when asked, replied with the correct answer instantly (it was part of his geometric toolkit), but that few of his contemporaries, when polled in an informal survey, were aware of this three-dimensional analogue of the familiar fact about the angles of a triangle summing to pi. I'm guessing that things haven't changed much in the intervening half-century. Jim Propp

6 7

[math-fun] Propp's birthday problem
by Warren D Smith 28 May '15

28 May '15

OK, I see what I did wrong on my "brute force solution" of the Q-generalization of Propp's problem. My error was, the (k-1)^(N-Q) term, counting ways to filling in N-Q slots with any of k-1 letters, allowed the resulting configurations to include some Q or more letters that all were the same. That should have been forbidden. Duh. So, this (i) makes it clear the brute force answers I derived were all valid as upper bounds. (ii) We can now repair. Let A(k,N,Q) be the number of N-letter words over k-letter alphabet such that there is no letter occurring Q or more times. We have the recurrence A(k,N,Q) = SUM(for m=0..Q-1) A(k-1,N-m,Q)*Binomial(N,m)*k and the base case A(1,N,Q) = 1 if 0<=N<Q, else 0. We can also let B(k,N,Q) be the number of N-letter words over k-letter alphabet such that there is no letter occurring Q or more times, except that the last letter occurs exactly Q times. We have B(k,N,Q) = A(k-1,N-Q,Q)*Binomial(N-1,Q-1)*k. These recurrences should let you compute any Propp-like expectation: Expected value of F(N) is SUM(for N=Q,...,k*(Q-1)+1)of k^(-N) * B(k,N,Q) * F(N). I have made no attempt to check these results, so beware of my usual erroneousness. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] Propp's birthday problem
by Warren D Smith 27 May '15

27 May '15

Propp: If N denotes the number of times you toss a k=2-sided coin until one side has come up Q=3 times, then the expected value of N-choose-3 is (2/8)(1)+(6/16)(4)+(12/32)(10)=11/2, not k^(Q-1)=4, so Warren's formula is incorrect, and the reasoning that he applied to the case Q=2 is inadequate. --WDS: I agree something must be wrong... But what? Apparently my reasoning was valid (anyhow, yielded the right answer!) when Q=2, but not for Q>2. Perhaps my reasoning still works when Q>2 to yield a lower bound?

1 2

[math-fun] Propp's birthday problem
by Warren D Smith 27 May '15

27 May '15

James Propp: Let the integer-valued random variable N be the number of times you roll a k-sided die until you see a number you've seen before (analogous to successively asking people's birthdays until you encounter the first repeat). E.g., if k=2, then p(N=2)=p(N=3)=1/2. There's no nice formula for the expected value of N, but as I learned from Jim Pitman last week, the formula for the expected value of N-choose-2 couldn't be simpler: it's just k itself! (Check: With k=2, the average of 2-choose-2 and 3-choose-2 is (1+3)/2 = 2.) Can anyone provide a "bijective" proof? --WDS SOLUTION: Nice formula. N-choose-2 is the number of dice-pairs, and among those pairs, there is EXACTLY ONE equal-pair, because when you rolled N-1 dice no two were equal, but then the Nth dice is equal, necessarily to exactly one, of the preceding. The chance a given pair is equal is 1/k. Among (N choose 2) pairs we have exactly one such special pair, so the "rate" of special pairs clearly being 1/k, we see that the expected value of (N choose 2) must equal k. EXTENDED RESULT: More generally, if you kept rolling dice until a Q-element subset of the dice all happened to be equal (for the first time when N dice have been rolled) then expected value of (N choose Q) would equal k^(Q-1). RELATED PUZZLE FOR YOU: In a random permutation of k items. Start from a random item. Walk to its successor (according to the perm) then to its successor, and so on, until you re-reach the item you started with, in all visiting N of the items (forming a cycle in the perm with cardinality N). The expected value of (N choose Q) is, I believe, binomial(k+1,Q) * [k-Q+1]/[k*(Q+1)] for any fixed integer Q>0. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

3 2

[math-fun] Good puzzle column
by Andy Latto 27 May '15

27 May '15

The Tech, MIT's sutdent newspaper, has added a puzzle column that has some good math-fun style puzzles. Googling "technical problems" at the tech's web site seems to be the easiest way to find them: https://www.google.com/webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF-8#… Andy Latto Andy.Latto(a)pobox.com

1 0

[math-fun] CS Faculty Position Open
by Michael Collins 27 May '15

27 May '15

My employer, Christopher Newport University in Newport News, VA, has an immediate need to hire a full-time non-tenure track instructor to teach mostly Java programming. Masters degree in CS or broadly related field required. Sorry if this is spam, but I figure a lot of people on this list are likely to know people who might be qualified for such a position. Please contact me at michael.collins(a)cnu.edu if interested. Thanks!

1 0

[math-fun] Birthday problem
by James Propp 27 May '15

27 May '15

Let the integer-valued random variable N be the number of times you roll a k-sided die until you see a number you've seen before (analogous to successively asking people's birthdays until you encounter the first repeat). E.g., if k=2, then p(N=2)=p(N=3)=1/2. There's no nice formula for the expected value of N, but as I learned from Jim Pitman last week, the formula for the expected value of N-choose-2 couldn't be simpler: it's just k itself! (Check: With k=2, the average of 2-choose-2 and 3-choose-2 is (1+3)/2 = 2.) Can anyone provide a "bijective" proof? Jim Propp

1 0

[math-fun] Gosper's EllipticK formula
by Bill Gosper 26 May '15

26 May '15

Bill Gosper: Then I bashed on it so hard that it got unnervingly ungrotesque: (*) EllipticK[1/4 (2 + (-2 + t)/Sqrt[1 - t])] == (1 - t)^(1/4) EllipticK[t] How could anything this simple be new? WDS: Let s=Sqrt[1-t]. Then (*) is rewritten as EllipticK[ 1/2 - (1+s^2)/(4s) ] == EllipticK[ -(1-s)^2/(4s) ] == s^(1/2) EllipticK[1-s^2] Now let s=1-m. Then this is EllipticK[ -m^2/(4(1-m)) ] == (1-m)^(1/2) EllipticK[(2-m)m]. E.Salamin: Complains WDS formula is wrong. --WDS: arg. Well, I just started with Gosper's "ungrotesque" formula taking its correctness on faith, then worked by hand to produce mine. Doing same thing over again now: Gosper: EllipticK[1/4 (2 + (-2 + t)/Sqrt[1 - t])] == (1 - t)^(1/4) EllipticK[t] Let t=1-s^2: EllipticK[1/4 (2 - (1+s^2)/s)] == (s)^(1/2) EllipticK[1-s^2] EllipticK[(2s-1-s^2)/(4s)] == (s)^(1/2) EllipticK[1-s^2] EllipticK[-(1-s)^2/(4s)] == (s)^(1/2) EllipticK[1-s^2] which is same as I got before. Now let s=1-m: EllipticK[-m^2/(4(1-m))] == (1-m)^(1/2) EllipticK[1-(1-m)^2] EllipticK[-m^2/(4(1-m))] == (1-m)^(1/2) EllipticK[2m-m^2] EllipticK[-m^2/(4(1-m))] == (1-m)^(1/2) EllipticK[(2-m)m] which is same as I got before, OK? So either I made same error over again because my brain is truly decaying, or Gosper was wrong, or Salamin was wrong, you figure out which. I was just trying to produce a nicer equivalent version. --------------------- Looks like a branch bug. Empirically, yours only works for m west of 1: gosper.org/braunch.pdf Would it remain nicer if repaired? --rwg

3 4

[math-fun] The amount of computation required to evolve or simulate human-level intelligence naively
by Warren D Smith 26 May '15

26 May '15

The atoms on or slightly below Earth surface can be regarded as performing experiments. If we re-express (4.4 gigayears) * (surface area of earth) * (1 meter deep) = 7 * 10^31 * meter^3 * sec in Hartree atomic time and length units, then we get 2 * 10^79 as the total number of such experiments performed so far. Now, of course, if you were going to redo that inside a computer, you could save time. The total amount of biomass on Earth is estimated to be (7+-1)*10^14 kg of carbon (and biomass is about 12 atomic percent carbon). http://www.pnas.org/content/109/40/16213 If we only simulated the biomass, with the nonliving matter being dealt with via some cheap model, that'd be only 1.5 * 10^73 experiments. OK, what if we decided, to hell with all that atom-level simulation, we are just going to propose a cheesy model of an entire cell (e.g. neuron) and simulate the interaction of those, 1 interaction per millisecond, with everything else in the world handled via some cheap model, and only some fixed set of possible interaction behaviors/rules, which can evolve. The same paper estimates total cell count on Earth is 5 * 10^31 which brings us down to 6 * 10^51 experiments. Of course, this all is well beyond what today's computers could reproduce. But suppose all you wanted to do was to simulate a single human brain (whose "wiring diagram" and neuron behaviors assumed 100% pre-known and the latter assumed pretty simple). Total energy use by brain is about 20 watts. If each synapse "firing" consumes about 24000 ATP molecules worth of energy per bit transmitted [Julia J. Harris, Renaud Jolivet, and David Attwell: Synaptic Energy Use and Supply, http://discovery.ucl.ac.uk/1368741/1/1368741.pdf] and ATP provides 40 kJoule/mole, then we would find the brain is transmitting at most about 10^16 bits/second inside. (Cells tend to fire all their synapses simultaneously, which would greatly lower simulation costs per bit.) Probably only 10-50% of that since brain cells also consume energy when they do nothing. Meanwhile a 64-bit processor chip would be transmitting 2*10^11 bits/sec on its bus if all 64 bits of the bus were continuously transmitting at 3 GHz. If you instead counted all the wires inside the chip, whenever they change logic state, what would the logic-event count per second be? I am guessing 10^12 / sec? Here the fact the human brain has 1.5*10^14 synapses [http://www.dana.org/News/Details.aspx?id=43512] and 9*10^10 neurons, is largely irrelevant to the time-cost, but does affect the memory usage, of the simulation. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0