January 2013 - mathfun@mailman.xmission.com

Re: [math-fun] poisoned wine bottles
by Phil Carmody 04 Jan '13

04 Jan '13

Veit Elser <ve10(a)cornell.edu> wrote: > After three hours wax-&-wane found the following 50/4 code: > > {225, 593, 92, 198, 394, 46, 553, 291, 816, 674, 538, 320, 780, 114, \ > 53, 147, 75, 660, 897, 281, 141, 104, 278, 69, 208, 712, 420, 612, \ > 578, 64, 160, 24, 6, 513, 400, 261, 48, 136, 516, 3, 640, 36, 296, 9, \ > 770, 18, 528, 130, 33, 12} > > I used d=6 for a slightly deeper, less greedy search. ... > I am now intrigued to see what other symmetries might turn up -- recall > that wax-&-wane makes no symmetry restrictions whatsoever. I can't construct an argument in my head why more or less symmetry should be favoured. There are vastly more random sets than patterned ones, but the property being searched for requires cooperation between the members. Which of those things will have the greater influence? > So now we can evenly divide up the 1000 bottles into 50 sets > of 20 from which at most 80 must be rejected. Fantastic work! You've certainly deserved your extra bottle! One thing that I've not seen mention of is the cost in bottles of the test on the rats. Are we assuming that the tests are such a small sample that they don't reduce the amount available for humans? Or do we need to sacrifice one bottle per set? If the latter, then there are diminishing returns, and we may have bottomed out already. Phil

3 2

Re: [math-fun] solar system formation caught in action by telescope
by Phil Carmody 04 Jan '13

04 Jan '13

Fred lunnon <fred.lunnon(a)gmail.com> wrote: > Remarkable picture. Why must intelligent people top-post? Because they can, of course --- sigh! Anyway, back to: > > http://www.usatoday.com/story/tech/sciencefair/2013/01/02/planet-formation-… It's a lot less remarkable than most paintings I see in the local art galleries near here. You didn't believe USAToday when they credited it "(Photo: M. Kornmesser, ALMA (ESO/NAOJ/NRAO))", did you? It's just an artist's impression, that's all. The actual *photo* is here: http://www.eso.org/public/archives/images/screen/eso1301b.jpg The news is ESO's - Warren really should have linked to the actual source: http://www.eso.org/public/news/eso1301/ , where at least they make it abundantly clear it's just an artist's impression. To be honest, I wish places like ESO wouldn't rely on such fabrications for PR at all. It causes the spread of more mis-information than it propagates actual factual information. Phil

1 0

[math-fun] solar system formation caught in action by telescope
by Warren Smith 03 Jan '13

03 Jan '13

http://www.usatoday.com/story/tech/sciencefair/2013/01/02/planet-formation-… interesting phenomena, which I do not think were predicted.

3 2

[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] Emphatic Countdown
by Hans Havermann 01 Jan '13

01 Jan '13

10/9!*8!*7!-6!*5!/4!+3!*2!+1!

1 0