 Subscribe!
My latest posts can be found here: Previous blog posts:
Additionally, some earlier writings: |
Some time ago I happened across one of these classics, the problem of The Mutilated Chessboard, and was surprised to learn something new from it. Check the above link for the classic. So here are the extra questions:
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?
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.
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:
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.
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:
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:
CommentsI'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.
|
Suggest a change ( <--
What does this mean?) /
Send me email
