Talk:Mutilated chessboard problem

Solution "without proof"?

Why the solution is said to be "without proof"?--Pokipsy76 (talk) 08:56, 5 January 2008 (UTC)

Merge disscussion

Gomory's theorem is nearly the same thing. Should this be merged? If not, at least links between these articles would be appropriate. --ἀνυπόδητος (talk) 10:01, 26 October 2009 (UTC)

They are not quite the same thing (this article is about nonexistence of solutions on a chessboard with some two particular squares removed, Gomory's theorem is about existence for some other removals) but they are so close that I agree it makes sense to merge them. I have gone ahead and performed the merge. —David Eppstein (talk) 15:28, 26 October 2009 (UTC)

Additional removals

The way the article state's Gomory's theorem, it sounds like it allows multiple removals. Gomory's theorem doesn't hold if you do more than one removal. For example, you could isolate a single, white, corner square by removing 2 blacks and 2 whites.--131.122.40.229 (talk) 04:45, 9 August 2010 (UTC)

History

The problem was not introduced by Gamow & Stern (1958), as it was discussed earlier, in 1954, by Solomon W. Golomb in his paper "Checker Boards and Polyominoes" in The American Mathematical Monthly, Vol. 61, No. 10/1954, where the author calls it 'the well-known problem' which suggests the puzzle was introduced even earlier. Tavilis (talk) 19:25, 15 January 2013 (UTC)

GA Review

This review is transcluded from Talk:Mutilated chessboard problem/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: Ovinus (talk · contribs) 18:21, 14 September 2022 (UTC)

Shall review over the next few days.

GA review (see here for what the criteria are, and here for what they are not)

1. It is reasonably well written.

   a (prose, spelling, and grammar): b (MoS for lead, layout, word choice, fiction, and lists):

2. It is factually accurate and verifiable.

   a (reference section): b (citations to reliable sources): c (OR): d (copyvio and plagiarism):

   All sources appear to be reliable. Suggest you mark [11] as open access or simply link the title. Earwig yields only reverse copies.

   You mean Bilalić et al, now [12]? Ok, done, but in general I prefer to let the bots that run around adding doi-access tags handle this. Because of the subscription accesses that I have, it's not always obvious to me whether I can see a source because it's open or because I have a subscription. And I don't think the doi-access tag is especially helpful to readers; if they want to find a source, and an obviously-open source is not already linked from the url, then the next most obvious thing to do is click on the link regardless of whether it's open or not, and see what happens. The only thing the doi-access tag will do is, if you pay attention to it, give you some premonition that, when you do the thing you were going to do anyway regardless of what it said, you might not get to what you want. But that's true of all web links; they could have gone dead, or whatever other problem. —David Eppstein (talk) 19:42, 14 September 2022 (UTC)

3. It is broad in its coverage.

   a (major aspects): b (focused):

4. It follows the neutral point of view policy.

   Fair representation without bias:

5. It is stable.

   No edit wars, etc.:

6. It is illustrated by images and other media, where possible and appropriate.

   a (images are tagged and non-free content have non-free use rationales): b (appropriate use with suitable captions):

   I vectorized the lead image. Any extra images would probably be excessive, and there's already one with a real chessboard. Ovinus (talk) 18:42, 14 September 2022 (UTC)

7. Overall:

   Pass/Fail:

Spotchecks

• [1, 3, 7]: Can't access
• [9]: Fine, but do you have an alternative citation for the fact that McCarthy was first, besides himself?
  • Added another source that says he introduced this idea. —David Eppstein (talk) 18:18, 17 September 2022 (UTC)
• [11, 13, 17, 18, 19, 21, 23]: Fine
• [24]: Can't access
• [27, 28, 30]: Fine
• [31]: Can't access
• [34]: Fine
• [38]: Towing the line between original research and WP:CALC, as the source never mentions it. I'd move the citation to after "given clues" and leave the following statement uncited, since the source does not directly support the second statement. Unless the arxiv version is outdated

  Here

  Ok, footnote moved. I may have been misled by the fact that the source does actually say something about clues in two opposite corners, but not this point about them. I think the remaining unsourced bit is just an obvious translation between equivalent statements, rather than rising to the level of original research. —David Eppstein (talk) 18:25, 17 September 2022 (UTC)

Content

• The link of impossible puzzle puzzles me as it's about a specific, unrelated puzzle. Ovinus (talk) 22:21, 14 September 2022 (UTC)

  Fixed by retargeting impossible puzzle to List of impossible puzzles, I think a more appropriate link target. The specific puzzle capitalizes the phrase differently (and is not impossible). —David Eppstein (talk) 22:41, 14 September 2022 (UTC)

• "More generally, dominoes can cover all but two squares of the chessboard, if and only if the two uncovered squares are of different colors." How about recast to "More generally, if two squares are removed from a chessboard, ... two removed squares ..." Simpler parallelism Ovinus (talk) 22:21, 14 September 2022 (UTC)

  Removed vs uncovered, you mean? Ok, done. —David Eppstein (talk) 18:19, 17 September 2022 (UTC)

  Here

• Any reason why only Gamow & Stern is done inline with {{harvtxt}} in History and not the others? Ovinus (talk) 22:21, 14 September 2022 (UTC)

  Not really, fixed. —David Eppstein (talk) 22:42, 14 September 2022 (UTC)

• "It has been examined in studies of the nature of mathematical proof" I would suggest expansion of this point, as it's very interesting. For example, in the fourth one, about the difficulties of formalizing the question and its classic solution into a combinatorial statement Ovinus (talk) 22:21, 14 September 2022 (UTC)

  Er. The reason I haven't expanded it in more detail is because my impression on trying to read this material is that it's bullshit. Or maybe more charitably, the point they were trying to make did not come across clearly enough for to me to be able to provide a useful summary of it. There are no actual difficulties in formalizing the classical solution, as the final sentence of "Application to automated reasoning" on automated proof assistants should make clear. —David Eppstein (talk) 22:45, 14 September 2022 (UTC)

  Legendary. Then why cite it at all? And what about the other three refs Ovinus (talk) 23:03, 14 September 2022 (UTC)

  It is obviously reliably published, on the philosophy of mathematics related to this problem, and I don't trust my judgement of it being bogus well enough to deliberately snub it. MacKenzie also states that the coloring argument "would not become a formal proof, in the sense in which this term is used in this paper, even if the everyday terms used in the puzzle were replaced by more precise mathematical equivalents", from which I can only conclude that I have no idea what he means by a formal proof, because to me the proof-assistant proofs are very much formal proofs in exactly the sense he describes: finite sequences of formulae each one of which follows from the previous by formal logical rules of inference, rather than merely arguments designed to convince other mathematicians of the truth of something. Kerber is less problematic, basically saying that a good proof should teach you something more than merely the truth of what it proves, that automated theorem provers should be flexible enough to handle higher-level proofs that provide useful intuition about the problem, and that some of the existing automated proofs actually do so. Tanswell also recognizes the existence of formalizations of the intuitive proof, and uses them as an example for something, but it's written in high-academic language for specialists in the philosophy of mathematics, in a way that makes it difficult for non-specialists to decode. My vague impression is that it's about the fact that there can be significant differences between multiple formalizations of the same informal proof outline. —David Eppstein (talk) 23:42, 14 September 2022 (UTC)

• "If the two black corners are removed instead, then 32 white squares and 30 black squares remain, so it is again impossible" It may be obvious, but I'd suggest you mention that the colors may be interchanged, as it shows another way of looking at the problem. Ovinus (talk) 22:21, 14 September 2022 (UTC)

  Rewrote to argue that the interchanged-color case has the same reasoning rather than merely writing out the same reasoning for both cases. —David Eppstein (talk) 00:53, 15 September 2022 (UTC)

• For Winograd's proof, it's probably wise to mention the trivial base case of 7 empty squares Ovinus (talk) 22:21, 14 September 2022 (UTC)

  But it's not different than the inductive case: the 7 squares in the top row automatically have an odd number of squares not covered by dominos from the previous row, because there are no dominos from the previous row. —David Eppstein (talk) 00:55, 15 September 2022 (UTC)

  Exactly, that should be mentioned. Especially because students will like to see both the base case and the inductive step, the heavenly ingredients for induction. Often they forget the base case. (It reminds me of that puzzle of fitting the square Ls into a square twice the size minus one square, with the base case being empty. Vacuous in a lovely way.) Ovinus (talk) 01:11, 15 September 2022 (UTC)

  The text in the current article states the induction hypothesis only. The induction hypothesis is: each row has an odd number of squares not covered by dominos from the previous row. The text in the article does not go through the more detailed reasoning why the induction hypothesis is true of the base case, and why it is true in the inductive case, both of which are easy but tedious to write out. It is in that more detailed reasoning that, if it were written out, the base case and the inductive case would need to be distinguished. The base case is true because it has the top row has an odd number of squares, none of which are covered by dominos from the previous row, because there are no dominos from the previous row, so they are all uncovered, forming an odd number of uncovered squares. For the rows below the top row, the previous row has an odd number of uncovered squares by the induction hypothesis, the horizontal dominos on that row cover an even number of these squares, leaving an odd number of squares that can only be covered by downward vertical dominoes, so the current row has an odd number of dominos from the previous row covering some of its even number of squares, leaving an odd number of remaining uncovered squares, again proving the induction hypothesis. Which is all to say, when we write only the induction hypothesis for any induction proof, we do not distinguish the base case from the inductive case; it is only in proving the hypothesis that we might need to make a distinction. But spelling out the details of the proof as above in the article would likely run into issues with WP:GACR 3b: for readers who understand this kind of proof easily, it's tedious detail because they don't need it to understand the proof, and for readers who don't, it's tedious detail because it doesn't help them understand. It also distracts from the bigger picture of this proof, which is that once you're proven this thing about parity in each row you still need to count up pairs of adjacent rows to prove that there are an odd number of vertical dominos and then by symmetry an odd number of horizontal dominos, contradicting the fact that the total number of dominos should be odd. —David Eppstein (talk) 01:26, 15 September 2022 (UTC)

  It is only distracting because it is verbose. Something as simple as "The first row or column has an odd number of uncovered squares and none from the (nonexistent) previous row or column, proving the base case" suffices. It needn't be discursive or super precise to help a broader audience. Ovinus (talk) 01:37, 15 September 2022 (UTC)

  But the thing you are proving is that each row has an odd number of squares left uncovered by dominos from the previous row. It's pointless to prove that for the base case without also proving it for the inductive case. The article text doesn't do either of those things. It just states what is being proved and leaves the details of the argument as unimportant detail not stated. Maybe let's try a different example to make my point clearer. Suppose I were to say "you can prove by induction that the sum of the numbers from 1 to n is n(n+1)/2", but did not provide the details of the algebra needed to complete the proof. Would it make sense to demand that I separate out the base case from this statement of what is being proved? Would it be helpful to add "the base case is 1=1", still without giving any of the algebra in the inductive case? —David Eppstein (talk) 02:06, 15 September 2022 (UTC)

  But you do describe the inductive step: each row of the mutilated chessboard has an odd number of squares that are not covered by vertical dominoes from the previous row, and therefore an odd number of vertical dominoes must extend into the next row. That is fairly self-evident, and a student can draw it out. In my experience tutoring, the inductive step would be the easier-to-derive step than the base case, because not everyone can properly formulate the base case ex nihilo—properly figure out where to start. Re your analogy: If it were much more obvious that S(n) implies S(n+1) than it were obvious that "S(x)", where the correct x is not really specified, yes, I would note S(x). Ovinus (talk) 02:12, 15 September 2022 (UTC)

  Statement of what is to be proved:

  • S(n) = row n has an odd number of squares that are not covered by downward dominos from the previous row and an odd number of dominos that extend into the next row.

  Inductive proof that for all rows except the last one, S(n):

  • In the base case, row n has an odd number of squares, and zero (an even number of squares) covered from the previous row.
  • In the inductive case, by induction row n-1 has an odd number of dominos extending down, which cover an odd number of row n's even number of squares (this is where we use the fact that this is not the last row).
  • In both cases there is an odd number of uncovered squares, an even number of which can be covered by horizontal dominos. The remaining odd number of squares must be covered by downward dominos.

  You are asking me to include two lines: the definition of S(n) and the "In the base case" line. Why does that make sense as a way to present an induction proof? Under what circumstances would including the induction statement and the proof of the base case make more sense than including only the induction statement, or including all cases? That's what I don't understand about your request. —David Eppstein (talk) 03:10, 15 September 2022 (UTC)

  I've put in the article an example of what I think is clearer. The issue is that the base case is, in my opinion, less obvious than the inductive step. That is the circumstance in which it would "make more sense". I wouldn't be opposed to spelling out the inductive step, either, in the pursuit of WP:ONEDOWN. Is my structure harder to understand, or perhaps too long, compared to the original? Anyway, I'd like to get a third opinion if this is that objectionable. Ovinus (talk) 06:50, 15 September 2022 (UTC)

  I guess I don't see any strong reason to object to your version. —David Eppstein (talk) 19:09, 15 September 2022 (UTC)

• Removing larger numbers of squares, with equal numbers of each color, can result in a region that has no domino tiling, but for which coloring-based impossibility proofs do not work. Example? Ovinus (talk) 19:41, 16 September 2022 (UTC)

  Added a figure. Easier than trying to explain in prose. —David Eppstein (talk) 21:25, 16 September 2022 (UTC)

• Hm. Is it possible to use bent arrows for the Hamiltonian cycle? The turns of the cycle are a bit unsightly. I'd rather not mess with {{Alice chess diagram}}, though, and the template doesn't seem to allow you to force Unicode characters in there. Ovinus (talk) 19:41, 16 September 2022 (UTC)

  Redrew as an illustration rather than trying to hack the diagram code to be more legible. —David Eppstein (talk) 21:26, 16 September 2022 (UTC)

• According to [1], the puzzle appears in Martin Gardner's My Best Mathematical and Logic Puzzles (1994). I don't have access, but if I did I'd put that as a reference somewhere or as "further reading", since he probably will give a nice explanation. Ovinus (talk) 20:02, 16 September 2022 (UTC)

  Is that different from the 1957 Mathematical Games column already linked as a reference? A lot of the Gardner books are basically just reprints of his columns. —David Eppstein (talk) 21:49, 16 September 2022 (UTC)

• I read two lecture slides on the puzzle and everything that isn't already in the article is probably superfluous. Generalizations probably belong in domino tiling or elsewhere (no action needed) Ovinus (talk) 20:02, 16 September 2022 (UTC)

Alright. That's probably it, once we discuss my remaining points, and I don't think I'll need a thorough second pass. Ovinus (talk) 20:02, 16 September 2022 (UTC)

• Just two more points which I've marked above with "Here" Ovinus (talk) 00:34, 17 September 2022 (UTC)
  • Cool, passing. Nice work, on an article that was once at AfD, no less. Ovinus (talk) 20:34, 17 September 2022 (UTC)

Did you know nomination

The following is an archived discussion of the DYK nomination of the article below. Please do not modify this page. Subsequent comments should be made on the appropriate discussion page (such as this nomination's talk page, the article's talk page or Wikipedia talk:Did you know), unless there is consensus to re-open the discussion at this page. No further edits should be made to this page.

The result was: promoted by Theleekycauldron (talk) 19:47, 18 October 2022 (UTC)

(

• Comment or view
• Article history

)

• ... that there is no way to cover a chessboard by dominoes, each covering two squares, leaving only two opposite corners uncovered? Source: Gardner, Martin (March 1957), "Some old and new versions of ticktacktoe, plus the answers to last month's puzzles", Mathematical Games, Scientific American, 196 (3): 160–168, https://www.jstor.org/stable/24941903, reprinted in My Best Mathematical and Logic Puzzles (Dover Publications, 1994), page 39: "It is impossible to cover the mutilated chessboard (with two opposite squares cut off) with 31 dominoes, and the proof is easy."
  • ALT1: ... that the mutilated chessboard problem, originally posed as an example of creative insight in human thought, has become a test case for automated reasoning? Source: Creative insight: Black, Max (1946), Critical Thinking: An Introduction To Logic And Scientific Method, Prentice Hall, p. 157, 433. Automated reasoning: Kerber, Manfred; Pollet, Martin (2005), "A tough nut for mathematical knowledge management", in Kohlhase, Michael (ed.), Mathematical Knowledge Management, 4th International Conference, MKM 2005, Bremen, Germany, July 15-17, 2005, Revised Selected Papers, Lecture Notes in Computer Science, vol. 3863, Springer, pp. 81–95, https://www.cs.bham.ac.uk/~mmk/papers/05-MKM.html
  • Reviewed: Template:Did you know nominations/This Census-Taker and Template:Did you know nominations/Reconstructing Womanhood (double QPQ to help reduce DYK reviewing backlog)

Improved to Good Article status by David Eppstein (talk). Self-nominated at 00:27, 19 September 2022 (UTC).

• Huh, interesting article! Why not make the hook shorter though:

• ALT2: ... that if you remove two opposite corners of a chessboard, you can't cover all squares with dominos?

ALT0 is more precise, but imo it's a little wordy. Again, an interesting article, got me thinking (and checking out other chessboard probelms)! –LordPeterII (talk) 19:08, 19 September 2022 (UTC)

Nicely reworded, much catchier. I think the extra precision of ALT0 is not needed in this context; ALT2 is not incorrect (just a little vague about what it means) and any vagueness is cleared up by following the link. Indeed, maybe being a little vague will encourage people to follow the link. I prefer ALT2 over ALT0. —David Eppstein (talk) 20:11, 19 September 2022 (UTC)

• Full review needed. Thanks. BlueMoonset (talk) 21:44, 15 October 2022 (UTC)

• Alright, this is a formal review: Good article, no apparent issues with content (Earwig's finds this, but it clearly states to be copied from Wikipedia). Just out of curiosity @David Eppstein, have you considered running with an image? Either File:Mutilated chessboard vectorized.svg or File:Mutilated chessboard problem example.jpg could be used. –LordPeterII (talk) 10:52, 16 October 2022 (UTC)

The mutilated chessboard

• I'd be happy to go with the vectorized one (pictured). I think the other one would not look good at thumbnail size. —David Eppstein (talk) 16:04, 16 October 2022 (UTC)

• I was just going to re-promote the hook as a rewording with the image, but I won't because of the issue raised on the DYK talk page despite rewordings not needing a new approval. So I will just approve it like this, although it does add extra unneeded time. SL93 (talk) 19:50, 16 October 2022 (UTC)