February 2008 - mathfun@mailman.xmission.com

[math-fun] Re: State Diagram of Hanoi & BLT
by Steve Witham 12 Feb '08

12 Feb '08

Say "Obvious Trinary" (OT) representation for the Towers of Hanoi is that the digits from least to most significant represent the disks from smallest to biggest, and each digit says which pile a disk is on. I'll call my representation "Binary-Like Trinary" (BLT). I wonder whether it's the same one Fred Lunon was talking about. Loosely, Gray Code : Obvious Trinary (one digit changes at a time) :: Regular binary : Binary-Like Trinary (easy to compare) Here's the state diagram for the three-disk puzzle, labeled in BLT: 111 110 112 101 100 121 102 011 120 010 122 012 001 000 211 021 002 210 020 212 201 022 200 221 202 220 222 All the outside-edge paths look like binary counting. The wikipedia page has a similar diagram labeled in OT: http://en.wikipedia.org/wiki/Tower_of_Hanoi#Graphical_representation The spacial arrangement, and the rule, "Take the move that gets you closest by Euclidean distance," are simpler intuitively, but I think they're harder to code than the rules based on BLT digits: A legal move in BLT (for any d, e in {0,1,2} ) is: { ..., d, n e's } <==> { ..., e, n d's } where 0 <= n < the number of digits. The "direction" toward target T from state S is: The most significant digit in T that differs from the corresponding digit in S. To move from S in direction D: Make the move that changes the least significant digit of S that is not D, to D. So, to take a shortest path from S to T: s := S while s != T: d := direction from s to T move from s in direction d s := new location There is just one shortest path from any point to a corner state. For other targets, looks like there can be at most two shortest paths. For instance, going from 022 to 120, the algorithm above takes the path 022, 021, 012, 011, 100, 102, 120, but the other shortest path is 022, 200, 201, 210, 211, 122, 120. Haven't figured out the OT <==> BLT mappings. Mumble subtract mod 3. I keep wondering what physical puzzle might correspond to Gray code. It ought to be simpler than the Towers of Hanoi, but it's not. Towers of Hanoi: you can move a disk iff there are no smaller disks on the piles you're moving it from or to. Gray code: you can move a disk iff the next-smaller disk (if any) is in state 1 and any even-smaller disks are in state 0. ??? --Steve

1 0

Re: [math-fun] Indexing the 'States of Hanoi': correction to how to find the shortest path.
by Andy Latto 11 Feb '08

11 Feb '08

(recall that given a configuration A, we denote by A' the configuration A with the smallest disk removed. A path from A to B yields a path from A' to B' by ignoring the smallest disk, and a path from A' to B' yields a path from A to B by inserting moves of the smallest disk between every two moves as needed, possibly starting and/or ending with a move of the smallest disk) > > Define a "sensible" path as one that doesn't move the same disk twice > in a row. Any shortest path from A to B is always an extension of a > sensible path from A' to B'. > > I guess what I need to prove is this: > > With 3 or more disks, any sensible path that is not the unique > shortest path is at least 2 moves longer than the shortest path. > > Prove this by tedious enumeration for N=3, and by induction for larger values. Unfortunately, this is false. There are sensible paths from (12, , 3) to (3,1,2) of lengths 6 and 7. The lemma that is true is this: Any path from A to B that is either a shortest path, or within 1 in length from a shortest path, is derived from a path from A' to B' that is either shortest, or within 1 of being shortest. Since a path from A' to B' of length N produces a path from A to B of length N, N+1, or N+2, a path from A' to B' that is two longer than the shortest path produces a path from A to B that is also at least two longer than the shortest path. This proves the lemma. So instead of "try to find the shortest path from A to B", the correct task is "try to find all paths that are within 1 of being the shortest path from A to B". Since these can be quickly produced out of all the paths that are within 1 of being the shortest path from A' to B', the shortest and near-shortest paths can be found by a simple recursive algorithm (and the near-shortest paths that you didn't care about can then be discarded). -- Andy.Latto(a)pobox.com

1 0

[math-fun] Indexing the 'States of Hanoi'
by Guy Haworth 10 Feb '08

10 Feb '08

The recent question about a fallible agent taking on the 'Towers of Hanoi' leads me to look for a way of compactly indexing the 'States of Hanoi', i.e. the different states of the 1-person game. Godel-numbering the states is too 'spacious' but might be a element of the algorithm to achieve compact indexing. All ideas welcome: thank you - Guy

2 1

[math-fun] Question about difficulty of online Set game
by Dan Asimov 09 Feb '08

09 Feb '08

We've discussed the game of Set here in the past, but for anyone unfamiliar with it I'll summarize: There is a pack of cards, each marked with a graphic having 4 characteristics (color, number, shape, shading). Each characteristic occurs in one of 3 possible ways (color = red, green, or purple; number = 1,2,or 3; shape = oval, diamond, or squiggle; shading = outline, hatched, or solid). Every combination is represented on just one card, for a total of 3^4 = 81 cards. The game is played by someone's turning over 12 random cards in a 3x4 rectangular array. The object of the game is to identify a "set" of 3 cards, defined as follows: 3 cards form a set if for each of the 4 characteristics, the 3 cards display only 1 variant, or else all 3 variants, among them. E.g, the three cards "3 green outline ovals", "2 red outline diamonds", and "1 red outline squiggle" form a set. A set may be seen to be isomorphic to the concept of an affine line in the vector space (F_3)^4. --------------------------------------------------------------------------- The New York Times website now has a daily solitaire Set game, with 4 levels of play from easy to hard. The harder levels 3 and 4 work this way: You see an image of 12 Set cards in a 3x4 array. When you identify a "set" you click on all 3 cards in turn, and the software confirms that you're right. The array of 12 cards is pre-chosen to have 6 "sets" among them, and the object is to identify all 6 of them. The online game is here: < http://www.nytimes.com/ref/crosswords/setpuzzle.html >, (but it may require a subscription to access). >>>>>QUESTION: What makes one 3x4 array with 6 sets among them "harder" than another? (I often find this online puzzle's "level 4" to be easier than its "level 3", so this has me wondering.) --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

3 2

Re: [math-fun] Question about difficulty of online Set game
by Dan Asimov 09 Feb '08

09 Feb '08

By the way, I have some additional information about the online Set game at < http://www.nytimes.com/ref/crosswords/setpuzzle.html >. I had thought there were 4 levels of play, but an employee of PUZZL.COM (which created the online version) just e-mailed me to say that, in fact, there is no difference between the algorithms by which game 3 and game 4 are chosen. (Ditto for the easier pair, game 1 and game 2.) --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

Re: [math-fun] Indexing the 'States of Hanoi'
by Dan Asimov 09 Feb '08

09 Feb '08

Guy wrote: << The recent question about a fallible agent taking on the 'Towers of Hanoi' leads me to look for a way of compactly indexing the 'States of Hanoi', i.e. the different states of the 1-person game. Godel-numbering the states is too 'spacious' but might be a element of the algorithm to achieve compact indexing. All ideas welcome: thank you - Guy >> Any state of the game is a mapping from the set D of n disks (say D = Z/nZ) to the set P of 3 posts (say P = Z/3Z). (Given the set of disks on any one post, their order on that post is determined, so this mapping determines the full state of the game.) Questions: 1. Starting any two of these 3^n states -- say A and B -- can B be reached from A by a sequence of legal moves? (If not, for which A, B is this possible?) 2. When state B can be legally reached from state A, what is an algorithm for using the fewest moves to do this? --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

2 1

RE: [math-fun] Re: another calculus question
by Dan Asimov 08 Feb '08

08 Feb '08

<< Jim asked about the integrability of 2 x sin(1/x) - cos(1/x) if x is not zero, f(x) = 0 if x is zero. The function is Riemann integrable on [0,1]. Consider the intervals from 0 to \eps, and from \eps to 1. By uniform continuity, there is some \delta such that on the larger interval, any partitions of mesh \delta, on a subinterval of \eps to 1, with any associated Riemann sums, will yield values within \eps of one another. . . . . . . >> Huh? Uniform continuuity of what? Because of the cos(1/x) term, f is not continuous on [0,1]. --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

3 2

[math-fun] Re: another calculus question
by James Propp 08 Feb '08

08 Feb '08

The sort of function I'm worried about is 2 x sin(1/x) - cos(1/x) if x is not zero, f(x) = 0 if x is zero. This function has an antiderivative, namely x^2 sin(1/x) if x is not zero, F(x) = 0 if x is zero, but is f(x) Riemann integrable? (Note that it isn't continuous.) Jim

3 2

[math-fun] yet another calculus question
by James Propp 08 Feb '08

08 Feb '08

Another question that came up today is, why introduce Riemann sums at all? "It looks like Newton got by just fine without them, if he died before Riemann was born!" Of course, Newton could have used specific Riemann sums without the full general picture Riemann developed, but it looks as if the student may have been right: I just poked around a little bit on the web to see how Newton defined integration, and was a chagrined to learn that he *defined* the definite integral of f(x) from x=a to x=b as F(b)-F(a), where F is a primitive (also known as antiderivative) of f! But surely this can't be the whole story. After all, Newton used the calculus to show that the attraction between two balls is the same if you replace either or both by a point-mass, and my impression is that he did it by dividing the balls into spherical shells, dividing the shells into bands, etc. That sounds like a (multi-dimensional) Riemann sum to me (albeit perhaps a non-rigorous one, if Newton used infinitesimal elements)! So, what's the deal with these sums? Who first used them, and who first tried to make them rigorous? If I'm hogging too much bandwidth with calculus stuff, or if this latest more-historical-than-theoretical question is inappropriate for this forum, let me know. Jim Propp

2 1

[math-fun] another calculus question
by James Propp 08 Feb '08

08 Feb '08

Here's another question: Suppose that f is continuous on the interval [a,b] and F is an antiderivative of f on (a,b) (that is, if F is a function that is continuous on [a,b] and differentiable on (a,b) with F'(x) = f(x) for all x in (a,b)). Can we conclude that f is integrable on [a,b]? (The version of the Fundamental Theorem of Calculus that Stewart gives states that, under the above hypothesis, plus the additional hypothesis that f is integrable on [a,b], we can conclude that the integral of f from a to b is F(b) - F(a). I'm asking whether the integrability of f really needs to be included as an extra assumption, or whether it follows from the other assumptions.) Thanks, Jim

2 1