[math-fun] proofs; sudoku
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
That's a perfectly good deduction, but you've stated it wrong. If the 2 Z's in the first row can only be 2 and 6, and similarly for the last row, than no other number in either row can be 2 or 6. The same holds for the two columns. It even has a name, but I'm not certain what it is. Perhaps "X-wing". -- Stan Isaacs
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Stan Isaacs 210 East Meadow Drive Palo Alto, CA 94306 stan@isaacs.com
I'm a bit confused. I thought that the first column Z's could be either 2 or 6, but the 3rd column Z's could be 2, 3, or 6. If he threw out the 3 possibility, then the puzzle would have two (putative) solutions, so by uniqueness, he would know that one of the 3rd column Z's was, in fact, a 3. Of course, if the solution is truly unique, this should become apparent at some later point, but I think that he's looking for a short-cut (is that correct, Rich?). I keep expecting to run across one that has more than one solution, so I try not to throw out anything based on uniqueness. Can we capture a similar mathematical statement? Mathematically, if I know that a problem has a unique solution, and I have a partial solution where one set of choices appears to lead to consistent, multiple solutions, can I exclude that set? It doesn't seem so, but perhaps my phrasing is inadequate, or perhaps I'm misinterpreting the question. --BIll Cordwell ----- Original Message ----- From: "Stan E. Isaacs" <stan@isaacs.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Friday, March 03, 2006 12:02 AM Subject: [math-fun] Re: sudoku
That's a perfectly good deduction, but you've stated it wrong. If the 2 Z's in the first row can only be 2 and 6, and similarly for the last row, than no other number in either row can be 2 or 6. The same holds for the two columns. It even has a name, but I'm not certain what it is. Perhaps "X-wing".
-- Stan Isaacs
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Stan Isaacs 210 East Meadow Drive Palo Alto, CA 94306 stan@isaacs.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Schroeppel, Richard wrote:
---- 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?
It's a question of morals all right - I think it's a matter of preference. If you don't assume a unique solution, while deriving the solution you also *prove* that there is a unique solution. The dilemma also arises in other puzzles. Wei-Hua Huang wrote a post about it re Battleship: http://www.mountainvistasoft.com/t-uniq.htm Sometimes problems (e.g. Putnam problems) can be solved by a trick if you assume there is a solution. Huang gives a nice example. Most sudoku enthusiasts don't seem to mind assuming the uniqueness rule, judging by the hundreds, nay thousands, of forum posts on the various conclusions that can be drawn. Personally I don't like using it, but would use it if stuck. I don't find it as morally reprehensible as making an outright guess. Gary McGuire
participants (4)
-
Bill & Rosemary Cordwell -
Gary McGuire -
Schroeppel, Richard -
Stan E. Isaacs