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

Re: [math-fun] sudoku, uniqueness, proofs
by dasimov＠earthlink.net 07 Mar '06

07 Mar '06

Michael Kleber's post led me to wonder about a related issue: Suppose a sudoku has *exactly* 2 solutions. Then what is the maximum number of boxes that can differ in the two solutions? I'd like this question a bit more if it were imo "purer": The whole sudoku idea could be played based instead on finishing merely a Latin square (each row and column of an NxN square must contain all N of a set of N distinct tokens). So here's a question: What is the set comp(N) of numbers C such that there exists a partially completed NxN Latin square having exactly C completions? I strongly suspect that if N >= 4, then 2 belongs to comp(N). In which case we can go back to the original question for each N and ask, Given an NxN partially completed Latin square having exactly 2 completions, what is the maximum number of squares that can differ between its completions? --Dan

2 1

Re: [math-fun] Pandiagonal Sudoku?
by Sterten＠aol.com 07 Mar '06

07 Mar '06

yes, but the task is to find all of them. I found all symmetric ones for 17*17, presumably many/most are symmetric. Another idea: can we superimpose two pandiagonal 5^4 latin tesseracts ?

1 0

Re: [math-fun] sudoku, uniqueness, proofs
by dasimov＠earthlink.net 07 Mar '06

07 Mar '06

Gary wrote: << There are two concentric circles, A and B. There is a line segment which is a chord of A and tangent to B. This line has length 10. What is the area of the annulus between the two circles? There is a mathematical solution: . . . There is also a "meta"-solution: Since this puzzle must have a reasonable solution, the size of the circles are probably irrelevant. . . . . . . My question is, is this second proof a valid proof? If we had a proof checking program, and we fed it this proof and asked if it is correct, would it say "yes" or "no" ? If the answer is no, then why do we accept such solutions in exams/puzzle competitions? If a student submitted something like this in a puzzle competition (e.g. Putnam or olympiad) or even on a homework, we would all jump up and down with delight at the ingenuity. Well I would. I would be glad to have a student who thinks outside the box. Should I turn around and tell such a student that the argument is not valid? >> Are you sure that such solutions *are* given full credit in Putnam exams and Olympiads? I don't know if that's the case. I would definitely *not* give full credit for such a solution, though I wouldn't deduct a lot, either. The ideal student would use the absence of information as a tip-off that the answer most likely is independent of the missing info, and then prove this fact as part of the solution. (It's really not that hard to label a diagram and then write r^2 + 5^2 = R^2, so pi*R^2 - pi*r^2 = pi*(R^2 - r^2) = pi*25.) --Dan

1 0

Re: [math-fun] Pandiagonal Sudoku?
by Sterten＠aol.com 07 Mar '06

07 Mar '06

I generated pandiagonal latin squares of size 17*17 some time ago. _http://groups.yahoo.com/group/magiccubes/_ (http://groups.yahoo.com/group/magiccubes/) The same method was already too slow for 19*19 AFAIR, but some heuristics to find _some_ solutions could be feasable. Maybe searching with the additional 5*5-squares constraint too. You can make these from 25-queen solutions and some other tricks. There could be something in the paper from Jordan Bell Guenter. --------------------------------------------------------- Christian Boyer <cboyer(a)club-internet.fr> wrote: Do you know if a pandiagonal Sudoku has already been published? I have a 25x25 example, the smallest possible size for this problem, but perhaps the same work has already been done. "Pandiagonal Sudoku" means that all the diagonals and broken diagonals of the square should also contains all the numbers, as it is for rows, columns, and sub-squares. It is proved that a pandiagonal Latin square cannot exist for 2k and 3k orders, meaning that a pandiagonal Sudoku of standard size (9x9) is impossible. I know published 25x25 pandiagonal Latin squares, but they are not Sudokus, because they are not organized in 5x5 sub-squares. Christian.

2 1

Antwort: Re: [math-fun] Most influential mathematician?
by dirk.lattermann＠bgs-ag.de 06 Mar '06

06 Mar '06

Hello, this is maybe such a project: http://www.qedeq.org/index.html Greetings, Dirk Lattermann "David Wilson" <davidwwilson(a)comcast.net>@mailman.xmission.com am 03.03.2006 15:28:48 Bitte antworten an math-fun <math-fun(a)mailman.xmission.com> Gesendet von: math-fun-bounces+dirk.lattermann=bgs-ag.de(a)mailman.xmission.com An: "math-fun" <math-fun(a)mailman.xmission.com> Kopie: Thema: Re: [math-fun] Most influential mathematician? What is needed is not an influential voice so much as an ambitious doer, someone who will start the project instead of talking about it. As Goethe said: What you can do, or dream you can do, begin it! Boldness has genius, power and magic in it. If someone started such a project, those influential people with opinions on the way it should be carride out would soon be on the bandwagon, and probably take over the project. ----- Original Message ----- From: "Steve Gray" <stevebg(a)adelphia.net> To: "math-fun" <math-fun(a)mailman.xmission.com> Sent: Thursday, March 02, 2006 9:10 PM Subject: Re: [math-fun] Most influential mathematician? > I published a proof in the 3/2003 Monthly that I was then not sure was > correct and, after thinking about it for hours, I'm still not sure! It doesn't > look like other proofs, involving a trick that seems a little too arbitrary, > and I don't know quite how to think about it. > Maybe the computer could tell me. > :o > > Steve Gray > > ----- Original Message ----- > From: "Henry Baker" <hbaker1(a)pipeline.com> > To: "Gareth McCaughan" <gareth.mccaughan(a)pobox.com> > Cc: <dasimov(a)earthlink.net>; <math-fun(a)mailman.xmission.com> > Sent: Thursday, March 02, 2006 5:02 PM > Subject: Re: [math-fun] Most influential mathematician? > > >> Computer proof-checking technology (HW & SW) have gotten to the point >> where it now makes sense to develop a system whereby _every_ mathematical >> proof could eventually be _checked_ by computer. This won't happen >> overnight, but will require a 10-20 year effort to develop a generic >> system into which one could shovel all the lemmas, theorems, etc., so >> that _every_ paper submitted to a math journal would come with its own >> certification that the proof is valid. > > > > _______________________________________________ > 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

2 1

Re: [math-fun] Most influential mathematician?
by Henry Baker 06 Mar '06

06 Mar '06

Dear Dan, et al: I was trying to find someone alive, as I wanted to find someone with the credibility to influence non-mathematicians, in much the same way that Einstein helped convince Roosevelt & others re the atom bomb. Sorry about the confusion. At 09:35 AM 3/2/2006, dasimov(a)earthlink.net wrote: >Henry writes: > ><< >Does anyone on this list have a suggestion of who is the most >influential mathematician today? I'm looking for someone of >the stature of Hilbert; i.e., someone whom most people inside >& outside of mathematics would acknowledge as being influential. > >Of course, this presumes that anyone outside of mathematics >knows or cares about mathematicians! >. . . >>> > >As you suggest, there is little overlap between the most influential >mathematicians and the ones most known to the general population. > >So it may be necessary to narrow down what you're asking for some more. > >You said most influential *today*, but not that the mathematician need be >alive today. I'm not sure what you meant regarding this. > >Shiing-Shen Chern, the differential geometer (1911-2004) is said to be >well-known to the general population of China. Cf. <http://en.wikipedia.org/wiki/Chern>. > >Martin Gardner (mostly self-taught in math) and Ian Stewart are widely known >as popularizers of math; many mathematicians attribute their choice of profession >to Gardner's columns in Sci. Am. > >Within math per se, I think of John Milnor and Jean-Pierre Serre as probably the >most influential mathematicians alive today. (I'd pick Milnor over Serre, because >Milnor's scope is probably wider and he's written more math texts, all of which are >gems of exposition, and accessible survey articles.) > >Excluding Euclid, Pythagoras, Archimedes, and Al-Khwarizmi for being in different categories, >I'd say that Carl Friedrich Gauss is the clear winner, if the question is which mathematician >living or dead, has had the most impact on modern civilization AND within math per se. >Cf. <http://en.wikipedia.org/wiki/List_of_topics_named_after_Carl_Friedrich_Gauss> for >evidence of this. (Full disclosure: I would've said Gauss anyway, but recently learned >from the Mathematics Genealogy Project that Gauss is a direct mathematical ancestor >of mine, i.e., via a sequence of thesis advisors.) > >--Dan

14 19

[math-fun] proofs; sudoku
by Schroeppel, Richard 06 Mar '06

06 Mar '06

Anyone is free to include in their math paper a statement of the shape "Computer checkable proofs of Theorems 1 and 2, and Lemmas 3-6, are available at the URL math.foo.edu/~baker/paper7.txt" . Maybe noone has thought to do it yet. An extreme endpoint of checking is verifying a Mersenne Prime, where you pretty much have to repeat the LL test. But of course they do that anyway. A checkable proof of the Odd Order Theorem could be very useful, since it would likely result in the discovery and repair of some minor errors. But it seems unlikely that much of our edifice is built on wrong stuff, so making checks required seems extreme. And it could chase the non-detail-oriented out of the profession. (Or perhaps they'd make their grad students do it. Hmmm. Would the 8th Amendment apply?) ---- Sudoku: I ran across a moral dilemma in a Sudoku last night: Can I use the uniqueness of the solution to exclude some lines of argument? My partial solution looked like this: Z - Z | * * * | * * * x - x | * * * | * * * x - x | * * * | * * * --------------------- x - x | * * * | * * * x x ? | * * * | * * * x - x | * * * | * * * --------------------- x x x | * * * | * * * x x x | * * * | * * * Z x Z | * * * | * * * x is a known value, - is an empty cell (so far), * could be either. I knew that the left column Z,Z values had to be 2,6 in some order, and the third column Z,?,Z values had to be 2,3,6 in some order. I observed that, if I assigned 3 to the ?, that the Zs could be either 2,6 and 6,2, or vice versa. If one solution worked, the other would also, since all the puzzle constraints on uniqueness etc. would be satisfied in either case. Hence, if I used my meta-knowledge of a unique solution, I could exclude the value 3 in the ? cell. Dilemma: Is this fair? In a race, there's no way to exclude the inference; and we used to do similar things on multiple choice tests. But for self solving, should the conclusion be allowed? Rich

4 3

Re: [math-fun] Proof checking and program checking
by The Purple Streak, Hilarie Orman 06 Mar '06

06 Mar '06

I did a little of this stuff many years ago, mainly for software verification. The surprising thing is that many errors are caught during the process of preparing the material for verification, and almost none are caught during verification. This latter arises either because the specification is wrong in some respect (e.g., doesn't capture the concept precisely) or because the verification system is faulty, or because there aren't any errors left (hah!). At the time, there seemed to be general agreement that the process of specifying and verifying things (theorems, software, hardware) was valuable, but it was also extremely expensive and required a new class of experts. Automated theorem verification could become a new mathematical specialty, generating its own kind of complexity theorems and great unsolved problems. Hilarie

3 2

[math-fun] Re: a(n) = trace(B(A^n))
by Joerg Arndt 05 Mar '06

05 Mar '06

* Edwin Clark <eclark(a)math.usf.edu> [Mar 04. 2006 22:55]: > > In discussing Creighton Dement's floretion generated > sequences with him I came across the following fact: > > Every sequence a(n) defined by a k-th order linear recurrence > with constant coefficients over any commutative ring with identity > can be realized in the form > > a(n) = trace(B(A^n)) > > where A and B are k x k matrices over the ring in question. > > Surely this must be known! Can someone provide a reference? > > [Taking A to be the companion matrix of the polynomial defining > the recurrence will clearly give a sequence satisfying > a recurrence relation of order k with the desired coefficients > then one just needs to fiddle with B to get the desired initial > terms. One can take all entries of B to be 0 except for the > last column and it is not too hard to find a formula for the > last column of B in terms of the coefficients and initial > conditions.] > > --Edwin Note that practical computations can be much accelerated via computations modulo the polynomial (cf. p.463 of the fxtbook, http://www.jjj.de/fxt/fxtpage.html#fxtbook ). I'd very much appreciate a reference for that one, too (found it myself). jj

1 0

[math-fun] Re: proofs
by James Propp 04 Mar '06

04 Mar '06

>Anyone is free to include in their math paper >a statement of the shape "Computer checkable proofs >of Theorems 1 and 2, and Lemmas 3-6, are available >at the URL math.foo.edu/~baker/paper7.txt" . >Maybe noone has thought to do it yet. Doron Zeilberger does exactly this in many of his articles. Jim Propp

2 1