July 2005 - mathfun@mailman.xmission.com

[math-fun] Re: counting Latin squares
by dasimov＠earthlink.net 21 Jul '05

21 Jul '05

Gary McGuire writes: << Call two completed sudoku grids "equivalent" if one can be obtained from the other by a sequence of the following operations: 1) permutation of the digits 1-9 2) permutation of the rows. These come in two types: a) permute the three rows within a given band b) permute the bands 3) permutation of the columns, same two types. 4) rotation, reflection >> This makes me realize that my previous attempt to define an equivalence relation on Latin squares was much too weak. (I'm more interested in Latin squares than Sudoku grids with their kind-of random condition on certain 3x3 squares.) Call two of these equivalent if they become identical by some combination of the following: 1) any permutation of the n symbols 2) any permutation of the n rows 3) any permutation of the n colums 4) application of any dihedral element from D_4. This suggests most equivalence classes have 8(n!)^3 elements (but not necessarily that many since some combinations of these equivalencing operations may not change anything). Problem: How many n by n Latin squares are there before taking equivalence classes? How many equivalence classes are there? --Dan

1 0

[math-fun] sudoku diagonals
by Gary McGuire 21 Jul '05

21 Jul '05

>HOW ABOUT THE SUPERDOKU WITH ADDITIONAL DIAGONAL AND ANTIDIAGONAL >CONTAINING ALL DIGITS? > >JOHN MCKAY These have been around for yonks in the puzzle books as a variation on "number place" puzzles, which is what sudoku is called sometimes. You can certainly have ordinary sudoku completed grids that have this property, one below. I don't know if this is what you meant, but you can also have sudoku puzzles that cannot be done without having this extra piece of information. If you want *all* the diagonals (the pan-diagonals) to have all the digits, then I don't know the answer. Gary McGuire --------------------------------- 492|681|573 357|249|168 816|735|924 ---+---+--- 573|168|492 168|924|357 924|573|816 ---+---+--- 681|492|735 249|357|681 735|816|249

1 0

[math-fun] sudoku groups
by Gary McGuire 21 Jul '05

21 Jul '05

One of the big sudoku questions was: How many completed Sudoku grids are there? This was answered, see http://www.shef.ac.uk/~pm1afj/sudoku/ The answer is 6670903752021072936960. Call two completed sudoku grids "equivalent" if one can be obtained from the other by a sequence of the following operations: 1) permutation of the digits 1-9 2) permutation of the rows. These come in two types: a) permute the three rows within a given band b) permute the bands 3) permutation of the columns, same two types. 4) rotation, reflection A sequence of these transformations that maps a grid to itself is called an automorphism of the grid. Example: 124|567|893 378|294|516 659|831|742 ---+---+--- 987|123|465 231|456|978 546|789|321 ---+---+--- 863|972|154 495|618|237 712|345|689 the permutation (1397)(2684) on the digits followed by a clockwise rotation through 90 degress is an automorphism. Question: what are the possible automorphism groups? Or equivalently, how many sudoku grids are there up to equivalence? This has been answered, see http://www.shef.ac.uk/~pm1afj/sudoku/sudgroup.html Now: is this helpful in the problem of searching for a sudoku puzzle with 16 clues? I think fated sets are invariant under an automorphism. Therefore we only need choose one grid from each equivalence class and compute all the fated sets. Unfortunately there are 5472730538 equivalence classes. Anyway, in the computer search for a 16, we don't want to choose two grids that are equivalent. Gary McGuire

1 0

[math-fun] Irrationality proofs
by dasimov＠earthlink.net 20 Jul '05

20 Jul '05

The cutest proof I've seen that sqrt(2) is irrational goes like this: If the hypotenuse of a 1,1,sqrt(2) rt. triangle = p/q, then magnifying by q gives a similar triangle w/ all sides integers L,L,H. Call the sides L1,L2,H. Using (L1 int H) as center, draw the 45-deg. circular arc A of radius L between H and L1. [Erecting a perpendicular to H from where A meets H, extended to reach L2] defines a smaller, similar right triangle whose sides are H-L, H-L, 2L-H (the last by the equality of 2 tangents to a circle from an external point). We can now continue this process to obtain an infinite sequence of similar rt. triangles w/ integer sides, each smaller than the last -- contradiction. (Tom Apostol is one discoverer of this proof; maybe JHC is another?) QUESTIONs: Can this proof be imitated to show other square roots are irrational? (If so, how do we avoid proving that, e.g., sqrt(3^2 + 4^2) is irrational?) What about just trying to show all sqrt(n^2 +1) are irrational? --Dan

1 0

[math-fun] sudoko
by Richard Schroeppel 19 Jul '05

19 Jul '05

I was puzzled about Sudoku, mentioned in a recent message. It's apparently well known on the puzzle circuit. Here's an example I swiped from last Monday's USA Today -- they've started running a daily puzzle. - 6 - | 3 - 8 | - 7 - - - - | - - - | - - - 4 3 - | 6 - 1 | - 9 5 ------+-------+------ - - 5 | - 4 - | 7 - - - - - | - 1 - | - - - - - 1 | - 2 - | 8 - - ------+-------+------ 9 2 - | 4 - 5 | - 3 6 - - - | - - - | - - - - 8 - | 7 - 9 | - 4 - In a completed sudoku, each row and column of the puzzle has one occurence of each digit from 1-9. (This makes it a Latin Square.) In addition, each of the nine marked 3x3 subsquares has (one of) each digit. The solver's job is to fill in the blanks in the puzzle. I think the one above would qualify as simple; I was able to complete it without much "advanced reasoning". Rich rcs(a)cs.arizona.edu

6 8

[math-fun] Re: SUDOKU - TO SUPERDOKU
by MCKAY＠vax2.concordia.ca 19 Jul '05

19 Jul '05

HOW ABOUT THE SUPERDOKU WITH ADDITIONAL DIAGONAL AND ANTIDIAGONAL CONTAINING ALL DIGITS? JOHN MCKAY

1 0

Re: [math-fun] sudoko
by dasimov＠earthlink.net 19 Jul '05

19 Jul '05

Just curious: Is there a closed formula L(n) for the total number of Latin squares on n symbols? (If not, how 'bout an asymptotic expression?) (Even better: Assume we equate two Latin squares if they differ only by 1) a dihedral transform 2) a permutation of the n symbols 3) two cyclic permutations, applied resp. to the rows and columns. These should lower the count by a factor of roughly 8 n^2 n!. Roughly, since a 3) might yield the same result as a 2). Making this exact seems hard.) --Dan

1 0

[math-fun] 999,999,999,999 places of pi on the wall, 999,999,999,999 places of pi;
by Richard Schroeppel 18 Jul '05

18 Jul '05

This looks cute. --Rich ----- Subject: [CCA] "Many Digits" Friendly Competition 2005 : Call for Participation From: Milad Niqui <milad(a)cs.ru.nl> Reply-To: manydigits(a)cs.ru.nl Date: Fri, 15 Jul 2005 20:57:26 +0200 Sender: owner-cca-list(a)fernuni-hagen.de [Apologies for multiple copies] THE "MANY DIGITS" FRIENDLY COMPETITION 2005 4 October 2005 Radboud University, Nijmegen, The Netherlands Call For Participation <http://www.cs.ru.nl/~milad/manydigits> In the Institute for Computing and Information Sciences at Radboud University Nijmegen we will organise a friendly competition/benchmark session for investigating the state of the art in the various implementations of exact real arithmetic. The event will be held on October 4th 2005, in conjunction with the Small TYPES workshop on Constructive analysis, types and exact real numbers <http://www.cs.ru.nl/fnds/typesreal/>. The event will be akin to those held in CCA00 <http://www.cs.swan.ac.uk/~csjens/pdf/resart.pdf> and CCA2002 <http://www.informatik.uni-trier.de/~mueller/cca2002/>. All the interactive software packages capable of handling arbitrary precision arithmetic on elementary functions are invited to participate. Moreover all libraries for handling arbitrary precision arithmetic in any programming language are welcome to participate provided that the participant writes a suitable interface/program. The participants can choose to attend the event at Nijmegen, or they can choose to participate remotely via Internet. Friendly Competition The friendly competition consists of giving a solution to a set of problems that are posed by the organisers shortly (few hours) before the event. The problems cover the minimum abilities of a system capable of handling the elementary real functions and are expected to ask for a large (>=10,000) number of digits. An example of a problem that might be in this set is to calculate the first 10,000 digits of sin(sin(1)). A set of `practice problems' can be found on the website of the competition <http://www.cs.ru.nl/~milad/manydigits/sample_questions.php>. The solutions consist of the input needed to generate the answers to the problems plus the answers themselves. The competition criteria will be the accuracy (correctness) of the solution and the time needed for producing the solution. Apart from this, we will also compare the other aspects of the solutions (such as memory usage and readability and length of the input code) to give a better comparison. On the day of the competition the solutions will be executed by participants on one specific machine at the event site, under either Debian/GNU Linux or Windows XP. A more detailed description of the setup and format of the competition can be found on the website of the competition <http://www.cs.ru.nl/~milad/manydigits/rules.php>. The outcome of this friendly competition is expected to give a comparison in performance of the systems that chose to participate for the selected problems. Remote Participation In case of remote participation, the participants will receive the set of problems by email. Then they will be given the opportunity to log into our local machine and perform their solution. Systems, Packages and Libraries Those who wish to participate in the Friendly Competition are expected to provide the software necessary for their solutions, so it can be run on the machine used for the competition. Schedule * August 26th deadline for registering for the competition * August 29th final list of registered participants on the web * September 23rd timings of the practice problems for the registered participants posted on the web * October 4th competition Registration If you are interested in participating in the event we will be happy to hear from you: 1.Team name, name and email of contact person(s) and the platform your system needs to run (GNU Linux or Windows XP). 2.Whether you plan to come to the meeting or whether you would like to participate remotely. We would prefer that participants (especially those whose system requires Windows) to send their intention to participate before August 26th, 2005. Please register by sending mail to <manydigits(a)cs.ru.nl>. Best Regards, Local Organisers: Milad Niqui and Freek Wiedijk

1 0

[math-fun] star polygon area
by R. William Gosper 15 Jul '05

15 Jul '05

(Very elementary stuff.) When n>2d, (d,n)=1, connecting every dth vertex of a regular n-gon makes an n-pointed star {n/d} consisting of d-2 concentric rings of kites surrounding a ring of isosceles triangles surrounding a regular n-gon. Working inward, successive rings of kites have winding numbers W=1,2,3,...; the triangles have W=d-1, and for the polygon, W=d. For unit edges, the area is %pi d cot(-----) n n n A(-) = ------------, d 4 where the component polygons are weighted by their winding numbers, i.e, W dx dy integrated over the whole plane. This correctly gives n n A(-----) = - A(-), n - d d i.e., mirror imaging negates the area by winding clockwise. The %pi d csc(-----) n circumradius = ----------, and the 2 %pi d cot(-----) n inradius = ----------. 2 For unit circumradius instead of unit sides, the area is %pi d sin(-----) n n n a(-) = ------------, d 2 which, for fixed n is clearly maximal for d=n/4. I.e., the star with greatest weighted area is the one with most nearly right-angled vertices, since the vertex angles are pi - 2 pi d/n. E.g., the star of Lakshmi (two squares) is maximal among the octagrams. Removing just the outermost edges that form the vertex angles leaves an {n/(d-1)} star polygon, if when (n,d-1)=g we interpret this as g {n/g,(d-1)/g} stars superposed. Interestingly, for such improper stars, continued edge deletion recovers the proper ones with lesser d. E.g., {9/4} -> {9/3} (star of Goliath = three triangles) -> {9/2}. This tells us all the interior angles. The circumradius formula for consecutive d provides the proportions of the inner stars, and hence the sizes of all the kites, etc. Note also that the area formulas work for improper stars: A((gn)/(gd)) = g A(n/d). --rwg I keep warm peanut butter in my pockets AND I VOTE

1 1

[math-fun] variants of the Kotani ant problem
by James Propp 15 Jul '05

15 Jul '05

The Kotani ant problem asks us to consider distances between points on the surface of a cube where the distance between two points is the length of the shortest path between them that stays on the surface. (See Dick Hess' article "Kotani's Ant Problem" in the book "Puzzler's Tribute: A Feast for the Mind".) Has anyone considered analogues of the Kotani ant problem for polyhedra other than cubes and rectilinear blocks, e.g., the other Platonic solids? (I'm looking for a research project for some students, and this one came to mind as something that doesn't require any post-high-school background.) Jim Propp

1 0