I suppose it has been a few years since there was a math-fun discussion which turned on the difference between a proof based on ZF and a proof based on ZF+Consis(ZF) -- that is, a proof in which you need to assume the extra axiom that ZF is consistent. The answer to Gary's "is this a valid proof" question, and the sudoku question to which he's drawing the analogy, both boil down to asking what your set of axioms is. In calculating the area of the annulus, Gary's second proof is valid only if you assume that the answer is independent of the radii -- which is, perhaps, an application of the pseudo-axiom "there is something clever which makes this problem worth asking", a frequent domain in which to solve olympiad-style problems. If you came across a similar but "naturally-occurring" problem -- one where it hadn't already been subjected to a selection process to eliminate boring questions -- then you would likely use different techniques to solve it. Similarly, as Gary said, most sudoku enthusiasts seem to agree that the axioms you're working under are "Each row/column/box contains one of each number, and the solution is unique." If you handed such solvers a puzzle with multiple solutions, they might well "solve" it using their axiom set -- which, note, makes false assumptions -- and conclude that they had found "the unique" solution, while in fact they had only found one of several. (If you were lucky, maybe you could even get them to conclude that the puzzle has no solution at all, when in fact it has more than one.) Note that this question of axioms is related to, but not the same as, the question of legal deductive techniques -- that's a question of what steps may appear in a proof, not of what axioms you assume. In a sense, a sudoku's "difficulty rating" is an assertion that a certain set of techniques suffice to solve this puzzle. You could imagine expanding your bag of tricks by adding the difficulty of the puzzle as yet another axiom: "This puzzle is rated as `devious', but if this box here held a 3, then I'd be able to solve the whole thing using only `beginner'-level logic. Therefore this box must hold an 8!" I doubt that many sudokists would condone that line of reasoning. --Michael Kleber On 3/7/06, Gary McGuire <Gary.McGuire@nuim.ie> wrote:
Re the threads on proofs, and sudoku uniqueness, I thought of a question relating the two threads.
Before I ask my question, I'll quote the example from Huang's post :
-----------------------
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:
Let the radius of A be a and the radius of B be b. Now, call one endpoint of the line segment X, and the tangent point of the line segment to B we will call Y. Call the centers of the two circles Z. Now, since X is on circle A, we know XZ = a. Since Y is on circle B, we know YZ = b. Since YZ is a radius of B and Y is a tangent point of segment XY, we know that angle XYZ is a right angle.
Finally, since we know that the extended line going through YZ is a diameter of A and that if a diameter of a circle intersects a chord at right angles then it bisect the chord, XY must be half the length of the chord, to wit, 5. By the Pythagorean theorem on right triangle XYZ, we know that 25 + b^2 = a^2, or 25 = a^2 - b^2.
Now, the area of the annulus is the area of A minus the area of B. To wit, the area is pi a^2 - pi b^2, which is equal to pi (a^2 - b^2) = 25 pi. Therefore the area is 25 pi.
There is also a "meta"-solution:
Since this puzzle must have a reasonable solution, the size of the circles are probably irrelevant. Then consider the case where circle B has radius 0. In that case, B becomes a point (the center), the chord becomes a diameter of A, and the annulus becomes the area of A. The question is then: Given that the diameter of a circle has length 10, what is its area? This is easily found to be 25 pi.
----------------------------------
The first proof is a valid proof. If we ran it through a proof-checker, we would get a positive answer "yes this is valid".
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?
Gary McGuire _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.