October 2007 - mathfun@mailman.xmission.com

Re: [math-fun] Re: Submarine problem
by Fred lunnon 11 Oct '07

11 Oct '07

On 10/11/07, Steve Witham <sw(a)tiac.net> wrote: > >From: "Michael Kleber" <michael.kleber(a)gmail.com> > >--------- > >You are shooting at a submarine that is moving through > >Z/nZ at constant velocity -- that is, its position at time t > >is a+bt (mod n), for some 0 <= a,b < n -- but you don't > >know a or b. At each time t=0,1,2,..., you can shoot at > >one position. How quickly can you hit all possible > >submarines? > > For n = one million, I guess you have to shoot about 13815504 > shots -- 1e6 * ln( 1e6 ). > > That is how many times you have to shoot at random > before the chance that you've still missed is <= 1/1e6. Glad I don't have to pay Steve's ammo bills! Spoiler below ... Now I really will stop thinking about this irritating problem! WFL || || V Consider the special case n prime: during stage (i), the player aims at cell 0 and fires n times. Provided b is nonzero mod n, he gets lucky at time t = - a b^{-1} mod n [where the multiplicative inverse of b is found in a standard fashion using Euclid's algorithm]. Otherwise, the target is stationary: so during stage (ii) he fires once at every other cell in turn. Total cost (at most) 2n-1 slugs.

1 0

Re: [math-fun] Re: Submarine problem
by Michael Kleber 11 Oct '07

11 Oct '07

Steve Witham wrote: > For n = one million, I guess you have to shoot about 13815504 > shots -- 1e6 * ln( 1e6 ). > > That is how many times you have to shoot at random > before the chance that you've still missed is <= 1/1e6. When you say "at random", you're really assuming that you can hit 1/n of the remaining subs with each shot -- that is, you're calculating how long it should take if each sub randomly teleported to a square after each shot. But surely the structure of the problem should give us some leverage and let us do better than that, right? Right? --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.

1 0

[math-fun] Re: Submarine problem
by Steve Witham 11 Oct '07

11 Oct '07

>From: "Michael Kleber" <michael.kleber(a)gmail.com> >--------- >You are shooting at a submarine that is moving through >Z/nZ at constant velocity -- that is, its position at time t >is a+bt (mod n), for some 0 <= a,b < n -- but you don't >know a or b. At each time t=0,1,2,..., you can shoot at >one position. How quickly can you hit all possible >submarines? For n = one million, I guess you have to shoot about 13815504 shots -- 1e6 * ln( 1e6 ). That is how many times you have to shoot at random before the chance that you've still missed is <= 1/1e6. Here is my back-of-the-envelope calculator: #include <math.h> #include <stdio.h> main () { double remain; long n; long shots; for( n = 10; n <= 1000000; n *= 10 ) { remain = 1.0; shots = 0; while( remain > 1.0/n ) { shots++; remain -= remain / n; } printf( "%7d %8d %f\n", n, shots, shots * 1.0 / n / log(n) ); } } (In the C standard library, log(n) is the natural log.) --Steve

1 0

Re: [math-fun] Re: Teabag Problem
by David Gale 11 Oct '07

11 Oct '07

> > >Here are some references for the corresponding problem using two unit disks >identified along their boundaries: > > The Mylar Balloon Revisited > IvaiÌlo M. Mladenov; John Oprea > The American Mathematical Monthly, Vol. 110, No. 9. (Nov., 2003), pp. > 761-784. > > What Is the Shape of a Mylar Balloon? > William H. Paulsen > The American Mathematical Monthly, Vol. 101, No. 10. (Dec., 1994), pp. > 953-958. > >Both papers use some hairy integrals and differential geometry. > >But, the first paper states that the goal is to determine the *convex >hull* of the >wrinkly shape that the Mylar balloon would actually assume. It's not >clear to me >what assumptions the second paper is making. > >I doubt either paper rigorously determines the maximum volume the metric >space >formed by a circular teabag can assume when embedded isometrically in 3-space. > >--Dan It seems to me these papers do not require the embedding to be strictly an isometry.so I would still like to see an example, probably with "wrinkles", of the disc problem which has a positive volume. dg >_______________________________________________ >math-fun mailing list >math-fun(a)mailman.xmission.com >http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun David Gale Professor Emeritus Department of Mathematics University of California, Berkeley

2 1

[math-fun] Submarine problem
by Michael Kleber 11 Oct '07

11 Oct '07

Hi funsters, A colleague posed the following question: --------- You are shooting at a submarine that is moving through Z/nZ at constant velocity -- that is, its position at time t is a+bt (mod n), for some 0 <= a,b < n -- but you don't know a or b. At each time t=0,1,2,..., you can shoot at one position. How quickly can you hit all possible submarines? --------- Well, he actually asked about n = one million, but you get the idea. I hadn't seen this before; anyone recognize it? I have a plausibly efficient answer, but no proof that it's optimal. I'll wait a few days before sending my heuristic, to give y'all a chance to think about it without contamination. --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.

2 3

Re: Teabag Problem (Was: Re: [math-fun] 3-D spider webs?)
by David Gale 11 Oct '07

11 Oct '07

> >It's even somewhat surprising that a positive volume is possible. > >--Dan It surprised me until I found an origami example on the internet. There's whole lot of stuff on this problem, e.g. http://www.ics.uci.edu/~eppstein/junkyard/teabag.html but I couldn't find anything on the natural question, what if instead of a square you have a disc? Can there be a positive volume? dg >_________________________________________________________________________ > ><< >Jim asks: > ><< Do any spiders build genuinely three-dimensional webs? > >Just Friday I turned over an 8-inch rock from our garden0, >and clinging to the bottom were two thin earthworms and >a paperish thing that resembled the remains of some kind >of cocoon. When that thing started flexing, I thought we >were about to witness the emergence of some insect's next >stage. But instead -- after about five minutes of flexing -- >out walked a spider -- a black one quite fat (probably expecting) -- >looking quite formidable. > >> > >_______________________________________________ >math-fun mailing list >math-fun(a)mailman.xmission.com >http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun David Gale Professor Emeritus Department of Mathematics University of California, Berkeley

2 1

[math-fun] Re: Teabag Problem
by Dan Asimov 10 Oct '07

10 Oct '07

David Gale writes re the Teabag Problem: << It surprised me until I found an origami example on the internet. There's whole lot of stuff on this problem, e.g. http://www.ics.uci.edu/~eppstein/junkyard/teabag.html but I couldn't find anything on the natural question, what if instead of a square you have a disc? Can there be a positive volume? >> Here are some references for the corresponding problem using two unit disks identified along their boundaries: The Mylar Balloon Revisited Ivaïlo M. Mladenov; John Oprea The American Mathematical Monthly, Vol. 110, No. 9. (Nov., 2003), pp. 761-784. What Is the Shape of a Mylar Balloon? William H. Paulsen The American Mathematical Monthly, Vol. 101, No. 10. (Dec., 1994), pp. 953-958. Both papers use some hairy integrals and differential geometry. But, the first paper states that the goal is to determine the *convex hull* of the wrinkly shape that the Mylar balloon would actually assume. It's not clear to me what assumptions the second paper is making. I doubt either paper rigorously determines the maximum volume the metric space formed by a circular teabag can assume when embedded isometrically in 3-space. --Dan

1 0

[math-fun] Brushing your teeth with Pascal's triangle
by Jason 08 Oct '07

08 Oct '07

I was surprised to see this puzzle on the back of my milk carton today at breakfast: http://lunkwill.org/tmp/pascal.jpg The fine print says to check smartcarton.com for problem #M027 to see the answer. Entering "027" turns up a different pyramid-shaped problem, though. In any case, I'm going to have trouble getting much done today if I have to brush my teeth 33 times.

1 0

Re: [math-fun] Mathematical cosmos article by Max Tegmark
by Henry Baker 08 Oct '07

08 Oct '07

A logician's view of a "theory" is that it is simply the shortest (in bits) description that fits (more or less) the data. We can use any computational engine we want to simulate the universe from the description, but since they are all equivalent to Turing Machines (modulo the number of bits required to describe the interpreter), it doesn't much matter which one we use. Fredkin is fond of "Life"-like cellular automata, but those models may require substantial modifications depending upon the "geometry" that fits the universe the best. The job of physics/chemistry/biology/etc. is the "compress" the experimental data into as few bits as possible. We are allowed an arbitrarily high degree of cleverness in coming up with such descriptions, but clearly new data may require arbitrarily large adjustments to the existing descriptions. It is interesting that physics loves "continuity" so much that they embed this concept into their view of physical models. Thus, when Einstein showed that Newton was wrong, physics explained this by saying that the previous models & data were correct, but just not for the precision required at large distances, high velocities, large masses, etc. I am particularly interested in why the simplistic models of the ancients _ever_ worked. There seems to be no a priori reason why _circular_ orbits should work as well as they do; if most of the planetary orbits had been highly elliptical, it might have required another several millenia for the mathematicians to come up with a proper description. Furthermore, if the planetary orbits had been closer together, the resulting chaos would have made even elliptical orbits an impossible model. (Using some of the web sites that allow experimentation with Newtonian gravity, it appears to me that _most_ gravitational systems with a relatively small number of objects "blow up" (i.e., kick one or more of their objects off to infinity) after not very much time. So perhaps a planetary system with widely spaced (minimally interacting) planets in nearly circular orbits is characteristic of long-lived configurations.) So we fall back on the fact that the fact that we are here, may imply that highly chaotic planetary orbits are inimical to human existence. We now have the circular argument that the universe is understandable (partially decomposable/factorable) simply because that is the only universe that supports human life. Alternatively, of all of the chaos in our lives, only the pitifully small percentage that is amenable to simple patterns is actually visible/"understandable" to us. So, yes, Max is correct, but only vacuously so.

3 2

Teabag Problem (Was: Re: [math-fun] 3-D spider webs?)
by Dan Asimov 08 Oct '07

08 Oct '07

Perhaps I should mention that the papery thing resembled two rectangles overlaid and joined along their perimeters. Which reminds me of the --------------------------------------------------------------------------------- TEABAG PROBLEM (which I learned of on the Web a few years ago): Let metric space T be 2 unit squares identified along their perimeter. Among all isometric embeddings of T in 3-space, what is the supremum of the attainable volumes? (And, is there an embedding that attains this sup? If so, which one(s)?) --------------------------------------------------------------------------------- It's even somewhat surprising that a positive volume is possible. --Dan _________________________________________________________________________ << Jim asks: << Do any spiders build genuinely three-dimensional webs? Just Friday I turned over an 8-inch rock from our garden0, and clinging to the bottom were two thin earthworms and a paperish thing that resembled the remains of some kind of cocoon. When that thing started flexing, I thought we were about to witness the emergence of some insect's next stage. But instead -- after about five minutes of flexing -- out walked a spider -- a black one quite fat (probably expecting) -- looking quite formidable. >>

2 1