These fields are all optional and need only be supplied if you would like a direct reply. Subject Your email address Your real name

You must answer this! If you don't, my spam filtering will ensure that I never see your email. What's 8 plus five (in digits only)?

Please make your changes here and then
Editing tips and layout rules.
File: TheMutilatedChessboardRevisited ''' <link rel="alternate" type="application/rss+xml" ''' href="/rss.xml" title="RSS Feed"> ********> width="25%" |>> ''' <a title="Subscribe to my feed" ''' rel="alternate" ''' href="https://www.solipsys.co.uk/rss.xml"> ''' <img style="border-width: 0px;" ''' src="https://www.feedburner.com/fb/images/pub/feed-icon32x32.png" ''' align="middle" ''' alt="" />Subscribe!</a> _ ''' <a href="https://twitter.com/ColinTheMathmo"> ''' <img src="https://www.solipsys.co.uk/new/images/TwitterButton.png" ''' title="By: TwitterButtons.net" ''' width="212" height="69" ''' alt="@ColinTheMathmo" ''' /></a> <<| ---- My latest posts can be found here: * ColinsBlog ---- Previous blog posts: * AMirrorCopied * TheOtherOtherRopeAroundTheEarth * PhotocopyAMirror * ThePointOfTheBanachTarskiTheorem * SieveOfEratosthenesInPython * FastPerrinTest * RussianPeasantMultiplication * FindingPerrinPseudoPrimes_Part2 * FindingPerrinPseudoPrimes_Part1 * TheUnwiseUpdate * MilesPerGallon * TrackingAnItemOnHackerNews * HackerNewsUserAges * PokingTheDustyCorners * ThereIsNoTimeForThis * PublicallySharingLinks * LearningTimesTables * GracefulDegradation * DiagrammingMathsTopics * OnTheRack * SquareRootByLongDivision * BeyondTheBoundary * FillInTheGaps * SoftwareChecklist * NASASpaceCrews * TheBirthdayParadox * TheTrapeziumConundrum * RevisitingTheAnt * TheAntAndTheRubberBand * IrrationalsExist * MultipleChoiceProbabilityPuzzle * RandomEratosthenes * WrappingUpSquareDissection * DissectingASquarePart2 * DissectingACircle * DissectingASquare * AnOddityInTennis * DecisionTreeForTennis * DecisionTreesInGames * AMatterOfConvention * DoYouNourishOrTarnish * BinarySearchReconsidered * TwoEqualsFour * TheLostPropertyOffice * TheForgivingUserInterface * SettingUpRSS * WithdrawingFromHackerNews ---- Additionally, some earlier writings: * RandomWritings. * ColinsBlog2010 * ColinsBlog2009 * ColinsBlog2008 * ColinsBlog2007 * ColinsBlogBefore2007 ''' <img src="/cgi-bin/CountHits.py?MutilatedChessboardRevisited" alt="" /> ******** [[[> If you like this, _ you might want to visit _ http://www.mathsjam.com ]]] Puzzle enthusiasts know that a really good puzzle is more than just a problem to solve. The very best problems and puzzles can provide insights that go beyond the original setting. Sometimes even classic puzzles can turn up something new and interesting. Some time ago I happened across one of these classics, the problem of TheMutilatedChessboard, and was surprised to learn something new from it. Check the above link for the classic. So here are the extra questions: * What happens when you cut out /*two*/ squares of each colour? * What happens when you cut out /*three*/ squares of each colour? * When can we know it's /*definitely*/ possible, * ... or definitely /*impossible*/ ? In all cases we assume the remaining squares are connected. !!! The Classic - a recap ... If we mutilate the chessboard by removing one corner square (or any single square, for that matter) then it's clearly impossible to cover it exactly, because now it would take 31.5 dominos. If you cut off two /*adjacent*/ corners then it's still coverable, and pretty much the first attempt will succeed. The classic problem then shows that when two /*opposite*/ corners are removed, it's no longer possible, simply because each domino must cover exactly one black and one white, and the two squares we've removed are the same colour. As we cover pairs of squares, we must cover the same number of blacks as whites. If the number of blacks and whites is unequal, it can't be done. A wonderful example of being able to show something is impossible, without having to examine all possible arrangements. !!! The Extra Questions ... !! Removing one square of each colour ... Clearly in order to cover the mutilated board it's necessary that there be the same number of blacks as whites. Is this sufficient? ********> width="40%" Let's start with the simple cases. If you remove any single black and single white and try to cover the remainder it seems always to be possible. Indeed, in 1973 mathematician Ralph E. Gomory showed with a beautifully simple and elegant argument that it is always possible to cover the board if just one black and one white square are removed. So that's a good start. ******** width="5%" ******** width="55%" [[[ *Proof:* Consider a closed tour that visits every square exactly once and returns to its starting point. Removing one square of each colour cuts the path into two pieces (one possibly being of zero length) and some thought shows that each piece is of even length (To see why, consider start and end colour). So each section can be covered, and we're done. ]]] ********< !! Removing two squares of each colour ... What about if two whites and two blacks are removed? Clearly if one corner gets detached by the process then it's no longer coverable, but let's suppose the chessboard remains connected. Can it always be covered? Yes it can, although I'll leave the details to the interested reader. I've yet to find a truly elegant argument (and would be interested in seeing one. Please.) !! Removing three squares of each colour ... And so we continue. What if three whites and three blacks are removed (still leaving the board connected.) Can it then /*always*/ be covered? No. [[[>50 Challenge: find an example of a chess board with three whites and three blacks removed, still connected, but can't be covered. There is a hint later [X] ]]] Oh. Well, that was quick. So consider. Clearly it's necessary that the number of blacks is the same as the number of whites, but equally clearly it's not sufficient. So what condition is both necessary and sufficient? Specifically: * Given a chess board with some squares removed _ (but still connected!), can we show that it's _ not possible to cover it with dominoes, without _ having to try every possible arrangement? Before we look at the answer to that, let's consider the dating game. !! Diversion - the dating game ... Suppose we have a collection of men and a collection of women, and each woman is acquainted with some of the men. Our challenge is to marry them all off so that each woman is only married to a man she knows. Under what circumstances is this possible? In another formulation, suppose we have a collection of food critics. Naturally enough, they all hate each other, and refuse to be in the same room as each other. Also unsurprisingly, each has restaurants that they won't ever eat at again. Is it possible for them all to eat at a restaurant they find acceptable, but without having to meet each other? These are "Matching" problems - we want to match each item in one collection to an item in the other. In one case we are matching women with suitable men, in another we are matching critics to restaurants. So when can we do this? Let's consider the restaurant critic problem. If we successfully create such an arrangement then we know that every critic must be happy with at least one restaurant, namely, the one where they eat. If some critic is unhappy with *all* of the restaurants, then clearly it's impossible. But we can go further. If a dining plan is possible, then any collection of, say, */k/* critics will collectively be happy with the restaurants where they are dining. So to get a matching, any (sub-)collection of */k/* critics must between them be happy with at least */k/* restaurants, otherwise it's impossible. [[[>50 The result was originally stated and proved as a lemma by Phillip Hall in the process of proving a significant result in algebra. Later, Marshall Hall Jr. (no relation) realised that the result could be generalised, and produced a paper in which he extended and enhanced the result, but he named it "Hall's Marriage Theorem" after Phillip Hall, thus forever producing confusion for all. ]]] The surprising result is that this condition is sufficient. The proof isn't difficult, proceeding by induction in a fairly straight-forward manner (although undergrads do seem to find it intricate and tricky, but that's probably just insufficient familiarity with the techniques) and we won't take the time here to go through it. !! Back to the chess board ... So how does this solve our problem with the mutilated chess board? A covering of dominoes matches each white square with a black square, so we have two collections that we are trying to match. If some collection of white squares collectively are not attached to enough black squares, a covering is impossible. Therefore: * To show that a mutilated chess board is coverable - cover it. * To show that it is not coverable, demonstrate a collection of black squares which are collectively attached to insufficiently many white squares. * ( or /vice/versa/ ) We can now use this result to create a minimal, connected, uncoverable set of squares. Here's how. [[[> https://www.solipsys.co.uk/images/TwoBlackOneWhite1.png _ ---- |>> Two black and one white <<| ]]] To be uncoverable we must have a collection of black squares that collectively are connected to insufficiently many white squares. If we used just one black square then it would have to be connected to no squares at all, and so it would be disconnected, so we must use at least two black squares. They must then be attached to just one white square. Now we need at least one more white square to balance the numbers, but that can't be connected to either of the black squares we already have. That means we need another black square. We now have a white square with three black neighbours, and so we need /*two*/ more white squares to balance the numbers. These must only be attached to one of the black squares, and there's only one way to do that. And we're done! By construction, we have a provably minimal uncoverable configuration. If you like you can see how every possible configuration of four can be covered, and every other configuration of six can also be covered. This is the unique shape. It also lets us answer the question above about the mutilated chessboard with three of each colour missing. That's a hint for the puzzle [X] above. And no, I've not included a picture of the final configuration - that's for you to work on! ---- !!! A surprise application ... And so finally to a surprise application. Take a deck of cards, shuffle (or not) as you will, then deal out 13 piles of 4 cards each. Some pile will have an ace, possibly more than one. Some pile will have at least one deuce, and so on. But here's an interesting thing. No matter how you shuffle, or how you deal, it will be possible to draw a full straight - ace through king - taking just one card from each pile. So remove those cards to leave thirteen piles of three. Now we can do it all a second time. And a third time. And now we have just thirteen cards left, one of each rank, so we can do it a fourth and final time. Alternatively, deal the cards into four piles of thirteen. It won't surprise you that it's possible to draw a card of each suit, one from each pile. What may surprise you is that you can do it again, and again, and again, and so on, right through to the end. It's not that hard to accomplish these feats, a bit of fiddling will find a solution, but it is interesting that it's always possible. It seems plausible that some sort of magic trick could be devised that uses this principle, although I really don't see how. Maybe it can't, but I'd be fascinated to see one. So that's a challenge - show that it's always possible to make such selections. I'll give you a hint. It uses Hall's Theorem. ---- !! References: * MartinGardner (1994), * My Best Mathematical and Logic Puzzles, * Dover, ISBN 0-486-28152-3 * Hall's Marriage Theorem * https://en.wikipedia.org/wiki/Hall's_marriage_theorem ---- |>> | |>> <<<< Prev <<<< ---- AMirrorCopied <<| | : | |>> >>>> Next >>>> ---- BeCarefulWhatYouSay ... <<| | ---- ********> ''' <a href="https://twitter.com/ColinTheMathmo">You should follow me on twitter</a> ******** ''' <a href="https://twitter.com/ColinTheMathmo"> ''' <img src="https://www.solipsys.co.uk/new/images/TwitterButton.png" ''' title="By: TwitterButtons.net" ''' width="212" height="69" ''' alt="@ColinTheMathmo" ''' /></a> ********< <<| ---- !! Comments I've decided no longer to include comments directly via the Disqus (or any other) system. Instead, I'd be more than delighted to get emails from people who wish to make comments or engage in discussion. Comments will then be integrated into the page as and when they are appropriate. If the number of emails/comments gets too large to handle then I might return to a semi-automated system. That's looking increasingly unlikely. ********<