December 2012 - mathfun@mailman.xmission.com

[math-fun] poisoned wine bottles
by Warren Smith 03 Jan '13

03 Jan '13

> From: Michael Kleber <michael.kleber(a)gmail.com> > You have 1000 bottles of wine, which you need for a party that starts in an > hour. Two of the bottles are poisoned. > You have ten rats, and you can cause each rat to drink from any subset of > the bottles, which will cause it to die if the bottle is poisoned. But the > poison takes most of an hour to act, so you only get one round of giving > wine to rats, after which you must throw away any bottle which you do not > know is safe. > What do you do? I'd be happy to hear either worst-case or average-case > results. > Obviously if only one bottle were poisoned, you'd number the bottles and > assign one rat to each bit of the binary representation, and the dead rats > would spell out the binary of the unique poisoned bottle number. But two > poisoned bottles seems to make this much more subtle. --Interesting puzzle. Let W be the number of wine bottles, P the number poisoned, 1<=P<=W, and R the number of rats. The task is to identify the poisoned wine bottles with a single round of feeding each rat a wine-mixture from a selected bottle-subset. Say rat j gets fed subset Sj. Consider this WxR boolean matrix M: M_ij = 1 if wine bottle i is in set Sj. Otherwise M_ij=0. The essential property demanded (for a worst-case result allowing us to identify the P poisoned bottles) is that for any P-element subset of the rows of the matrix, its logical-OR (as an R-bit binary word) is DISTINCT from that arising from any other P-element subset. (This logical OR's locations for its 1-bits give the names of the dead rats.) So evidently for a solution to exist we need that binomial(W, P) <= 2^R. It was proposed that W=1000, P=2. Hence the left hand side is 499500=1000*999/2. Hence a solution cannot exist unless there are at least 19 rats, R>=19. Since Kleber had R=10, we conclude there is no solution guaranteed to identify the two poisoned bottles. We can however adopt the weaker goal of trying to identify some subset of bottles we can guarantee are safe. In that case, just partition the bottles into R equal-size subsets each with W/R bottles. Then P rats die whereupon we've identified (R-P)*W/R safe wine bottles. With R=10, P=2, W=1000, we identify 800 safe ones this way. Returning to the original problem of identifying the poisoned bottles, Kleber's binary method shows the inequality I gave is tight (up to integer roundoff) if P=1. But what if P>=2? I will now attempt to sketch an argument that my trivial inequality is not too far off being tight, for any FIXED P. To prove this, consider selecting the matrix M at random, each bit chosen by an i.i.d. coin toss, where the coin used is biased with a particular well-chosen constant bias. Specifically, I choose the bias in such a way that the expected number of 1-bits in the R-vector got by ORing P rows of the matrix, comes out to be R/2. I claim this argument will show that R = C * lg( binomial(W,P) ) rats suffice, for some positive constant C. To prove this (i.e. to supply the details of the proof, which I have not provided since I am lazy), you need to argue that with positive probability, all those P-row-ORs will indeed be distinct. This can be done by arguing the expected number of conflicting P-row-subset pairs is <1. Then since probability>0, that proves some set of such coin tosses must exist, which have this property, hence a suitable experimental-design exists. QED. Hence, with P=2, since 2 is fixed, there is a solution with R=O(logW) rats and somebody less lazy than I could even work out a good bound on the constant C (1<C<5 sounds safe).

12 35

[math-fun] Khinchin & Geometric Means
by Hans Havermann 30 Dec '12

30 Dec '12

Under 'Applications' here < http://reference.wolfram.com/mathematica/ref/Khinchin.html >, the Mathematica documentation states: Geometric mean of the first 1000 continued fraction terms in Pi… In[1]:= N[Apply[Times,ContinuedFraction[Pi,1000]]^(1/1000)] Out[1]:= 2.66563 In[2]:= N[Khinchin] Out[2]:= 2.68545 Sadly, the example ignores the fact that the first term of a continued fraction is very different from all the rest, a matter that would have been more apparent if one had asked for the geometric mean of the first 1000 continued fraction terms of Pi/4. I have just determined that the geometric mean of 1498931686 terms (cherry-picked) of the *fractional* part of the continued fraction of pi is within 1.002405*10^-13 of Khinchin's constant.

6 12

[math-fun] As long as we're talking astronomy
by Bill Gosper 29 Dec '12

29 Dec '12

http://media.zenfs.com/en_us/News/Reuters/2012-12-19T035245Z_616564795_TM3E… shows the ridiculously complicated illumination of Saturn's nightside by sunlight scattered off the rings, some of which is then viewed though the rings. At 4 o'clock on the limb, there is even an arc filtered through the dayside rings and then the upper atmosphere. But I don't understand: 1) Why the crisp silhouettes of the near rings against the (false color) green background seem discontinuous with the arcs outside the planet's shadow, presumably viewed by scattered, transmitted sunlight. 2) The bluish white haze extending far to the right from 5 o'clock on the limb. --rwg

3 2

Re: [math-fun] J Borwein's sig
by Henry Baker 28 Dec '12

28 Dec '12

Thank you, Edwin! I don't think I knew about Erez Lieberman Aiden's work directly, but had seen other people refer to it. The first 20 minutes of this 31-minute video shows really nice graphics of (human-like) DNA in chromosonal "fractal globules", which have the "locality" properties I described, and are _not_ knotted. This video also describes how this data was gathered & processed. http://www.youtube.com/watch?v=7hT0_tQVjzA Erez Lieberman Aiden: Things You Can't Browse at UCSC broadinstitutebroadinstituteÂ·114 videos Published on Oct 2, 2012 This talk was presented at VIZBI 2011, an international conference series on visualizing biological data (http://www.vizbi.org) funded by NIH & EMBO. At 10:46 AM 12/28/2012, W. Edwin Clark wrote: >Henry is perhaps thinking of the work of Harvard Fellow Erez Lieberman. >He claims that human nuclear DNA folds into something he calls a >fractal globule which has few if any knots. > http://www.aaas.org/news/releases/2011/1201sp_ge_prize.shtml >I hear him speak on this in April, but I don't recall the details --only that he >had some beautify simulations of DNA folding and unfolding. > >On Fri, Dec 28, 2012 at 1:07 PM, Henry Baker <hbaker1(a)pipeline.com> wrote: > >> From the article in the nih.gov link below: >> >> "The *** E. coli *** strains used in this study and their relevant >> genotype are detailed in Supplementary Table S1." >> >> http://en.wikipedia.org/wiki/Escherichia_coli >> >> "The first complete DNA sequence of an E. coli genome ... was published in >> 1997. It was found to be a *** circular *** DNA molecule 4.6 million base >> pairs in length, containing 4288 annotated protein-coding genes (organized >> into 2584 operons), seven ribosomal RNA (rRNA) operons, and 86 transfer RNA >> (tRNA) genes." >> >> E. coli has *** circular *** DNA. Human nuclear (non-mitochondrial) DNA isn't circular. >> >> At 09:41 AM 12/28/2012, Michael Kleber wrote: >> >On Fri, Dec 28, 2012 at 11:56 AM, Henry Baker <hbaker1(a)pipeline.com> wrote: >> > >> >I don't know what % of the time (human nuclear--i.e., non-mitochondrial) >> >> DNA spends doing recombination, but I would guess/hope very small. During >> >> the rest of the time, it is my understanding that there aren't any knots in >> >> this DNA. >> > >> >I'm sorry, I didn't realize we were still arguing about this question of >> >fact. Let me re-post the link from up-thread, along with the beginning of >> >the article this time. >> > >> >http://www.ncbi.nlm.nih.gov/pubmed/22187153 >> >"Topo IV is the topoisomerase that knots and unknots sister duplexes >> during DNA replication"

2 1

[math-fun] life on Mars? No problem?
by Warren Smith 28 Dec '12

28 Dec '12

Tests of Earth bacteria, to see if they could survive in Martian conditions, found most died, but 6 kinds of "carnobacteria" survived & grew, plus the Gram-negative bacterium "Serratia liquefaciens." However, their "Martian" conditions sounded to me pretty atypically nice, for Mars: 0C in 7mbar CO2 on agar.

1 0

[math-fun] astro-news (and a trivia question)
by Warren Smith 28 Dec '12

28 Dec '12

The answer I had in mind was this. The first extrasolar planets were detected NOT by optical means, but instead with a radio telescope and a clock. Need an atomic clock. They are planets orbiting a pulsar and are detected by variations in the ultraprecise pulse timings.

1 0

Re: [math-fun] J Borwein's sig
by Henry Baker 28 Dec '12

28 Dec '12

This AMS article talks exclusively about _circular_ DNA -- e.g., that found in some bacteria & in mitochondria. I believe that this is because bacteria/mitochondria have to use DNA itself to make stuff directly, rather than first translating into RNA. It may also have relevance to _RNA_, but this AMS paper doesn't talk about RNA. Once again, I'm not aware of any evidence that non-circular DNA is knotted. At 09:19 AM 12/25/2012, W. Edwin Clark wrote: >You will find pictures of knots and links of DNA in this 1995 Notices of >AMS article by DeWitt Summers >one of the first knot theorist to look at DNA > http://www.ams.org/notices/199505/sumners.pdf > >On Tue, Dec 25, 2012 at 11:10 AM, Henry Baker <hbaker1(a)pipeline.com> wrote: > >> DNA does get incredibly _folded_ & kinked, but not mathematically >> _knotted_, at least according to the lectures I've listened to. >> >> There are some wonderful videos of DNA being replicated by a graphics >> group in Australia, which show how the two different strands are separated, >> one of them is broken up into chunks (because it has to be copied the >> other direction) and then copied & put together. >> >> If you believe these videos, there aren't any knots involved. >> >> At 07:45 AM 12/25/2012, Michael Kleber wrote: >> >Not at all! DNA does indeed become knotted; most notably, this is >> >inevitable when a circular chromosome gets replicated to create two >> >daughter chromosomes, whose knotting is forced by the helical structure of >> >DNA. The cell's solution is a class of enzymes called topoisomerases, >> >which serve only to break the phosphate backbone of one strand, pass the >> >other through it, and then repair the broken one -- a topology-only >> >chemical reaction. >> > >> >--Michael >> >On Dec 25, 2012 7:08 AM, "Henry Baker" <hbaker1(a)pipeline.com> wrote: >> > >> >> The amazing thing about DNA is that even though it is incredibly long, it >> >> never seems to "knot". >> >> >> >> I guess that if it ever does get knotted, the whole cell commits suicide >> >> (or at least tries to -- perhaps a source of cancer?) >> >> >> >> Some relatively small bacterial and mitochondrial DNA are circular (except >> >> when being copied), which probably aids in keeping them from knotting. >> >> >> >> At 04:47 PM 12/24/2012, Fred lunnon wrote: >> >> >On 12/25/12, Bill Gosper <billgosper(a)gmail.com> wrote: >> >> >> Awful thought: What is the expected time at which a 3D random walk first >> >> >> becomes "knotted"? (W.r.t. pulling on the ends.) >> >> > >> >> >Bearing in mind that the ends may in general lie deep within the convex hull >> >> >of the walk, perhaps this question requires rather more careful >> >> >definition ... WFL

4 4

Re: [math-fun] J Borwein's sig
by Henry Baker 28 Dec '12

28 Dec '12

From the article in the nih.gov link below: "The *** E. coli *** strains used in this study and their relevant genotype are detailed in Supplementary Table S1." http://en.wikipedia.org/wiki/Escherichia_coli "The first complete DNA sequence of an E. coli genome ... was published in 1997. It was found to be a *** circular *** DNA molecule 4.6 million base pairs in length, containing 4288 annotated protein-coding genes (organized into 2584 operons), seven ribosomal RNA (rRNA) operons, and 86 transfer RNA (tRNA) genes." E. coli has *** circular *** DNA. Human nuclear (non-mitochondrial) DNA isn't circular. At 09:41 AM 12/28/2012, Michael Kleber wrote: >On Fri, Dec 28, 2012 at 11:56 AM, Henry Baker <hbaker1(a)pipeline.com> wrote: > >I don't know what % of the time (human nuclear--i.e., non-mitochondrial) >> DNA spends doing recombination, but I would guess/hope very small. During >> the rest of the time, it is my understanding that there aren't any knots in >> this DNA. > >I'm sorry, I didn't realize we were still arguing about this question of >fact. Let me re-post the link from up-thread, along with the beginning of >the article this time. > >http://www.ncbi.nlm.nih.gov/pubmed/22187153 >"Topo IV is the topoisomerase that knots and unknots sister duplexes during DNA replication"

2 1

[math-fun] glasses are liquids?
by David Makin 28 Dec '12

28 Dec '12

This seems to be quite relevant - and of interest ;) http://www.livescience.com/7511-bizarre-properties-glass-revealed.html

2 1

[math-fun] Mathematician's Century-Old Secrets Unlocked
by Ray Tayek 28 Dec '12

28 Dec '12

http://news.yahoo.com/mathematicians-century-old-secrets-unlocked-171554694… While on his death bed, the brilliant Indian mathematician Srinivasa Ramanujan cryptically wrote down functions he said came to him in dreams, with a hunch about how they behaved. Now 100 years later, researchers say they've proved he was right. "We've solved the problems from his last mysterious letters. For people who work in this area of math, the problem has been open for 90 years," Emory University mathematician Ken Ono said. Ramanujan, a self-taught mathematician born in a rural village in South India, spent so much time thinking about math that he flunked out of college in India twice, Ono said. But he sent mathematicians letters describing his work, and one of the most preeminent ones, English mathematician G. H. Hardy, recognized the Indian boy's genius and invited him to Cambridge University in England to study. While there, Ramanujan published more than 30 papers and was inducted into the Royal Society. "For a brief window of time, five years, he lit the world of math on fire," Ono told LiveScience. But the cold weather eventually weakened Ramanujan's health, and when he was dying, he went home to India. It was on his deathbed in 1920 that he described mysterious functions that mimicked theta functions, or modular forms, in a letter to Hardy. Like trigonometric functions such as sine and cosine, theta functions have a repeating pattern, but the pattern is much more complex and subtle than a simple sine curve. Theta functions are also "super-symmetric," meaning that if a specific type of mathematical function called a Moebius transformation is applied to the functions, they turn into themselves. Because they are so symmetric these theta functions are useful in many types of mathematics and physics, including string theory. Ramanujan believed that 17 new functions he discovered were "mock modular forms" that looked like theta functions when written out as an infinte sum (their coefficients get large in the same way), but weren't super-symmetric. Ramanujan, a <http://www.livescience.com/999-ancient-hindu-text-preserved-modern-technolo…>devout Hindu, thought these patterns were revealed to him by the goddess Namagiri. Ramanujan died before he could prove his hunch. But more than 90 years later, Ono and his team proved that these functions indeed mimicked modular forms, but don't share their defining characteristics, such as super-symmetry. The expansion of mock modular forms helps physicists compute the <http://www.lifeslittlemysteries.com/2693-entropy-explanation.html>entropy, or level of disorder, of <http://www.space.com/15421-black-holes-facts-formation-discovery-sdcmp.html>black holes. In developing mock modular forms, Ramanujan was decades ahead of his time, Ono said; mathematicians only figured out which branch of math these equations belonged to in 2002. "Ramanujan's legacy, it turns out, is much more important than anything anyone would have guessed when Ramanujan died," Ono said. The findings were presented last month at the Ramanujan 125 conference at the University of Florida, ahead of the 125th anniversary of the mathematician's birth on Dec. 22. --- co-chair http://ocjug.org/

1 0