The Mutilated Chess Board
|
AllPages RecentChanges Links to this page Edit this page Search Entry portal |
|
|
|
The Mutilated Chess Board |
|
||||
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 the Mutilated Chessboard, and was surprised to learn something new from it. That's what I want to share with you here. The way I present it here is slightly unusual - bear with me for a moment.
|
If we multilate 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 now take 31.5 dominos.
Something not often mentioned is that cutting off two adjacent corners leaves the remaining squares coverable, and it takes 31 dominos. It's not hard - pretty much the first attempt will succeed.
|
|
Why is this important? The reason is simple. 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. It's a wonderful example of being able to show that something is impossible, without having to examine all possible arrangements.
And that's where the discussion usually stops. Some people look for generalisations in different ways, and that has led to some interesting extensions of the ideas, but again, that's not where I'm going. Clearly in order to cover the mutilated board it's necessary that there be the same number of blacks as whites. Is this sufficient?
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.
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.)
And so we continue. What if three whites and three blacks are removed (still leaving the board connected.) Can it then always be covered?
|
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 that this is a paper for G4G it won't surprise you that the answer is yes. It's an elegant and slightly surprising result concerning matchings between collections, and goes by the name of "Hall's Theorem," or sometimes "Hall's Marriage Theorem." I'll explain it briefly here, and then show an unexpected application. [Z]
The original setting is this. 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 marriage problem. If we do successfully create such an arrangement then we know that every woman must know at least one man, namely, her husband. If some women is acquainted with none of the men, then clearaly it's impossible. But we can go further. If a matching is possible, then any collection of, say, k women will collectively know their husbands (and possibly more). So to get a matching, any (sub-)collection of k women must between them know at least k men, otherwise it's impossible.
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.
So how does this solve our problem with the multilated chess board?
A covering of dominos 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:
We can now use this result to create a minimal, connected, uncoverable set of squares. Here's how.
To be uncoverable we must have a collection of black squares that collectively are connected to insuffciently 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 so finally to the surprise application I mentioned above [Z].
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.
|
