July 2006 - mathfun@mailman.xmission.com

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

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

06 Jul '06

I've now implemented k=1 & k=8 (level 1) and k=2 & k=7 (level 2). I implemented k=2/k=7 in such a way that the two cells are never the same cell. Nevertheless, it appears that k=2&k=7 completely _subsume_ the k=1&k=8 cases. If I implemented k=2/k=7 in a way that allowed the cells to be the same, then this would trivially follow, but I included a check to make sure that I was never inadvertently operating on the same cell in two different roles. I.e., if the cells (i1,j1), (i2,j2) were the two cells, it is never the case that i1=i2 and j1=j2 at the same time. I should attempt to prove that if you do the level 2 checks, you should never have to do level 1 checks. LATimes "Moderate" appears to approximate my "level 2" (k=2/k=7). LATimes "Tough" and "Diabolical" are not routinely solved by my level 2, although the "Tough" ones come very close. Perhaps Tough = level 3 (k=3/k=6) ? Only a very few of "Sudoku Genius" sudoku's succumbed to level 2. ------- I implemented the k=1 & k=8 rules, and this is "level 1". Interestingly, these 2 rules are somewhat dual to one another -- perhaps someone else has better insight on this? The k=1 rule says that there's only one possibility for a cell (singleton set), so _broadcast_ this information to the rest of the row, column and block. The information flows out from the cell -- i.e., the cell itself doesn't change, but it potentially changes the rest of the row, column and block. The k=8 rule extracts information from the row, column and block to constrain what goes into the cell. All of the information goes _into_ the cell -- i.e., the only thing that changes is the cell itself. So level one is a series of waves of information alternating out & in. When there's no new information to be processed, the puzzle is either solved, or isn't crackable via level 1. "Level 1" seems to be a very natural level. Unfortunately, it isn't particularly powerful -- it can only handle the LATimes "Gentle" sudokus. "Level 2" would seem to be similar to level 1, except also handling k=2 and k=7. I haven't fully implemented this version of "Level 2", as of yet. At 10:02 AM 6/30/2006, Joshua Zucker wrote: >Right, that's the rule I was trying to state, and pointing out that >when k = 1 and k = 8 it amounts to the "if there's only one >possibility for a cell" and "if there's only one cell where the digit >can go" rules ... > >--Joshua > >On 6/30/06, Mike Speciner <speciner(a)ll.mit.edu> wrote: >>What about this rule: >> >>If the set of candidate digits for some set of k positions in a row/column/block >>has cardinality k, then those digits can be eliminated from the rest of that >>row/column/block. >> >>Is that implied by your level 1 or level 2? >> >>--ms >> >>Henry Baker wrote: >> >>> I've since extended my program to what I call "level 2" -- >>> propagating forcing constraints a bit further: >>> >>> If a digit in a _row_ can only appear in 2 or 3 positions >>> within the same 3x3 block, then that digit is eliminated from >>> the rest of the block. If the digit can appear in multiple >>> blocks, then we can't eliminate it. >>> >>> Ditto for columns. >>> >>> For blocks, the rule is more complicated. If a digit can >>> only appear within a single row or column within a block, >>> then it can be eliminated from the rest of the row or column, >>> respectively. >>> >>> These new rules, together with the previous set of forcing rules, >>> appears sufficient to solve the LATimes Sudoku's called >>> "Moderate", while the previous set of rules were sufficient >>> for those called "Gentle". >>> >>> However, my "level 2" is not sufficient for LATimes "Diabolical", >>> nor for the Sudoku's in "Sudoku Genius". >>> >>> It would appear that the LATimes _does_ have a precise definition of >>> what it means to be "Gentle" (~ level 1), "Moderate" (~ level 2), >>> and "Diabolical". >>> >>> Since "level 2" appears to be exhausting the notion of what >>> can be done with only local rules & "force fields" (the information >>> propagating on rows, columns & blocks), I would suggest that level 2 >>> captures the notion of "non-backtracking". >>> >>> --- >>> >>> BTW, I mentioned that my bit representation produced "surprises" >>> in that some squares "accidentally" produced singleton sets. However, >>> because these singletons were "accidental", they didn't get a chance >>> to propagate their "first-class" status and suppress the same digit >>> in rows, columns and blocks. While this problem is automatically fixed >>> by level 2, this constraint really belongs to level 1, and so my level >>> 1 program has to have an extra check just for this constraint. "The >>> representation giveth, and the representation taketh away."

2 2

[math-fun] Pythatgorean problem
by David Wilson 06 Jul '06

06 Jul '06

I noticed that the 8-15-17 Pythagorean triangle, has 8 = 3+5 while 15 = 3*5, and then saw that the 3-4-5 triangle has 4 = 1+3 and 3 = 1*3. These turn out to be members of a family of Pythagorean triangles with a = x+(x+2), b = x(x+2), c = x(x+2)+2. Can all Pythagorean triangles with a = x+y, b = xy be parameterized?

1 0

[math-fun] Logic puzzle
by franktaw＠netscape.net 05 Jul '06

05 Jul '06

It is well known that the first-order theory of the non-negative integers with only addition available is decideable, while the theory with addition and multiplication is not. Suppose we have addition and the number of divisors function (often called d(n) or tau(n)). Is the theory then decideable or not? Proof requested. Franklin T. Adams-Watters

1 2

Re: [math-fun] Factorial n
by dasimov＠earthlink.net 04 Jul '06

04 Jul '06

David Wilson wrote: << I would be willing to conjecture that if there are an infinitude of primes == r (mod m), then there is a prime of this form between n and n(1+e) for sufficient n. >> Does "for sufficient n" mean for n >= N(r,m,e), so that possibly N(r,m,e) -> oo as e -> 0 ? (Or might it be just for n >= N(r,m) ?) * * * I would be willing to conjecture that for integers m > r > 0, GCD(r,m) = 1, then the fraction of primes == r (mod m) is asymptotically r/m. Does anyone know a counterexample to that? It seems that it might be a consequence of David's conjecture (or perhaps vice versa). --Dan

3 2

Re: [math-fun] Factorial n
by dasimov＠earthlink.net 04 Jul '06

04 Jul '06

Graeth wrtoe: << On Tuesday 04 July 2006 18:31, dasimov(a)earthlink.net wrote: > . . . I seem to be having a bit of trouble with number theory today. --d. You mean "it is Cohn", I take it? :-) (It certainly is on the cover of my book of that title that makes exactly the same statements...) >> Ddi I sya nmuber thorey? I mnea usnig ym brnai. --dna

1 0