November 2012 - mathfun@mailman.xmission.com

[math-fun] poisoned wine bottles -- perfect union codes continued
by Warren Smith 17 Nov '12

17 Nov '12

M(n) is the maximum size "perfect union code" on n symbols. Describe binary codewords of length N in terms of subsets of N symbols. A "perfect union code" is a set of codewords such that if A, B, C are any distinct codewords in the code, then it never happens that A is contained in the union of B and C. --you can obtain perfect union codes using BIBDs -- balanced incomplete block designs. http://en.wikipedia.org/wiki/Block_design#Definition_of_a_BIBD_.28or_2-desi… Any (v,k,lambda) design will do if lambda*2<k and will show M(v)>#blocks=b. For example, any Steiner triple system S(2,3,n) shows M(n) >= n*(n-1)/6 when n mod 6=1 or 3. Hence M(9) >= 12. M(13) >= 26. The Steiner system S(4,7,23) shows M(23) >= 253.

1 0

Re: [math-fun] 0.9999... = 1 and all that
by Dan Asimov 17 Nov '12

17 Nov '12

P.S. It may be that the sum-of-coordinates function can't be extended to Hilbert space from the absolutely convergent series, in such a way that it's continuous. Recall that I recently asked about the set of points in Hilbert space whose coordinates sum to 0, and it turns out to be a dense subset of Hilbert space. --Dan Daniel Asimov Visiting Scholar Department of Mathematics University of California Berkeley, California

1 0

Re: [math-fun] 0.9999... = 1 and all that
by Dan Asimov 17 Nov '12

17 Nov '12

If you stick with formal sums -- i.e., sequences of reals such as R^oo (direct product) -- without trying to assign a real number to each, you should be fine. Then if R^oo is indexed by Z (rather than say Z+), we have the double-ended sequences. And index-shifting can define an equivalence relation on R^oo whose quotient might be some interesting algebraic structure, replete with addition & scalar multiplication . . . I think. But if you do try to assign all elements of R^oo or even Hilbert space an extension of the sum-of-coordinates functions (from absolutely convergent double-ended series, where it is clearly well-defined), I think you always run into trouble if you want the definition to be non-random. But I'm not certain how to formulate or prove this precisely. --Dan David W. wrote: << With regard to the double-ended sums, I was hoping to treat them as a formalism, and avoid issues of convergence (which end do you converge toward?). Thus we would assign a reasonable value to some class of basic expressions (e.g, ... + 0 + 0 + 0 + 9 + 0 + 0 + 0 + ... = 9), and apply some formal arithmetic rules (value preserved by shifting, term-by-term sum, term-by-term scalar multiplication) and see where that leads us (I expect to a contradiction). >> Daniel Asimov Visiting Scholar Department of Mathematics University of California Berkeley, California

1 0

[math-fun] poisoned wine bottle puzzle
by Michael Kleber 17 Nov '12

17 Nov '12

Hello funsters, Somehow I've never seen this puzzle before! Is this old hat to any of you? 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. --Michael -- Forewarned is worth an octopus in the bush.

3 2

[math-fun] Coordination sequence for 3.3.4.3.4 lattice
by Allan Wechsler 17 Nov '12

17 Nov '12

There's a pretty Archimedian tiling with vertex figure 3.3.4.3.4 whose vertex coordination sequence has at least one of the following two properties: 1. It is not in OEIS. 2. I have miscalculated it. (This seems likely, since my "calculation" consisted of scrawling a portion of the tiling and then drawing blobs on vertices while I counted them by hand.) I have the first five elements as 1, 5, 11, 16, 22; OEIS doesn't find anything with those elements. I'll submit this if somebody else can verify my entries.

4 6

Re: [math-fun] when and why was it agreed that 0.999...=1?
by Phil Carmody 16 Nov '12

16 Nov '12

From: "Huddleston, Scott" > David Wilson asks: > > Anyway, I was wondering, does 0.99999... = 1 in the surreal numbers? > > That depends on how you map infinite decimals into > surreals. For sets of numbers A and B with a<b > whenever a in A and b in B, surreal "A | B" is the > "simplest" number between A and B. The surreals that > have finite sets of reals for A and B are dyadic rationals > (including integers). ... > A better (IMO) mapping of infinite decimals to surreals is > .3333... = {.3, .33, .333, .3333, ...} | {.3+.1, .33+.01, .333+.001, ...} Let a be 0.33, in A, and let b be 0.3+0.1, in B. a<b does not hold. So "|" is not defined. Phil

3 3

[math-fun] New(?) elliptic K transformation
by Bill Gosper 16 Nov '12

16 Nov '12

Purely empirically, for 0<r<1/2, EllipticK[4 E^(I ArcTan[1/2 Sqrt[-4 + 1/(1 - r) + 1/r]]) Sqrt[(1- r) r]] == E^(I ArcTan[Sqrt[r/(1 - r)]]) EllipticK[r] E.g., for r=1/4 EllipticK[Sqrt[3] E^(I*π/6)] == E^(I*π/6) EllipticK[1/4] For r=1/2, it gets the conjugate of the right answer, which is EllipticK[2] == -(-1)^(3/4) EllipticK[1/2] which can be found by listing all eight sign variations of the three square roots. Then we can try complex r: EllipticK[1/2 + I/2] == (-3 + 2 Sqrt[2])^(1/4) EllipticK[4 - 2 Sqrt[2]] which puts the lhs in polar form. And for r = I, EllipticK[(8 + 8 I) - 4 Sqrt[-1 + 7 I]] == (2^(1/4) E^(-(I*π/8)) - I E^(I*π/4)) EllipticK[I] None of the eight sign guesses works for Re(r)>1/2. If no one finds a proof of this stuff, imagine some future Mathematica just trying everything and choosing the numerically plausible one. --rwg

1 1

[math-fun] poisoned wine bottles
by Warren Smith 16 Nov '12

16 Nov '12

>From: Michael Kleber <michael.kleber(a)gmail.com> >I didn't quite follow this, Warren. What are you saying is almost tight? > Just to be clear, the puzzle I'm passing along is: Come up with a way of > assigning a subset of wine bottles to each rat, such that by observing > which rats die you can produce a set of wine bottles known to be safe, > where the set of safe bottles is as large as possible (either > expected-value or worst-case size). --Actually, it was not at all clear from your problem statement what you wanted. I was interested in the problem of identifying the exact set of poisoned bottles, using as few rats as possible, in 1 round. I argued with P poisoned bottles, P fixed, out of W total bottles, R rats with R=O(logW), would suffice, and this is best possible up to the constant hidden in the O. ---- But if P is not fixed, but instead is allowed to grow with W, for example P=W^(1/3), then I do not know a good answer. I can produce a good answer if we allow only a strong probability (not certainty) of success. Divide the W bottles into P*logW almost equal random disjoint subsets. With good probability, each such set contains at most a constant number of poisoned bottles. Now use my previous scheme that works well when P is bounded by a constant, within each subset. This has sketched a proof of existence of a scheme in which R=O(P*logW) rats are used, and which will, with probability>2/3, succeed in identifying the exact set of P poisoned bottles, and this works for any 0<=P<=W with P known ahead of time. However, with some probability<1/3, it will fail. The failure probability can be made to be <(1/3)^k by doing this k times in parallel (then k times as many rats needed), which I presume/guess means that O(P*(logW)^2) rats suffice to get certainty. (That is unproven, but you might be able to prove it using more careful and expanded version of this argument.) If that conjecture is true then we are tight up to an annoying log factor. ----- Mike Speciner pointed out that dividing the W bottles into R+P-1 almost-equal subsets allows us to use R rats in 1 round to identify at least (R-1)*floor( W/(R+P-1) ) safe bottles if we know at most P are poisoned.

1 0

[math-fun] poisoned bottles
by Warren Smith 15 Nov '12

15 Nov '12

--I also make the trivial remark that, no matter how many poisoned bottles P there are among the W total bottles (and let us say we do not know the value of P ahead of time), you can always identify them by using R=W rats, 1 rat per bottle. Can we do better? No. Because there are 2^W possible bottle-subsets and 2^R possible dead-rat subsets, so you can't have enough info to identify the poisoned bottles unless you have at least R>=W rats.

1 0

Re: [math-fun] when and why was it agreed that 0.999...=1?
by Adam P. Goucher 14 Nov '12

14 Nov '12

It depends on what set of numbers you're considering. In the reals, we can prove very immediately that 0.999... = 1: Least upper-bound axiom => Axiom of Archimedes => Non-existence of infinitesimal reals => 0.999999... = 1 The only thing you can question here is the least upper-bound axiom, which is true because it just is. If you reject the least upper-bound axiom, there are sets of numbers (such as the surreals) for which 1-(1/omega) exists and has a decimal representation of 0.999999.... However, unlike the reals, a decimal representation does not determine a unique surreal. Sincerely, Adam P. Goucher http://cp4space.wordpress.com > ----- Original Message ----- > From: Thane Plambeck > Sent: 11/14/12 05:39 AM > To: math-fun > Subject: Re: [math-fun] when and why was it agreed that 0.999...=1? > > Vi Hart dealt with all these flawed proofs that 1= 0.99999....in a video > > http://www.youtube.com/watch?v=wsOXvQn3JuE > > > On Tue, Nov 13, 2012 at 9:32 PM, Dan Asimov <dasimov(a)earthlink.net> wrote: > > > I'm pretty sure the shift in thinking -- at least among mathematicians -- > > occurred when Cauchy came up with the modern epsilon-delta definition > > of limit. Which Wikipedia says occurred in 1821. > > > > I've seen way too many non-mathematically trained people insisting > > (e.g., on sci.math) that 0.9999... definitely does not, can not, > > equal 1. So I guess the shift among non-mathematicians is still > > in progress. > > > > --Dan > > > > > > On 2012-11-13, at 8:33 PM, Gary Antonick wrote: > > > > > Hi all, > > > > > > I'm wondering if anyone knows when and why it was agreed that 0.999...=1. > > > > > > That is, the expression meant its limit of 1 and not something that got > > > closer and closer to 1. > > > > > > I've asked several people and have gotten some big pieces but not quite > > the > > > whole story: > > > Keith Devlin (last week): before Cantor mathematicians considered > > > "0.999..." to mean a *growing sequence* of 9's after the decimal. After > > > Cantor it was decided that the expression meant the *limit* of this > > > sequence: an infinite number of 9's after the decimal all at once. > > > Steven Strogatz (this afternoon) suggested talking to John Stillwell > > > John Stillwell (a couple hours ago) seemed to indicate the shift in > > > perspective happened gradually, with Zeno arguing for the growing > > sequence > > > (which would never get to 1) and everyone after the Axiom of Choice > > > agreeing that the expression was referring to its limit. > > > > > > -400 Zeno: 1/2 + 1/4 + 1/8 etc will never get to 1 > > > -350 Aristotle: 1/2 + 1/4 + 1/8 etc eventually gets to 1 > > > -300 Euclid: 1/4 + 1/4^2 + 1/4^3 + etc eventually gets to 1/3 > > > 1585 Stevin: 0.999... = 1 > > > 1671 Newton: 0.999... = 1 > > > 1858 Dedekind cuts > > > 1880? Cantor > > > 1904 Zermelo: Axiom of Choice > > > > > > Does anyone have more precise timing for this shift from thinking? > > > > > > All the best, > > > > > > Gary > > > _______________________________________________ > > > math-fun mailing list > > > math-fun(a)mailman.xmission.com > > > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > > > > _______________________________________________ > > math-fun mailing list > > math-fun(a)mailman.xmission.com > > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > > > > -- > Thane Plambeck > tplambeck(a)gmail.com > http://counterwave.com/ > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0