- mathfun@mailman.xmission.com - mailman.xmission.com

[math-fun] Square (& other) chains and necklaces.
by Richard Guy 05 Dec '02

05 Dec '02

I recently mentioned a problem of finding chains and necklaces in which adjacent links add to a square (or other things). Such problems can be restated as: Draw a graph having the numbers from 1 to n as vertices and an edge between any pair of vertices whose labels add to a square (or whatever). Is there a Hamilton path (circuit) in the graph? For example (requested by at least one listener), n = 32. 28 8 1 15 10 21 26 4 23 32 2 17 14 19 22 30 27 6 9 3 16 13 20 12 29 24 7 25 11 5 31 18 This can be upped to 33 by inserting ... 9 16 33 31 18 7 29 20 5 11 ... so we now have chains for n = 15 16 17 31 32 33 34 35 ... (and no smaller others??). This (and 32 33 ... for necklaces) seem to be in too much of an inchoate state for acceptance as sequences for OEIS ?? Finding Hamilton paths is NP-hard in general, but those of us who don't know about such things can often find them in particular cases. Any offers for contributions to knowledge, or references to existing knowledge that Ed Pegg hasn't told me about? R.

8 16

[math-fun] Laces high
by Helger Lipmaa 05 Dec '02

05 Dec '02

Today's Nature has an interesting article - a survey is available from http://www.nature.com/nsu/021202/021202-4.html Paper itself: -- Mathematics: What is the best way to lace your shoes? BURKARD POLSTER School of Mathematical Sciences, PO Box 28M, Monash University, Victoria 3800, Australia e-mail: burkard.polster(a)sci.monash.edu.au The two most popular ways to lace shoes have historically been to use 'criss-cross' or 'straight' lacing but are these the most efficient? Here we demonstrate mathematically that the shortest lacing is neither of these, but instead is a rarely used and unexpected type of lacing known as 'bowtie' lacing. However, the traditional favourite lacings are still the strongest. -- Helger

2 1

[math-fun] Laces high
by John McCarthy 05 Dec '02

05 Dec '02

It seems to me that the main objective of a shoe lacing scheme should be to produce a uniform force pulling the two sides of the uppers together. This doesn't come up in the article.

1 0

[math-fun] ANKOS after 180 days
by mcintosh＠servidor.unam.mx 05 Dec '02

05 Dec '02

>From Edwin Clark, 20 Nov 2002: > Speaking of reviews of ANKOS. Here's a review by Lawrence Gray that is > somewhat more substantial than Kranz's review: > > www.math.umn.edu/~gray/pdf/wolfram.pdf > ... Well worth reading; he was apparently present at the 1998 Santa Fe meeting. Having hinted at the legal wrangle, let us hope that he is correct in saying that Cook's paper may finally be released. The proceedings have kept being put off and off (latest estimate January 2003); dare one hope to see it there? Melanie Mitchell has an extremely perceptive review of ANKOS in Science, which had not yet arrived in Puebla at the time of my last posting (but by now E.C. has included it in his list). > And by the way, does anyone know if Mathew Cook's proof of the > universality of CA 110 (as presented in ANKOS) has been verified by > workers in the area? Some progress has been reported in this area; see my previous postings or the postings in the ``cellular automata'' usenet group. The necessary collisions are spectacular and were easy to verify, given that we had already done considerable work in this area. Global synchronization is harder to check because it takes place over such a wide area and long time span. Apparently there is nothing better to do than to sit in front of a screen and watch it, although segments can always be captured and printed. What at first seemed to be an error or a mislabelling turns out to be due to the sketchy nature of the information presented in the book. More aspects of the collisions have to be taken into account than are shown in the figures. Inviting people to run the Mathematica programs associated with the book does not lead to independent confirmation of the assertions in the text. Using a proprietary language which can only be run in a proprietary operating system does not necessarily imply falsification of the results (but look at what that boy Schoen just did at Bell Labs). We have just had some discussion here on math-fun of the acceptability of the Four Color Theorem, wherein be it noted that running an independently written program on a different model of computer was considered to be reassuring. What is for sure is that the pictures in the book were carefully selected and hopefully no mistakes were made in transcribing their code into the manuscript. Handsome indeed are the results. But lacking even an attempt to explain the programs, how would one go about trying experiments of one's own? Such as bombarding the data with a string of nulls, or trying to merely copy or complement an incoming data stream? Or writing that binary counter? Supposing that all the adjustments which are inherent in the collision parameters can successfully be made (and bear in mind that the scheme outlined in ANKOS practically forces the use of a cyclic system), the larger question arises as to whether there is a Turing Machine lurking in the background somewhere. We are offered Kolakoski's automatic substitution systems, and we can search the literature of small Turing Machines. There isn't much to work with here in Puebla except the Internet, but we haven't been able to find any paper giving an explicit connection. Maybe soomeone can offer some references? - hvm

1 0

[math-fun] totient blooper, segment arc, pestilent vectors
by R. William Gosper 04 Dec '02

04 Dec '02

I said k - 1 ==== \ k + 1 k - j > B ( ) n U (n) / j + 1 j + 1 j ==== ==== k + 1 \ k j = 1 phi(n ) > t = ----------------------------------- + -----------, / k + 1 k + 1 ==== t < n (t,n)=1 >where B are Bernoulli numbers, > j > a b c a-1 b-1 c-1 > phi(p q r ...) := p (1 - p) q (1 - q) r (1 - r) ..., >and > a b c k k k > U (p q r ...) := (1 - p ) (1 - q ) (1 - r ) ..., > k >where p, q, r, ... are distinct primes. In fact, a b c a-1 b-1 c-1 phi(p q r ...) := p (p - 1) q (q - 1) r (r - 1) ..., as in the earlier message (and which you all know). --------- I added "volume" and "surface" of segment of n-sphere to Macsyma's GeoFuncs package, e.g., (c355) block([radexpand:false],sphere_segment_curved_surface(n,r,t)) n - 1 ----- n - 1 3 n n 1 t 2 hyper_2f1(-----, - - -, - + -, ---) (2 %pi r t) 2 2 2 2 2 2 r (d355) ---------------------------------------------------- n - 1 (-----)! 2 (t is thickness. radexpand:false just prevents the exponent in the numerator from distributing.) You can also give two abscissae instead of the thickness, getting powerseries in x1 and x2 instead of t=r-x1 and r-x2. (Perhaps I should have left it an integral, but half the time, the series terminate in just n/2 terms.) Try the n=2 case: On a circle of radius r, the chord of a segment of thickness t subtends what angle? Expecting something like 2 cos((r-t)/r), or even 2 atan(sqrt(r^2-(r-t)^2)/(r-t)), I was surprised by (c356) (assume(r>0), hypersimp(subst(2,n,%))/r) sqrt(t) (d356) 4 asin(---------------) sqrt(2) sqrt(r) (c357) rootscontract(%) t (d357) 4 asin(sqrt(---)) 2 r This says that the chord from an endpoint of the original chord to the midpoint of the arc is twice the mean proportional of the thickness and half the radius. Can this be seen directly, as opposed to via two Pythagorisms? -------- Apropos RKG's pun typo, mathematicians can indeed be vectors. I infected a 7th grader with the following diseased factoid, probably caught from a confused highschool teacher, and never examined critically: :-( :-( :-( :-( :-( :-( :-( :-( :-( :-( :-( "The gravitational effect of an extended body on a point outside its convex hull is the same as if all its mass were concentrated at its center of gravity." )-: )-: )-: )-: )-: )-: )-: )-: )-: )-: )-: )-: )-: )-: The absurdity of this is evident from comparing the force at the origin due to aligned unit masses at distances 1 and 3, vs a two-unit mass at 2. Otherwise, masscons would not perturb lunar orbits, and the oblateness of the Sun would not contribute to the precession of Mercury. --rwg

2 1

Re: [math-fun] n-complements, squared
by Henry Baker 04 Dec '02

04 Dec '02

Knuth talks about this in the later editions. I seem to recall that this is Volume II. It's in one of the exercises. At 08:02 AM 12/4/02 -0800, Eugene Salamin wrote: >--- Don Reble <djr(a)nk.ca> wrote: >> I think the two-square-sum problem has been done to >> death. If you can factor X, it's easy to determine >whether it has such representations; does anyone know >>how to generate them? > >Maple has a function "sum2sqr" which lists all the >representations. You could examine the code. > >Gene

1 0

Re: [math-fun] Square (& other) chains and necklaces.
by Dan Hoey 03 Dec '02

03 Dec '02

Dan Asimov wrote: > Nice example! Now suppose every vertex is required to have finite > valence. Then I think this slight modification of Mike's example > will still serve as a graph where every {1,...,n} has a Hamiltonian > path, but not {1,2,3,...}. (This is a slight modification of Dan's graph.) 4--3--5--7--9---11--- | /| /| /| / | / ... |/ |/ |/ | / | / 1--2--6--8--10---12-- Now suppose we require Hamiltonian cycles for every {1,...,n}. Is there then a Hamiltonian path for N (there can't be a cycle). Suppose we require Hamiltonian cycles for every {a, ..., b} for a,b in Z? Can we then find a Hamiltonian path through Z? Dan (not that Dan, this Dan) Hoey(a)AIC.NRL.Navy.Mil

2 1

Re: [math-fun] infinite paths & cycles
by Dan Hoey 03 Dec '02

03 Dec '02

When I said, "The only kind of graph connectedness I know of is finite," I meant that a path with two endpoints has to have finite length. So the distance between any two points is finite if it exists. Dan

1 0

Re: [math-fun] Square (& other) chains and necklaces.
by asimovd＠aol.com 03 Dec '02

03 Dec '02

Edwin Clark asked: << Let G be a graph whose vertices are N, the natural numbers. Suppose for every n the subgraph G_n of G induced on {1,2,...,n} has a Hamiltonian path starting with 1. Does G necessarily have a Hamiltonian path? >> MIke Reid wrote: << no. a simple counterexample is the graph 4 --- 3 --- 6 --- 7 --- 8 --- 9 -- ... | \_ | _/ | \ | / ... 1 --- 2 --- 5 where 5 is connected to n for all n > 5 (as well as to 2 and 3 ). Since 1 and 4 each have degree 1 , they would both have to be endpoints of any infinite hamiltonian path, a contradiction. >> Nice example! Now suppose every vertex is required to have finite valence. Then I think this slight modification of Mike's example will still serve as a graph where every {1,...,n} has a Hamiltonian path, but not {1,2,3,...}. 4 --- 3 --- 6 --- 7 --- 9 --- 11 ... |\_ | _/ | _/ | _/ | | \ | / | / | / | 1 --- 2 --- 5 --- 8 --- 10 ---12 ... --Dan

2 1

[math-fun] A "cycle" in N and proving a quaternion-like group is infinite
by Thane Plambeck 03 Dec '02

03 Dec '02

While we're on the subject of the meaning of infinite paths in N, would anyone like to comment on the validity/invalidity of the following argument? I was looking at the group G defined by the quaternion-like relations ijk = l jkl = i kli = j lij = k If you define two "permutations of N" t = (1)(2 3)(4 5) (6 7).... u = (1 2)(3 4)(5 6)... their product is a sort of infinite-order "cycle" in N tu = (1 3 5 7 9 11 13 15 17 ...... 16 14 12 10 8 6 4 2). Now consider the mapping f f(i) = t f(j) = t f(k)= u f(l) = u The mapping f seems to be a homomorphism from G into the group of permutations of N that respects the 4 group relations I started out with (when you check the relations, the involutions t and u cancel each other out). So in particular the element f(ik) = tu has infinite order, so G is infinite. I'm sure this is nothing new, but I was happy to find it (even more happy if it is valid). Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.qxmail.com/home.htm

1 0