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

[math-fun] Stirling's second
by wouter meeussen 10 Jul '06

10 Jul '06

S(n,k)=S(n-1,k-1)+k*S(n-1,k) is a well-known recursion, and I tried to find out which of the two terms dominate. So, I looked for the values n & k where S(n-1,k-1)<=k*S(n-1,k). Going down diagonals in the triangular table of S(n,k) using Table[k = 1; While[StirlingS2[n - 1 + k, k] <= (1 + k)*StirlingS2[n - 1 + k, k + 1] && k < 1000, k++]; k, {n, 256}] and I got: {1, 3, 5, 8, 10, 13, 15, 18, 21, 23, 26, 28, 31, 33, 36, 39, 41, 44, 46, 49, 52, 54, 57, 59, 62, 65, 67, 70, 72, 75, 77, 80, 83, 85, 88, 90, 93, 96, 98, 101, 103, 106, 109, 111, 114, 116, 119, 122, 124, 127, 129, 132, 134, 137, 140, 142, 145, 147, 150, 153, 155, 158, 160, 163, ... The first differences are 2 (106 times) or 3 (149 times). No regularity in sight. Picking out the positions of the 2's, I got: {1, 2, 4, 6, 9, 11, 13, 16, 18, 21, 23, 26, 28, 30, 33, 35, 38, 40, 43, 45, \ 48, 50, 52, 55, 57, 60, 62, 65, 67, 69, 72, 74, 77, 79, 82, 84, 86, 89, 91, \ 94, 96, 99, 101, 103, 106, 108, 111, 113, 116, 118, 120, 123, 125, 128, 130, \ 133, 135, 137,... Again taking first differences, {1, 2, 2, 3, 2, 2, 3, 2, 3, 2, 3, 2, 2, 3, 2, 3, 2, 3, 2, 3, 2, 2, 3, 2, 3, \ 2, 3, 2, 2, 3, 2, 3, 2, 3, 2, 2, 3, 2, 3, 2, 3, 2, 2, 3, 2, 3, 2, 3, 2, 2, 3, \ 2, 3, 2, 3, 2, 2, 3, 2, 3, 2, 3, 2, 2, 3, 2, 3, 2, 3, 2, 3, 2, 2, 3, 2, 3, 2, \ 3, 2, 2, 3, 2, 3, 2, 3, 2, 2, 3, 2, 3, 2, 3, 2, 2, 3, 2, 3, 2, 3, 2, 2, 3, 2, \ 3, 2} with the 3's at positions {4, 7, 9, 11, 14, 16, 18, 20, 23, 25, 27, 30, 32, 34, 37, 39, 41, 44, 46, 48, \ 51, 53, 55, 58, 60, 62, 65, 67, 69, 71, 74, 76, 78, 81, 83, 85, 88, 90, 92, \ 95, 97, 99, 102, 104} This seems convoluted beyond avail. Why? Wouter.

1 0

[math-fun] Rubik cube 'game graph'
by Guy Haworth 10 Jul '06

10 Jul '06

The Rubik cube is an example of both a 1-person game, and a game for which all positions can be enumerated. The number of moves taken to restore a cube to its 'home position' could be called the 'depth' of that position, analogous with nomenclature in Awari, Checkers and Chess. There can be more than one metric: in chess, more than one goal can be identified - mate, mate and/or conversion of force, mate, mate and/or conversion of force, mate and/or conversion of force and/or Pawn-push. Thus, the metric defines the graph and the depth. The key is to define an indexing of the positions, i.e., a 1-1 into mapping of {positions} --> Z, preferably [0, N] with N as small as possible. The indexing method should be usable to get the index or to derive the position of the cube from the index. Still, I would have thought that 'N' is still challenging for today's computers. 7-man chess endgames, involving an N of about 60^7 are on the limit at the moment. G

1 0

Re: [math-fun] 3-dimensional rhombus
by dasimov＠earthlink.net 10 Jul '06

10 Jul '06

Minor comment: It's not really the "Drexel" anything; rather, Drexel has in recent years provided a web-based newsreader for the much older Usenet newsgroup sci.math.research . There are a number of choices for how you can read the newsgroups, but Drexel's operation of """its""" Math Forum has been riddled with incompetence. I recommend using Google Groups for Usenet and sci.math.research in particular. For one thing, you can read *all*, not just some, of the posts there. For another, if someone cancels their erroneous post for any reason, the cancellation is reflected in Google Groups -- but not in """Drexel's""" math forum (which once had about a one-month outage when they screwed up a new software/hardware rollout). << This thing turns up in 3-D analogues of the Penrose tiling, see e.g. the Drexel Math Forum discussion by Joshua Socolar at . . . . . . >> --Dan

3 2

Re: [math-fun] diameter of Rubik's cube puzzle
by Michael Reid 09 Jul '06

09 Jul '06

> > Has the diameter of the Rubik's cube puzzle been established yet? > ... > > Later a number of variations on the original 3x3x3 puzzle appeared, > including 4x4x4, 5x5x5, and 2x2x2. It must be quite easy to find the > diameter of the last example --- does anybody know what it is? for the 4x4x4 and larger puzzles, the graph is not vertex transitive, at least not in a natural way. this is because the set of positions is naturally identified with a coset space, H \ G , with a right action of G , the group of (legally obtainable) permutations of the cubies. this of course is true for the 2x2x2 and 3x3x3 cubes, but in those cases, the subgroup H of permutations that preserve the solved state is a normal subgroup of G , so it is safe to identify the set of positions with a group, namely H \ G . this means that there is a difference between asking for the diameter of the graph, which is max d(v, w) , the maximum being over all pairs of vertices (v, w) , and asking for the maximal possible distance from the solved state, which is max d(v_0, v_1) , over all possible vertices v_1 , where v_0 is the vertex for the solved position. mike

1 0

[math-fun] 3-dimensional rhombus
by Russ Cox 09 Jul '06

09 Jul '06

complete the analogy: square : rhombus :: cube : ____ ? is there a word for such a thing? russ

4 3

Re: [math-fun] diameter of Rubik's cube puzzle
by Michael Reid 07 Jul '06

07 Jul '06

> Has the diameter of the Rubik's cube puzzle been established yet? i don't believe so. before approaching this question, one needs to decide how to measure distance. there are two common approaches, the "face turn" metric and the "quarter turn" metric. in the face turn metric, you can turn any outer face as far as you want, and it counts as 1 turn. in the quarter turn metric, each 90 degree rotation of an outer face counts as 1 turn. the quarter turn metric has the nice property that the cayley graph is bipartite. for this (and other reasons) i think it is the most natural metric to consider. i did some work on this problem way back when. in 1995, i showed that 42 quarter turns and 29 face turns are upper bounds for the diameter in the respective metrics. i also showed that the position "superflip", in which all 12 edges are flipped in place, is exactly 20 face turns from solved, and is either 22 or 24 quarter turns from start. each of these improved the known lower bounds for the diameter, which at the time were due to counting (i.e. existential) arguments. jerry bryan later showed that superflip is indeed 24 quarter turns from solved. in 1998, i discovered a related position that is exactly 26 quarter turns from solved. this position is "superflip composed with four spot"; i.e. first create the position superflip, then perform a maneuver for the pattern "four spot", which has two solved faces and four faces in which the central square is the wrong color. exercise for munsters: show that this position is locally maximal in the quarter turn metric, that is to say, any quarter turn moves you closer to the solved position. i have heard that some improvements have been found for the upper bounds, but i'm unaware of any improvements to the lower bounds. i haven't followed along since the demise of the cube-lovers mailing list, and those involved in the improvements have not gone out of their way to keep me up to date. some information is at: http://cubezzz.homelinux.org/drupal/ optimal cube solvers are available, my own is at http://www.math.ucf.edu/~reid/Rubik/optimal_solver.html and has been available since 1997. it has only a primitive text interface, but should compile and run on any ansi c system. i have another solver that uses much larger pattern databases (~883Mb) and i was recently requested to make that one available too ... but that will be on an "as time permits" basis. if you like gui interfaces and use micros**t, you should try herbert kociemba's optimal solver http://www.kociemba.homepage.t-online.de/cube.htm which has some other really cool features. mike

1 0

Re: [math-fun] diameter of Rubik's cube puzzle
by dasimov＠earthlink.net 07 Jul '06

07 Jul '06

Rich asks: << Has the diameter of the Rubik's cube puzzle been established yet? We now have enough computing power to find & prove the distance- to-start for any particular position, using the obvious square-root meet-in-the-middle algorithm and a big disk. We can search for edge positions by generating random positions and using the exact distance algorithm to guide a hill-climb away from the start position. But this is only heuristic. >> This is asking, given the usual 6 generators of the group G of all Rubik cube positions (say, holding the armature fixed), what is the maximum over all g in G of [the smallest size of a word in those generators that represents g]. A question stemming from ignorance: Are there results in this area which can specialize to answer Rich's question about G (or at least shed light on it) ? --Dan

2 1

[math-fun] Abelian group puzzle
by dasimov＠earthlink.net 07 Jul '06

07 Jul '06

Let P denote the direct product of countably many copies of the integers Z. E.g., the set {f: Z+ --> Z | f is a function} under addition of functions. Puzzle: Is P a free abelian group? Prove your answer. --Dan

5 7

[math-fun] FW: Springfield Theory - Mathematical references abound on The Simpsons
by Dave Dyer 07 Jul '06

07 Jul '06

<http://www.sciencenews.org/articles/20060610/bob8.asp>http://www.sciencenews.org/articles/20060610/bob8.asp <http://www.sciencenews.org/articles/20060610/toc.asp>Week of June 10, 2006; Vol. 169, No. 23 , p. 360 Springfield Theory Mathematical references abound on The Simpsons Erica Klarreich In the 1995 Halloween episode of the award-winning animated sitcom The Simpsons, two-dimensional Homer Simpson accidentally jumps into the third dimension. During his journey in this strange world, geometric solids and mathematical formulas float through the air, including an innocent-looking equation: 178212 + 184112 = 192212. Most viewers surely ignored this bit of mathematical gobbledygook. Fox Broadcasting Company On the fan discussion site alt.tv.simpsons, however, the equation caused a bit of a stir. "What's going on, he seems to have disproved Fermat's last theorem!" one fan marveled, referring to the famous claim by Pierre de Fermatproved just months earlierthat for any exponent n bigger than 2, there are no nonzero whole numbers a, b, and c for which an + bn = cn. The Simpsons equation, if correct, would be a counterexample to the theorem, meaning that the proof had been wrong. Plug the equation into any run-of-the-mill calculator and it seems to check out. The 12th root of 178212 + 184112, according to a calculator, is 1,922. Yet it's easy to see that the equation is false, because the left-hand side is odd, while the right-hand side is an even number. There's no paradox here: It's simply a matter of the calculator's round-off error. To David X. Cohen, the Simpsons writer who concocted the equation, the fans' responses were a source of glee. Cohen had written a computer program specifically to look for what mathematicians call Fermat "near misses": combinations of numbers a, b, c, and n that come so close to satisfying Fermat's equation that they would seem to work when tested on a calculator. Why go to such lengths for a background joke that would flash across the screen in a matter of seconds? Mainly for the fun of it, but also to flex intellectual muscles that don't typically get exercised in Hollywood script rooms: Cohen has a master's degree in computer science. As a mathematically inclined Simpsons writer, Cohen is in good company. Although nobody would call The Simpsons a science show, the writing staff boasts an impressive array of former mathematicians, scientists, and computer scientists. Over the years, they have injected their brand of geeky humor into the show. They've written hundreds of math jokes, ranging in subtlety from Cohen's fake Fermat equation to open jabs at the mathematical illiteracy of the general public. Math has occasionally even provided the theme of an episode. Digital details The Simpsons writers have a perfectionistic streak when it comes to math on the show, even when it's just for a throwaway joke. For instance, after Cohen realized that his Fermat near miss could be refuted so easily by an even-odd argument, he refined his computer program to produce a new one without that flaw: 398712 + 436512 = 447212, which appeared on Homer Simpson's basement blackboard in 1998. In another episode, Kwik-E-Mart proprietor Apu brags that he can recite pi to 40,000 decimal places. "The last digit is 1," he announces. To get that detail right, the Simpsons writing team faxed a query to NASA, where mathematician David Bailey obliged with the digit in question. The writers never put in a math joke simply to tickle only their own funny bones, according to Ken Keeler, a Simpsons writer with a Ph.D. degree in applied math. "We always think there are a moderate number of viewers who will get it," he said last October during a panel discussion about math on The Simpsons at the Mathematical Sciences Research Institute in Berkeley, Calif. "Based on the newsgroups and fan sites, it seems as if somebody finds everything we put in." The Simpsons writers often play on mathematical cultural stereotypes, extracting humor by exaggerating both the mathematical illiteracy of the U.S. public and the nerdiness and self-aggrandizement of the mathematically gifted. In a characteristic exchange, in the third-dimension episode, mad scientist Professor Frink tries to explain to Police Chief Wiggum the nature of the three-dimensional space through which Homer Simpson is wandering. Prof. Frink - Discoverer of the Frinkahedron, or cube. Fox Broadcasting Company Frink: It should be obvious to even the most dimwitted individual who holds an advanced degree in hyperbolic topology that Homer Simpson has stumbled into the third dimension. . . . (drawing on a blackboard) Here is an ordinary square. Wiggum: Whoa, whoaslow down, egghead! Frink: But suppose we extend the square beyond the two dimensions of our universe, along the hypothetical z-axis, there. This forms a three-dimensional object known as a "cube," or "Frinkahedron" in honor of its discoverer. "One of the themes we've harped on is Professor Frink trying to seize credit for something," Keeler says. "That should be very familiar to people in academia." Gender issues in mathematics take center stage in "Girls just want to have sums," which aired on April 30. It lampoons the scandal that ensued in 2005 when Lawrence Summers, then president of Harvard University, suggested that women are innately inferior at mathematics. In that Simpsons episode, Springfield Elementary School Principal Skinner is ousted after casually remarking that girls aren't much good at math. Skinner's female replacement divides the boys and girls into separate schools since, she says, girls can't learn math around "aggressive, obnoxious" boys. Brainy 8-year-old Lisa Simpson is delighted until she attends the girls' math class. "How do numbers make you feel?" the teacher begins. "What does a plus sign smell like? Is the number 7 odd or just different?" Aghast, Lisa poses as a boy to attend the ghettolike boys' school, where real math is being taught. At the climax, the Simpsons writers leave the issue of women in mathematics tantalizingly unresolved. As Lisa, aka Jake, accepts the award for best math student, she says, "I guess the real reason we don't see many women in math and science is. . ." only to be hurried off stage so that the award for best flautist can be presented. Simpsonian evolution Most of the mathematically inclined Simpsons writers also wrote for Futurama, an animated science fiction series that aired on network television from 1999 to 2003. On that show, math jokes abounded. In a typical scene, two robots meet and discover what to them is an amazing coincidence: their serial numbers are, respectively, 3370318 and 2716057. As the robots high-five delightedly, they explain to their bewildered human companions that both numbers are expressible as the sum of two cubes. The exchange is a not-so-veiled reference to a famous mathematical anecdote. When mathematician G.H. Hardy visited mathematical prodigy Srinivasa Ramanujan in a London hospital in 1917, he lamented to Ramanujan that his taxi had a very boring number, 1729. On the contrary, Ramanujan immediately replied, that number is very interesting: It's the smallest number expressible as the sum of two cubes in two different ways. In contrast to The Simpsons, Futurama permitted the writers to let their mathematical fancies run wild and to cram in math references for their personal delectation, Keeler says. "That's why it's not on the air any more," he jokes. Yet even on The Simpsons, the writers constantly have their radars tuned for opportunities to incorporate math humor. Jeff Westbrook, who has a Ph.D. in computer science, said at the panel discussion that he's on the lookout for a way to work in the Bridges-of-Königsberg problem. Mathematician Leonhard Euler famously attacked this problem in 1736, using graph theory to show that there is no route through the city of Königsberg, Germany, that traverses each of its seven bridges just once. In the meantime, Westbrook says, the Simpsons writers embedded some mathematically interesting numbers in the season finale, which has since aired on May 21. In that episode, a singing star tells her estranged baseball-player husband that she will come back to him if he can correctly guess the attendance of that day's ballgame: 8,191, 8,128, or 8,208. At the panel discussion, Westbrook declined to elaborate on just how these numbers are interesting. In the same spirit, we leave that question as a challenge to readers. (Visit the Simpsons post at <http://blog.sciencenews.org/>http://blog.sciencenews.org/ to let us know what you figure out.) As Homer Simpson would surely say, "D'oh!"

3 2

Re: [math-fun] Sudoku levels
by Henry Baker 06 Jul '06

06 Jul '06

Yes, I have a program for the "box rule", and it is indeed distinct from the pigeonhole rules. However, even with this rule and the pigeonhole rules, I can't solve sudoku's requiring "xwing"-type rules. At 05:17 PM 7/6/2006, Joshua Zucker wrote: >You certainly need the "box rule" too: that's the obvious rule about >numbers appearing at the intersection of a box with a row/column. I >think a good statement of it is: if a set of digits appears within a >box only where it intersects a certain row/column, then you can >eliminate those digits from the rest of that row/column, and >conversely (with row/column swapped with box). I hope that's at least >enough of the idea for you to figure out what I mean even if I didn't >say it right. > >--Joshua Zucker > >On 7/6/06, Henry Baker <hbaker1(a)pipeline.com> wrote: >>I've come to the conclusion that the LATimes does _not_ use a >>program to rate the Sudoku's. In the past several days, there >>have been two Moderate's: one was easily solved by my Level 1 (k=1&8), >>while the other wasn't solved by Level 3 (considering k=1,2,3, as well >>as implicitly k=8,7,6). This last Moderate should be relabeled at >>least "Tough", or worse. >> >>It also appears that the utility of the higher levels of k is very >>limited. I've only found 1 or 2 Sudokus where k=3/6 helped. >> >>Also, the "k rule" (pigeonhole rule) doesn't capture the power of some >>very useful rules, which relatively unskilled Sudoku people (like myself) >>use. >> >>I'm still trying to formalize a simple characterization of non-lookahead, >>non-backtracking strategies for Sudoku.

1 0