April 2010 - mathfun@mailman.xmission.com

Re: [math-fun] Fwd: Sticky Towers of Hanoi
by Dan Asimov 17 Apr '10

17 Apr '10

Alex Fink wrote (forwarded): << Sticky Towers of Hanoi is played with the disks of an n-disk ToH set (the pegs can be disregarded). In the initial position all of the disks are separate. In a general position there will be stacks of fused disks, with top radius and bottom radius differing. A move is to pick up a stack S and set it on another stack whose top radius exceeds the bottom radius of S; this causes the two disks that come in contact to fuse. >> I'm at least as perplexed as Fred here. Where it says "In a general position there will be stacks of fused disks" does that mean each stack is entirely fused, or just that it consists of a stack of fused stacks? I don't see how the description of play can lead to anything but each stack being entirely fused, yet as Fred points out, that makes "solving" the puzzle all too obvious. (There is nothing about what constitutes a solution, so maybe that's where the confusion lies?) Perhaps Alex can clarify this? --Dan ________________________________________________________________________________________ "Outside of a dog, a book is man's best friend. Inside of a dog, it's too dark to read." --Groucho Marx

6 7

[math-fun] NP-complete matching problem?
by Allan Wechsler 15 Apr '10

15 Apr '10

The following problem actually came up in the course of my work. I was pretty sure I'd heard of it before, and that it was NP-complete, but now I can't reconstruct my references, and I'm starting to doubt myself. The problem instance is a square N-by-N matrix of 1's and 0's. A solution consists of a set of N cells, all 1's, with including exactly one from each row and column, or the assertion that no such set exists. Alternatively, the instance is an (N,N)-bipartite graph, and a solution consists of a degree-1 subgraph (a matching) that includes all the vertices, or the assertion that no such matching exists. What is the classic name for this problem? What is its complexity?

2 2

Re: [math-fun] Animation of regular 17-gon construction
by Henry Baker 15 Apr '10

15 Apr '10

Very cool! Thanks for posting! Does anyone know what software was used in the construction of this animated gif? At 10:01 PM 4/14/2010, Thane Plambeck wrote: >this appeared on the wikipedia a few weeks ago, it looks like > >http://en.wikipedia.org/wiki/File:Regular_Heptadecagon_Inscribed_in_a_Circl… > >-- >Thane Plambeck >tplambeck(a)gmail.com >http://thaneplambeck.typepad.com/

2 1

[math-fun] Animation of regular 17-gon construction
by Thane Plambeck 15 Apr '10

15 Apr '10

this appeared on the wikipedia a few weeks ago, it looks like http://en.wikipedia.org/wiki/File:Regular_Heptadecagon_Inscribed_in_a_Circl… -- Thane Plambeck tplambeck(a)gmail.com http://thaneplambeck.typepad.com/

4 3

Re: [math-fun] Dumb astronomy question
by Steve Witham 14 Apr '10

14 Apr '10

>From: Henry Baker <hbaker1(a)pipeline.com> > >Wouldn't tidal forces eventually get rid of the tilt? > >From: Joshua Zucker <joshua.zucker(a)gmail.com> > >Tidal forces don't get rid of the tilt, they cause precession. > >From: Henry Baker <hbaker1(a)pipeline.com> > >So perhaps it might take longer, perhaps much, much longer, for a >tilt to dissipate? Maybe this sort of tidal effect falls off >exponentially with distance, so bodies far enough away are >"protected"? If by "exponentially" you mean "a lot"!-) The effect must fall off with a power of the distance. Power is force times speed the force is pushing through, in this case the rate of spin times both masses times the planet's radius. Tidal force must be like the difference between gravity on the two sides of the planet 1/d^2 - 1/(d+r)^2 2dr + r^2 ----------------------- d^4 + 2(d^2 r) + d^2 r^2 About r/d^3. Physics to me seems like having spears of units thrown at you from all directions and dodging them so they cancel. I think both the radius and mass of the satellite cancel when you want to know the half-life of the spin rate. Sun Earth Moon mass 2e30 kg 6e24 kg 8e22 kg distance 1.5e8 km 4e5 km radius 6e3 km 2e3 km The distance from the parent is 375 times as much, and the mass of the parent is 3e5 times as much, so 375^3 / 3e5 ~= 176 times as long to slow down............? --Steve

2 1

Re: [math-fun] NP-complete matching problem?
by Dan Asimov 13 Apr '10

13 Apr '10

Allan wrote: << Alternatively, the instance is an (N,N)-bipartite graph, and a solution consists of a degree-1 subgraph (a matching) that includes all the vertices, or the assertion that no such matching exists. >> This is very close to a problem that came up in my research, which turns out not to be crucial to me, but may be interesting in its own right: Given a graph K with |K| embedded in a orientable surface S, call (S,|K|) a "map" (think geography). Now we define what makes a map a "regular map": Let the connected components of S - |K| be called "faces", the edges of |K| "edges", the vertices of |K| "vertices". Let any triple (v,e,f) of face f that contains edge e that in turn contains vertex v, be called a "flag". It's easy to see that a flag can be used to define an orientation of the surface. An "automorphism" of a regular map is a homeomorphism from S onto itself that carries |K| onto itself. Finally, suppose that any homeomorphism of any flag onto [another flag that defines the same orientation] can be extended to an automorphism of the map to itself. Then (S,|K|) is a "regular map". Examples include all the regular polyhedra (S = S^2), and in fact exist on all compact orientable surfaces. There are 3 well-known geometric examples on the Euclidean plane. And infinitely many on the hyperbolic plane -- with q p-gons around each vertex, whenever (p-2)*(q-2) > 4). (By geometric I mean that the automorphisms of the map are all isometries of S.) Finally, the question: Suppose (S,|K|) is a regular map with either an even number, or infinitely many, vertices. QUESTION: Does there exist a set of edges that contains all vertices exactly once? This is easy to verify for the regular polyhedra, but there doesn't seem to be any obvious pattern. --Dan ________________________________________________________________________________________ "Outside of a dog, a book is man's best friend. Inside of a dog, it's too dark to read." --Groucho Marx

1 0

[math-fun] Best proof that RSA Public-Key Cryptography works ?
by Guy Haworth 13 Apr '10

13 Apr '10

I've had cause to revisit my notes on RSA Public Key Cryptography. The proof that it works is trivial if the message 'm' is coprime to the 'n' = p*q which features in the Public Key. I've seen no mentions of the case when m is divisible by p or q. Is there a neat proof handy that it doesn't matter if 'm' is divisible by p or q? Apologies as this is probably a noddy one, but thanks in advance. Guy

3 2

Re: [math-fun] Best proof that RSA Public-Key Cryptography works ?
by Mike Speciner 13 Apr '10

13 Apr '10

phi(n) = phi(p)*phi(q) = (p-1)*(q-1). If m is divisible by p, m = 0 (mod p), so m**phi(p) = 0 (mod p), so m**(k*phi(n) + 1) = 0 (mod p). Since 0 < m < n and (p,q)=1, m**phi(q) = 1 (mod q), so m**(k*phi(n)+1) = m (mod q) By Chinese remainder theorem, m**(k*phi(n)+1) = m (mod p*q). Of course, if you ever send such a message m, a simple gcd of the encrypted message with n will discover n's factorization, thereby breaking the code. RSA works because the probability of coming up with such a message is very small. --ms On Tuesday 13 April 2010 11:35:23 Guy Haworth wrote: > I've had cause to revisit my notes on RSA Public Key Cryptography. > > The proof that it works is trivial if the message 'm' is coprime to the > 'n' = p*q which features in the Public Key. > > I've seen no mentions of the case when m is divisible by p or q. > > Is there a neat proof handy that it doesn't matter if 'm' is divisible > by p or q? > > Apologies as this is probably a noddy one, but thanks in advance. > > Guy > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

[math-fun] Fwd: Sticky Towers of Hanoi
by Thane Plambeck 11 Apr '10

11 Apr '10

Sent from my iPad Begin forwarded message: > From: Alex Fink <finka(a)math.berkeley.edu> > Date: April 10, 2010 11:21:52 PM PDT > To: rjn(a)mathstat.dal.ca > Cc: Thane Plambeck <tplambeck(a)gmail.com> > Subject: Re: [math-fun] Sticky Towers of Hanoi > > I think I've managed to piece together what the game was. Thanks to > Aaron Siegel for jogging my memory. > > Sticky Towers of Hanoi is played with the disks of an n-disk ToH set > (the pegs can be disregarded). In the initial position all of the > disks are separate. In a general position there will be stacks of > fused disks, with top radius and bottom radius differing. A move is > to pick up a stack S and set it on another stack whose top radius > exceeds the bottom radius of S; this causes the two disks that come in > contact to fuse. Normal (or misere) play convention. > > This reduces to a game on posets, interval orders to be precise. > > I remember analysing the game with Conway through n=8. I doubt I > could find the results (the papers could be in any state of > disorganization in either of two cities) but it doesn't seem like a > difficult programming task to replicate or surpass it. > > best, > Alex > > On 9 April 2010 09:11, <rjn(a)mathstat.dal.ca> wrote: >> Thane, >> >> I remember Alex Fink did a lot of work with Conway on this problem. >> >> Richard >> >>> I remember writing a program for it, similar to one that Erik Demaine >>> (who was also there) wrote, but I don't remember the rules. Erik? >>> >>> Sent from my iPad >>> >>> On Apr 8, 2010, at 9:49 PM, Fred lunnon <fred.lunnon(a)gmail.com> wrote: >>> >>>> Sticky Towers of Hanoi was apparently invented by John Conway, >>>> while attending a Combinatorial Theory Workshop held at "BIRS" >>>> (Berkeley?) in June 2005, and attended by (amongst others) >>>> Richard Guy and (Thane?) Plambeck [we know what you did >>>> last summer]. See >>>> https://www.birs.ca/workshops/2005/05w5048/report05w5048.pdf >>>> >>>> Is anyone in a position to disclose to us the rules pertaining to >>>> this mysterious diversion? >>>> >>>> Fred Lunnon >>>> >>>> _______________________________________________ >>>> 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 >>> >> >> >> -- >> Richard Nowakowski >> Dept. Mathematics & Statistics >> Dalhousie University, >> Halifax NS, B3H 3J5 >> Canada >> >> Phone (902)-494-6635 >> FAX (902)-494-5130 >> >> >> >> -- >> Richard Nowakowski >> Dept. Mathematics & Statistics >> Dalhousie University, >> Halifax NS, B3H 3J5 >> Canada >> >> Phone (902)-494-6635 >> FAX (902)-494-5130 >> >> >> >>

3 2

Re: [math-fun] Dumb astronomy question
by Henry Baker 11 Apr '10

11 Apr '10

Perhaps if the main body is close enough/massive enough, the tidal forces conspire to eventually kill the tilt, e.g., Mercury/Sun (0 degrees) & Earth/Moon (1.5 degrees) ? http://en.wikipedia.org/wiki/Axial_tilt So perhaps it might take longer, perhaps much, much longer, for a tilt to dissipate? Maybe this sort of tidal effect falls off exponentially with distance, so bodies far enough away are "protected"? At 09:46 PM 4/10/2010, Joshua Zucker wrote: >Tidal forces don't get rid of the tilt, they cause precession.

1 0