October 2007 - mathfun@mailman.xmission.com

[math-fun] Re: submarine problem -- data
by Steve Witham 19 Oct '07

19 Oct '07

>From: "Schroeppel, Richard" <rschroe(a)sandia.gov> > >The 2N-1 pattern works for N=9, but my program isn't good enough to >show minimality in reasonable time. Mine, too (still running). >For N=10, the program hasn't >found any solutions so far with 19-22 shots. (This doesn't mean >much, since the space is huge.) So far, for n=10 I have these solutions: n=10, 19 shots: 0 0 0 0 0 0 0 1 1 1 1 2 5 7 8 9 6 4 3 n=10, 18 shots: 0 0 0 0 0 0 1 1 1 1 2 5 7 8 9 6 4 3 n=10, 17 shots: 0 0 0 0 0 1 1 6 1 4 8 5 3 9 2 7 7 (trying for 16 shots now) Interesting similarity between the first two solutions. Almost makes me want to try a search starting from the reverse of any solution... >There are a few obvious morphs of a solution: Increment each shot >by a constant C; or increment each shot by the number of the shot; >or multiply all shots by anything prime to N. This allows me to >restrict the search to begin 0, 0, D, with either D=0 or D divides N. Thanks for the inspiration & clues. I wrote a C program (longer) http://www.tiac.net/~sw/math-fun/subsolve.c that updates its status as it makes and retracts moves. I use an additional constraint that can cut off searches earlier: If there are m unsunk subs at a given velocity, then at least m additional shots will be needed to sink them. This is a generalization of the observation that you have to shoot at least once at every position to catch all the stationary subs. >From: Scott Huddleston <scotth(a)ichips.intel.com> > >For p an odd prime, I give a solution for the size N = 2p submarine >problem in 2N-1 = 4p-1 steps using 2N-2 shots. Since 17 shots works for n=10, an unused shot may indicate that you can do with less time...or maybe not always. --Steve

1 0

Re: [math-fun] A jostled string forms knots quickly
by Henry Baker 18 Oct '07

18 Oct '07

Thanks for this posting! I had always wondered the same thing about the headphone wires on my cellphone. I have speculated that putting the wires in a coil might actually _increase_ the amount of knotting -- i.e., leaving the wire in a jostled mess may actually make it harder for the knots to form. The next question is whether there is a simple way to fold the wires so they won't knot. I suppose if you connect the ends together, it won't be able to form a normal sort of a knot, but then it could always form knots with doubled wires. I suppose that if any of these questions had a simple answer, sailors over the past 4,000 years might have found them. At 03:14 AM 10/18/2007, Ray Tayek wrote: >http://www.sciencenews.org/articles/20071013/mathtrek.asp > >--- >vice-chair http://ocjug.org/ Science News Online Week of Oct. 13, 2007; Vol. 172, No. 15 A Tangled Tale A jostled string forms knots quickly Julie J. Rehmeyer You put the headphones in your bag in a tidy coil, but when you pull them out, they're a snarled mess every time. It may seem like a personal curse, but a new study shows that it's just physics in action. Dorian M. Raymer and Douglas E. Smith of the University of California, San Diego worked out the physics of random knotting by putting lengths of string into a contraption resembling a miniature clothes dryer that spun the loose string around. A mere ten turns, they found, had a fifty-fifty chance of putting a knot in a piece of string. The longer it tumbled, the greater the chance of a knot forming. They also wanted to know what kinds of knots were forming, so they took pictures of the strings before and after tumbling. Identifying the knots was tricky, however, because knots that look very different may nevertheless be equivalent, meaning that one knot can be transformed into the other by twisting or pulling the string without tying or untying it. One knot could be upside down, for example, or have trivial excess loops, or be twisted up. Fortunately, an entire branch of mathematics is devoted to identifying equivalent knots. When mathematicians talk about knots, they do one slightly unusual thing: they take the two ends of the string and fuse them together to form a loop. This makes it impossible to untie the knot without cutting the string. It also means that two knots are equivalent if one can be made to look just like the other by moving the string around without cutting it. Back in 1983, a mathematician named Vaughan Jones at the University of California, Berkeley devised a mathematical expressionÂnow known as the Jones polynomialÂthat can be defined for any knot. The remarkable thing is that if two knots are equivalent, they'll each yield the same Jones polynomial. It's not a perfect way to classify all knots, because some complicated knots that aren't equivalent correspond to the same polynomialÂso knot theorists still have plenty to keep them busy. But relatively simple knots are equivalent if their Jones polynomials are the same. This was just the tool Raymer and Smith needed. When they removed the strings from the tumbler, they pulled the two ends of each string straight up out of the tumbler and tied them together to get a mathematical knot. Then they photographed the knots and fed them into a computer program they had written to analyze each knot and compute its Jones polynomial. Running their experiment a couple of thousand times, the researchers produced a remarkable number of different knots. They found all of the 14 possible knots in which the string crosses itself seven times or fewer. They also found a smattering of more complicated knots, including a few with 11 crossings. Their results appeared online Oct. 2 in advance of publication in an upcoming Proceedings of the National Academy of Sciences. The pair was also surprised to find that almost all of their knots were "prime," meaning that they weren't composed of two or more simpler knots. They speculated that using longer strings and more tumbles would have generated some composite knots. Raymer notes that knots have become important in understanding the ways that strings of DNA form knots, but he also says that the biological forces on DNA are very different from the random forces on his tumbled strings. The importance of this study, he says, "is mostly that we constructed a scientific study into something that could be called Murphy's Law." The cord always gets tangled up.

1 0

[math-fun] A jostled string forms knots quickly
by Ray Tayek 18 Oct '07

18 Oct '07

http://www.sciencenews.org/articles/20071013/mathtrek.asp --- vice-chair http://ocjug.org/

1 0

[math-fun] submarine problem -- data
by Schroeppel, Richard 14 Oct '07

14 Oct '07

I wrote a program to look for minimal submarine shooting strategies. For N=3, 4, 5, 7, and 8, the minimal number of shots is 2N-1, and the pattern 0, 0, 0, ..., 0, 1, 2, ..., N-1 (with N 0s) is the lexicographically earliest solution. For N=6, there's a 10-shot minimal solution, 0 0 0 1 0 2 3 4 3 5. The 2N-1 pattern works for N=9, but my program isn't good enough to show minimality in reasonable time. For N=10, the program hasn't found any solutions so far with 19-22 shots. (This doesn't mean much, since the space is huge.) There are a few obvious morphs of a solution: Increment each shot by a constant C; or increment each shot by the number of the shot; or multiply all shots by anything prime to N. This allows me to restrict the search to begin 0, 0, D, with either D=0 or D divides N. There's also a reflect-time morph, but I can't see how to use it to make the program faster. I'm including the program; it's small. The only trick is to retest the previous escaping sub trajectory on the current shooting strategy. Rich ------------------ /* submarine3.c */ /* submarine puzzle */ /* see Math-Fun, Oct 2007 */ /* I can assume any solution begins 0,0,D with D=0 or D a divisor of N */ #define N 10 #define Nshots 22 int shots[100]; int recheck, rchi, rchj; nextshot() { int i; for (i=Nshots-1;i>=0;i--) { a: shots[i]++; if ((i==2) && (N % shots[2])) goto a; if (shots[i]<N) return; #if 1 if (i<=4) printf("%d,%d,%d,%d\n",shots[0],shots[1],shots[2],shots[3]); #endif shots[i]=0; recheck=0; }; } int check() { int i,j,k; for (i=0;i<N;i++) { for (j=0;j<N;j++) { for (k=0;k<Nshots;k++) { if (((i+j*k)%N) == shots[k]) break; }; if (k==Nshots) /* start i, velocity j has no hit */ { rchi=i; rchj=j; recheck=1; return 0; }; }; }; return 1; } main() { int i,v; printf("submarine3 N=%d Nshots=%d\n",N,Nshots); for (i=0;i<100;i++) shots[i]=0; recheck=0; for (;;) { if (recheck) /* see if last failure is fixed */ { if (((rchi+rchj*(Nshots-1))%N)!=shots[Nshots-1]) goto nxsh; }; v = check(); if (v) { printf("win N = %d, Nshots = %d\n", N, Nshots); for (i=0;i<Nshots;i++) printf(" %d",shots[i]); printf("\n"); exit(); }; nxsh: nextshot(); if (shots[1]) { printf("lose N = %d, Nshots = %d\n", N, Nshots); exit(); }; }; }

1 0

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

13 Oct '07

>From: "Michael Kleber" <michael.kleber(a)gmail.com> > >Therefore, for n=10^6, you can: > >a) Take n shots at square 1. This hits all subs with s=1. >b) Then take n/2 shots at square 2. This hits half of the > subs with s=2; the other half were already hit by the > more-than-n/2 shots taken at square 1. >c) Then take n/4 shots at square 3, followed by n/4 shots > at square 4. If n were a multiple of 3, you'd need n/3 shots > at square 3, but a million ain't. >[...] >Now the big question: Is this optimal? If I'm following, with that plan for n = 4 you would shoot at 1, 1, 1, 1, 2, 2, 3, 4 -- 8 shots-- but you only need 7, e.g.: 1, 1, 2, 2, 3, 3, 4. --Steve

1 0

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

13 Oct '07

Bill AT. writers: << [I wrote] << QUESTION: Suppose we consider only isometric embeddings h_1 that arise from a continuous family of isometric embeddings h_t: S^2 -> R^3, 0 <= t <= 1, where h_0 is the inclusion mapping. Does there still exist an isometry h_1 of S^2 into an arbitrarily small ball in R^3? If not, how small can the image of such an isometry be? (It's not immediately obvious that the image can even have a smaller diameter than the original sphere, but it can.) >> The Nash-Kuiper embedding theorem can be done in a parametrized way, i.e. any C^1 continuous family of short C^1 embeddings parametrized say by a cell complex, i.e. P -> {C^1 short embeddings S^2 -> R^3}, can be deformed through short maps to a family of isometric embeddings, by the same proof. I.e. there would be a homotopy P x [0,1] -> {C^1 short embeddings S^2 -> R} that ends up in {C^1 isometric embeddings S^2 -> R}. So the answer is yes. >> Very interesting! << On the other hand, concrete finite-complexity constructions seem harder. You can iteratively dimple a surface, by moving a plane through it and reflecting the part that sticks through the plane; this stays embedded for a while. Are you thinking about doing this from multiple directions, and seeing how far you can go? . . . >> Yes, exactly. Iterated reflections of this kind through a moving plane are the only concrete isometries of S^2 into R^3 that I thought of. --Dan

2 1

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

13 Oct '07

(Sorry about the garbled first line.) Bill wrote: << . . . The Nash-Kuiper embedding theorem can be done in a parametrized way, i.e. any C^1 continuous family of short C^1 embeddings parametrized say by a cell complex, i.e. P -> {C^1 short embeddings S^2 -> R^3}, can be deformed through short maps to a family of isometric embeddings, by the same proof. I.e. there would be a homotopy P x [0,1] -> {C^1 short embeddings S^2 -> R} that ends up in {C^1 isometric embeddings S^2 -> R}. . . . >> I had been originally just thinking C^0. But what is a C^1 isometric embedding of S^2 -> R^3 that approximates the inclusion map, yet whose image is strictly in the interior of it ? --Dan

5 5

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

12 Oct '07

On 10/11/07, Steve Witham <sw(a)tiac.net> wrote: > ... > For n = 2, 3 and 4, all of which have one prime factor, 2n-1 is the minimum. > > So... one stage per prime factor, plus a cleanup stage? > > So, for n=1000000, 2999998 shots? > > But for n = 510510 = 2 * 3 * 5 * 7 * 11 * 17 it would be > 510510 + 510509 + 510508 ... + 510104 = 3573549? > ... Er, this still doesn't look quite right to me. For composite number n of cells, the problem may be partitioned according to the HCF m of n and the target velocity b. Suppose the factors m_i (including m_1 = 1 and m_k = n) are arranged in increasing order [and define m_0 = 0]. For the subproblem corresponding to a factor m of n, the player must target each of m (consecutive) cells with n/m (possibly nonconsecutive) shots. We might as well choose consecutive blocks of cells, each starting from cell 0. Now it gets rather murky. At stage i > 0, the first m_{i-1} cells have already been targetted; is it possible to schedule the remaining shots so that they do not overlap orbits previously excluded? [This must be possible if we are allowed to miss turns without penalty.] If so, the number of shots is in total \sum_i (m_i - m_{i-1}) n/m_i , summed over (all) the divisors m_i of n. For example for n = pq a product of two primes p < q, this comes to 4n - 2q - p^2. Finally, all the above assumes that we know n and its factorisation; but suppose on the other hand that we don't even know n --- what is a good strategy now? Enough --- no more! [T'is not as sweet as t'were before.] Fred Lunnon

2 1

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

12 Oct '07

> >Steve Witham wrote: > > > > So... one stage per prime factor, plus a cleanup stage? > > [+ other off-base speculation & errors] >From: "Fred lunnon" <fred.lunnon(a)gmail.com> > >Er, this still doesn't look quite right to me. Apologies --- I'll pipe down now. --Steve

1 0

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

11 Oct '07

>From: "Michael Kleber" <michael.kleber(a)gmail.com> > >Steve Witham wrote: > >> For n = one million, I guess you have to shoot about 13815504 > > shots -- 1e6 * ln( 1e6 ). > > >But surely the structure of the problem should give us some >leverage and let us do better than that, right? > >Right? (SPOILOIDS) >From: "Fred lunnon" <fred.lunnon(a)gmail.com> >Consider the special case n prime: [...] Total cost (at most) 2n-1 slugs. For n = 2, 3 and 4, all of which have one prime factor, 2n-1 is the minimum. So... one stage per prime factor, plus a cleanup stage? So, for n=1000000, 2999998 shots? But for n = 510510 = 2 * 3 * 5 * 7 * 11 * 17 it would be 510510 + 510509 + 510508 ... + 510104 = 3573549? If that's true the worst cases are something like n * the, er, inverse-prime-torial function, which is < O(log n). --Steve

1 0