On Blockade

| 0 Comments

Recall that the Baron's game is comprised of taking turns to place dominoes on a six by six grid of squares with each domino covering a pair of squares. At no turn was a player allowed to place a domino such that it created an oddly-numbered region of empty squares and Sir R----- was to be victorious if, at the end of play, the lines running between the ranks and files of the board were each and every one straddled by at least one domino.

When the Baron described his game to me it immediately struck me that this game was a splendid example of the pigeonhole principle!
The pigeonhole principle states that if we have \(n\) pigeonholes and \(m\) pigeons and that \(m\) is strictly greater than \(n\) then at least one pigeonhole must house more than one pigeon.
That mathematicians have elected to give a specific, and admittedly rather whimsical, name to this most blatantly obvious of observations might suggest that they are somewhat slow witted fellows, but the truly remarkable fact is that it is astonishingly useful for analysing games of this ilk.
Indeed, I expressed as much to the Baron, but he seemed somewhat distracted and I was disinclined from pressing the issue.

Figure 1: A Losing Proposition
If the Baron were to enclose a single square at a corner of the board with his dominoes, such as in figure 1, then Sir R----- should most certainly decline the wager since it would trivially be impossible for him to completely cover it with his.
To determine whether Sir R----- should otherwise accept it, let us first assume that he should have placed all of the dominoes upon the board rather than allowing the Baron to place the first pair.

Now, to blockade the line between the first and second ranks, Sir R----- must place an even number of vertical dominoes upon the first rank, otherwise he should leave at least one uncovered square and should again not be able to cover the entire board. If he were to place no vertical dominoes then he would not have blockaded the line and would lose the wager, six and he could not blockade that between the second and third ranks and would again face defeat.
There would consequently be either two or four uncovered squares upon the second rank and, by the same reasoning, he should have straddled the line between it and the third with either two or four dominoes in the first case and two in the second.
By repetition, we are compelled to conclude that every line between the ranks must be blockaded by at least two dominoes and, by the argument of symmetry, that every line between the files must be done so by at least two placed horizontally.

Given that there are five lines running between the ranks and five more between the files he would therefore have had to have used at least twenty dominoes to blockade them all. But there is only room enough upon the board for eighteen and it is consequently impossible for Sir R----- to emerge victorious, even if he could have demanded that the Baron set his dominoes upon squares of his own choosing!

I should therefore certainly have advised Sir R----- to decline the wager!
\(\Box\)


Based upon an article I wrote for ACCU's CVu magazine.

Leave a comment

 
This site requires HTML5, CSS 2.1 and JavaScript 5 and has been tested with

Chrome Chrome 26+
Firefox Firefox 20+
Internet Explorer Internet Explorer 9+