July 2011 - mathfun@mailman.xmission.com

[math-fun] Guessing game
by Bill Thurston 17 Jul '11

17 Jul '11

One of my cousins asked me this question: Suppose 3 people make secret guesses of a number, uniformly randomly chosen from 1--100. Whoever is closest wins. What is their "best" strategy? I'd like to modify this to let the unknown number to be uniformly chosen real number in [0,1]. In the event of ties, let's say the winner is chosen uniformly from all best guesses (or the "prize" is distributed equally, I don't care). By "best", I want a Nash optimal probability distribution for the guesses of the the three participants --- that is, if each one knows the probabilities with which the others choose their guess, they can do no better than using the same distribution. Note that with two guessers, a guess of .5 wins over everything except another guess of .5, when it ties. For 3 guessers, it's not optimal for all three to pick .5, because .49 then wins against the other two. It's also not optimal to pick a number uniformly at random from the unit interval: if two of the players do that a guess of .5 has an expectation of 5/12. Bill Thurston

5 6

[math-fun] Evaluation of hypergeometric series in O(n(log n)^k) time and O(n) space
by quad 17 Jul '11

17 Jul '11

http://arxiv.org/abs/1106.2301 Thought some of your specialfunctionologists/computer algebra nuts might like this. --- "A simple algorithm for the evaluation of the hypergeometric series using quasi-linear time and linear space" Sergey V.Yakhontov (Submitted on 12 Jun 2011) A simple algorithm with quasi-linear time complexity and linear space complexity for the evaluation of the hypergeometric series with rational coefficients is constructed. It is shown that this algorithm is suitable in practical informatics for constructive analogues of often used constants of analysis. --- Sincerely, Robert

1 0

Re: [math-fun] should mathematics and evolution be taught in schools.
by Dan Asimov 16 Jul '11

16 Jul '11

David Wilson wrote: << But seriously, when deciding what should be taught in school, why should we even care about the opinions of beauty queens or actors? >> Seriously, I care because those comment represent more or less a cross-section of what typical Americans think, and the respect for science is dismal. In fact some of the beauty queens' answers reminded me of this great Tony Auth cartoon: < http://imgfave.com/view/213946 >. --Dan Sometimes the brain has a mind of its own.

1 0

[math-fun] should mathematics and evolution be taught in schools.
by Simon Plouffe 16 Jul '11

16 Jul '11

Hello, someone sent this to me : They asked, should mathematics be thaugt in school as well as the theory of evolution, here are the answers. The only one that makes sense is miss vermont, ouf, at least one is not completely stupid. I can't believe this. http://www.youtube.com/watch?v=IHH8Vi5SulI&feature=player_embedded http://www.youtube.com/watch?v=UkBmhM0R2A0 Best regards, Simon Plouffe

6 5

[math-fun] Hat Game
by Richard Hess 15 Jul '11

15 Jul '11

Dear funsters, The Hat Game problem below came to light over 10 years ago and the best strategy is not yet known for arbitrary N. It is known when N is one less than a power of 2. Can anyone tell me the best strategy for N=5 and for N=6? Happy puzzling, Dick THE HAT GAME N PLAYERS ENTER A ROOM AND A BLACK OR WHITE HAT IS PLACED ON EACH PERSON'S HEAD AS DETERMINED BY A FAIR COIN TOSS. EACH SEES THE HATS ON THE OTHERS BUT NOT HIS OWN. AT A SIGNAL EACH PLAYER MUST SIMULTANEOUSLY EITHER ANNOUNCE THE COLOR OF HIS HAT OR PASS. NO COMMUNICATION IS ALLOWED EXCEPT FOR AN INITIAL STRATEGY SESSION. THE GROUP SHARES A LARGE PRIZE IF AT LEAST ONE GUESSES CORRECTLY AND NO PLAYER GUESSES INCORRECTLY. CAN THEY DO ANY BETTER THAN A 50% CHANCE?

2 2

Re: [math-fun] more polynomial factor heights
by Bill Gosper 15 Jul '11

15 Jul '11

MKI> I hope my reposting of a solution to a different problem didn't fool > people > into thinking they shouldn't pay attention to this one! > > On Wed, Jul 6, 2011 at 5:29 AM, Bill Gosper <billgosper(a)gmail.com> wrote: > >rwg> >> Anyway, here's another: Find the height 1 polynomial of least degree d >> with >> an irreducible factor of height > d. And >=d? >> >> I'll start the bidding with d = 37, height 41. Whose value I'll >> sequester >> for now just to make things harder. >> --rwg >> MK> > I've got one that's degree 21, with an irreducible factor of height 23. > > I went looking for things of the form P = (irred) * (x-1)^2, since I > more-or-less understand how successive-differences-of-coefficients works. > The easiest thing to think about was P / (x-1): successive coefficients > of > that polynomial need to differ by 0, 1, or -1 (to make P height 1), the > sum > of the coefficients needs to be 0 (to make it divisible by x-1 again), it > needs to be short (to keep total degree down), and the sums of the initial > subsequences of coefficients needs to get large (to get the irred factor > to > get high degree). > > The best sequence of coefficients for P/(x-1) that I've come up with so > far > is: > 1,2,3,4,4,3,3,2,1,0,-1,-2,-3,-4,-3,-3,-2,-2,-1,-1,-1 > > Divide by x-1 (i.e. take successive sums of coefficients) and we get > coeffs > 1,3,6,10,14,17,20,22,23,23,22,20,17,13,10,7,5,3,2,1. Multiply by x-1 (ie > take successive differences) and the coefficients are all 0s, 1s, and -1s. > The length of my sequence is 21, so the degree of the polynomial is 21 > also > (since it has 22 coefficients, from x^0 through x^21). > > I don't expect this to be minimal, but it seems like a pretty good > construction. > > --Michael Whoa, can anybody beat that? Meanwhile, this is sort of interesting: In[1154]:= Factor[-1 + x + x^2 + x^3 - x^4 + x^5 + x^7 + x^8 - x^10 - x^11 - x^12 - x^13 - x^14 - x^15 - x^16 - x^18 - x^19 - x^22 + x^23 + x^24 + x^25 + x^26 + x^27 + x^28 + x^29 + x^30 + x^31 + x^32 + x^33 - x^34 - x^35 - x^36 - x^37 - x^38] Out[1154]= -(-1 + x)^3 (-1 - 2 x - 2 x^2 + 3 x^4 + 8 x^5 + 15 x^6 + 25 x^7 + 39 x^8 + 57 x^9 + 78 x^10 + 101 x^11 + 125 x^12 + 149 x^13 + 172 x^14 + 193 x^15 + 211 x^16 + 226 x^17 + 237 x^18 + 243 x^19 + 244 x^20 + 240 x^21 + 230 x^22 + 215 x^23 + 196 x^24 + 174 x^25 + 150 x^26 + 125 x^27 + 100 x^28 + 76 x^29 + 54 x^30 + 35 x^31 + 20 x^32 + 10 x^33 + 4 x^34 + x^35) --rwg

2 3

[math-fun] "Geometric Integration": Minsky-like numerical ODE methods
by Henry Baker 15 Jul '11

15 Jul '11

In previous posts, I indicated my interest in digital simulations of physics that _exactly_ preserved the usual conserved quantities: energy, angular momentum, etc. I hadn't realized that there is a very large field now called "Geometric Integration" that is dedicated to precisely this goal, and that a huge amount of progress has been made since the field took off in approx. 1990. As a result of this progress, it should be possible to import some of the insights from "Geometric Integration" back into the Minsky circle hack paradigm. A good introduction to "Geometric Integrators for ODEs" is by McLachlan and Quispel: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.125.3832&rep=rep1&… "Six Lectures on the Geometric Integration of ODEs" is also by McLachlan and Quispel: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.130.167&rep=rep1&t… --- The cool thing about so-called "symplectic" integrators (which preserve "volume" in phase space) is that many of them basically follow the "serialized" structure of the Minsky circle hack model (but without "floor()" or "round()") q_(k+1) = q_k + tau * p_k p_(k+1) = p_k - tau * delV(q_(k+1)) i.e., the second equation depends upon the first, rather than being "simultaneous". This enables the computation to be easily reversed: p_k = p_(k+1) + tau * delV(q_(k+1)) q_k = q_(k+1) - tau * p_k There is also a slightly more symmetrical so-called "leapfrog" version, also with a serialzed structure: q_(k+.5) = q_k + 1/2 * tau * p_k p_(k+1) = p_k - tau * delV(q_(k+.5)) q_(k+1) = q_(k+.5) + 1/2 * tau * p_(k+1) "The total energy is not conserved, but nor does the energy error grow with time, even for time steps of the same order of magnitude as the frequencies of the system. Invariant sets such as periodic, quasiperiodic, and chaotic orbits are well-preserved in phase space. Leapfrog preserves linear and angular momentum (where applicable) up to round-off error. On the other hand, it does become unstable if the time step is too large" There is also an "implicit" symplectic integrator, which should also work for a Minsky-like circle hack in integers: p_(k+1) = p_k + tau*delV((q_k+q_(k+1))/2) q_(k+1) = q_k - tau*(p_k+p_(k+1))/2 Here, we need to solve an implicit equation, possibly by using search or a Newton iteration, in order to find p_(k+1) and q_(k+1). While this "mid-point method" is typically more computationally expensive, the cool thing about it is that: "it too is symplectic, this time for any Hamiltonian system with any constant symplectic or Poisson structure. It preserves any linear symmetries of the system, and is time-reversible with respect to any linear reversing symmetry of phase space. It preserves not just linear and angular momentum but any quadratic first integrals of the system. It is linearly stable for all time steps." The time reversibility comes from the fact that it is no more difficult to solve the implicit equation going backwards than going forwards. The mid-point method does _not_ necessarily conserve energy, either. Indeed: "On the other hand, no method can preserve energy and symplecticity in general." [Ge & Marsden, Phys. Lett. A 133 (1998), 135Â139]. --- The orbits of the Minsky "circle" hack obviously don't conserve energy, else the orbits would be exact circles. On the other hand, the closed orbits do have their "energy" bounded both below and above, as well as a "winding number" and an "area". I'm currently doing computer searches to determine if a closed orbit can ever have _retrograde_ motion (= negative area step), how big the winding number can be, and what constraints there may be on the energy bounds of an orbit. For many purposes, the fact that the Minsky circle hack orbits are _disjoint_ is more important than the fact that energy be conserved. This behavior provides a discrete analogy to quantum theory where the different energy "levels" are discrete.

2 1

[math-fun] Blame the Minor Planets
by Hans Havermann 14 Jul '11

14 Jul '11

A team of astronomers found that close encounters among the minor planets Ceres and Vesta lead to strong chaotic behavior of their orbits, as well as of the Earth's eccentricity. This means, in particular, that the Earth's past orbit cannot be reconstructed beyond 60 million years. http://www.aanda.org/index.php?option=com_content&task=view&id=735&Itemid=2…

2 1

[math-fun] Blame the Galaxy
by Hans Havermann 14 Jul '11

14 Jul '11

When CP violation has been observed in the decay of B-Mesons the key difference observed between the break-up of matter and antimatter versions of the same particle is variation in the different decay rates. Curiously even though researchers observe that wide variation in the pattern of decay rates when those individual decay rates are added together they add up to the same total for both matter and antimatter versions of the same particle. Dr Hadley believes that the "frame dragging" affect of the whole Galaxy explains all of those observations. Matter and antimatter versions of the same particle will retain exactly the same structure except that they will be mirror images of each other. It is not unreasonable to expect the decay of those particles to also begin as an exact mirror image of each other. However that is not how it ends. The decay may begin as a exact mirror image but the galactic frame dragging affect is significant enough to cause the different structures in each particle to experience different levels of time dilation and therefore decay in different ways. However the overall variation of the different levels of time dilation averages out when every particle in the decay is taken into account and CP violation disappears and parity is conserved. http://www2.warwick.ac.uk/newsandevents/pressreleases/galaxy_sized_twist

1 0

[math-fun] K-T Meteorite did kill the dinosaurs, fossil shows
by Henry Baker 14 Jul '11

14 Jul '11

FYI -- http://www.telegraph.co.uk/science/dinosaurs/8633970/Meteorite-did-kill-the… Meteorite did kill the dinosaurs, fossil shows A horn from one of the last surviving dinosaurs could be clinching evidence that a massive meteor strike ended the extinct reptiles' reign on Earth. 8:51AM BST 13 Jul 2011 The 45cm-long fossilised browhorn belonged to a family of plant-eating dinosaurs that included the famous three-horned Triceratops. It was found at a geological site known as the Hell Creek Formation in the bleak badlands of south-east Montana, US, where many other dinosaur fossils have been unearthed. What made this one special was its location, just 13cm below the rock layer that marks the Cretaceous-Tertiary or "K-T" boundary Â the point in the fossil record where the dinosaurs died. This suggests dinosaurs were around right up to the time all traces of their existence vanished. In other words, they disappeared suddenly, as the result of an abrupt global disaster rather than a slow extinction. A huge asteroid or comet smashing into the Earth off the coast of Mexico at the end of the Cretaceous Period 65 million years ago is widely believed to have killed off the dinosaurs. But some sceptics point to an absence of dinosaur fossils for three million years leading up to the impact as evidence that the creatures may have already gone when the meteor struck. The "three million gap" has helped drive controversy over what happened to the dinosaurs, some of which evolved into birds. However, the horn fossil appears to close the gap, according to scientists writing in the Royal Society journal Biology Letters. The team, led by Dr Tyler Lyson, from Yale University in New Haven, US, wrote: "The in situ specimen demonstrates that a gap devoid of non-avian (bird) dinosaur fossils does not exist and is inconsistent with the hypothesis that non-avian dinosaurs were extinct prior to the K-T boundary impact event." The scientists pointed out that a 125cm section of rock strata laid down after the impact was completely devoid of fossils.

1 0