8 February 1992
"Business," said Rockchopper Rocknuttersson, "is bad."
"You can say that again," said his apprentice, Pnerd.
"Business is bad." The President of the Obelisker's Guild tended to take everything literally. "If we don't get a commission soon, I'll have to hang up my chisel and take that job herding pigs that my uncle Hogthumper Hogtrottersson keeps trying to offer me."
Pnerd chipped idly at a child's toy dolmen. "It's the recession, Rocky. Nobody's buying. The market in stone circles has hit rock bottom. And as for longbarrows... you can't even sell a wheelbarrow at the moment. I heard Moloch Molochsson complaining the other day because the tithes are down again and the priests can barely afford to buy enough rams to placate M'gaskil the snow-god before Winter comes."
Rocky scratched his ample nose, flexing his huge biceps. "Did you pick up that copy of Rolling Stone that I asked you to buy?" Pnerd dropped a large round slab of limestone at his feet. Rocknuttersson picked it up and pored over the chiselled inscriptions. "There may be something in the small ads. Mmmm... assistant newt-trainer... the Bogtown chief vermin inspector has retired... seven virgins wanted for unspecified purposes, must be willing to travel... Ah! Invitation to tender for repairs to the marketplace in Quagville! Pnerd, get over there and find out what they want done, while I check the thongs on the dressing-mallets."
Two days later, Pnerd returned.
"Well?"
"Quagville marketplace is paved with big stone slabs, Rocky. Sixty-four of 'em, each one about ten feet square, arranged in an eight by eight grid. The original stone is starting to crack. They want the whole lot ripped out and relaid."
"Brilliant!"
"Wait, there are some conditions. The main one is, they don't want it relaid in squares this time. The town priests reckon that's what caused the stone to crack."
"Rubbish! Typical priests, always worried about shapes and numbers and soft intellectual numerosophist trash... I know exactly what happened. When Chalkhacker Chalkwhackersson laid those slabs, he used inferior quality stone, and the frost got in."
"The priests say they cracked because a square is the symbol of Frozo the frost-demon."
Rocky looked up in surprise. "Is it? I thought it was the sigil of Gnashfang the cave ogre."
"It is," admitted Pnerd. "But there aren't that many symbols to go round, you know. The square is kind of popular. Gnashfang shares it with Frozo; he gets to use it on alternate weekdays."
"Oh." Rocky thought for a few moments. "Maybe the priests are right, then."
"Depends whether the frost comes on a Tuesday or not. But right or not, you don't argue with priests. Not if you want to keep your kidneys. Square slabs are out. They want dominoes."
Rocknuttersson stared at him as one might at something slimy that has crawled from under a rock. "Pnerd, what in the name of the Great Boggie is a domino?"
"Two squares stuck together, Rocky."
"Then why not say so? Why not make it clear that they want tweentwines? Why use a silly name like 'domino'?"
"Dom'd if I know," said Pnerd. He smiled briefly, and dodged the kick that Rocky aimed at him. Then his face fell. "Could be a problem, Rocky. Maybe dominoes won't fit."
"Of course they'll fit! All you have to do is place one of them where two of the old squares used to go!"
Pnerd frowned. "Yes, but that only works if the total number of squares is even. Each domino covers two squares. If you started with an odd number, there'd be one square left over at the end."
Rocky sighed. "Pnerd, you said there were sixty-four squares! That is even!"
"Is it?"
"Provided the slabs were laid horizontally, yes, the entire marketplace must be even."
"Oh. Right. I guess I should have mentioned the statues of Gog and Magog."
Rocknuttersson leaped to his feet in anger. "Statues? What statues?"
"Seems that when the first slab cracked up, the priests tried to cover it up by installing a statue of Gog instead. Soon after, another slab cracked, so they put in a matching statue of Magog. Each one has a base just the same size and shape and one of the square slabs. So it's not sixty-four squares any more, it's --- um..."
"Sixty-two."
"Right, yeah. Um --- is that an even number?"
Rocky began counting on his fingers, but they ran out before he got far enough. "To be quite honest, Pnerd, I have no idea."
"Well, you'd better be certain before we chisel our namesigns into any binding legal agreements, Rocky. There's penalty clauses." He waited for twenty minutes while Rocknuttersson cursed whichever son of a dog had invented penalty clauses in local government contracts, learning seventy-three new swear words in the process. "Ten years in the sulphur mines if the new slabs don't fit," he added by way of explanation. The curses renewed. Eventually Rocknuttersson stopped to draw breath, and Pnerd grabbed his chance. "Rocky, we can't work this out on our own. We need an expert."
"Who do you have in mind?"
"Snitchswisher!"
"May the gods preserve you against possession by demons."
"No, I didn't sneeze, you idiot! Snitchswisher Wishsnitchersdorter!"
"There, you've done it ag--- oh, her! Your numerosophist friend who lives in Dead Cat Swamp." Pnerd nodded. "Smart thinking, apprentice: we definitely need an expert. We are out of our depth on these matters."
Snitchswisher Wishsnitchersdorter was sewing new moletail trimmings on her tunic when they arrived. Rocky explained their problem, and she gave a sardonic laugh. "Good job you came to me. There are aspects of the matter that would not be apparent to lay persons, and you might have got yourselves into serious trouble. To begin with, although sixty-two is indeed and even number --- " she paused while Rocky and Pnerd argued over who had first conjectured this to be true, and who had claimed the opposite --- "it is not enough for the number of squares to be even."
"It's not?"
"No. There is a more subtle question of parity. It is an old numerosophical chestnut. For example, suppose that two opposite corners of the square are removed (Fig.1a). Is it possible to cover the remaining sixty-two squares with dominoes?"
1 (a) An 8x8 grid with opposite corners removed. Can it be covered by 31 dominoes? (b) If the grid is coloured like a checkerboard, there are 32 black squares and 30 white. But each domino must cover one of each. Therefore two black squares must remain uncovered.
"Beats me," said Rocky.
"Should be," said Pnerd. "There's lots of room to try different arrangements, and there can't be one left over."
Snitchswisher rummaged in a corner of the hut, and found a board marked off into a grid of sixty-four squares, and a box of wooden rectangles, each just large enough to cover two adjacent squares. She placed a pebble on the two opposite corners. "Try it."
Pnerd began playing with the squares. Rocknuttersson sidled up closer to Snitchswisher and asked what the board and wooden pieces were for. "I had an idea for a game," she said. "The board represents a river, and you have to use the wooden pieces to build a kind of arch thing over it, without it collapsing. I was going to call it 'bridge'."
"Never catch on, not with a name like that," said Rocky.
Pnerd thumped the table in frustration. "They won't fit! I've tried a dozen times but they won't fit!"
Snitchswisher Wishsnitchersdorter smiled. "And they never will, Pnerd. Let me draw your attention to the different colours of the squares (Fig.1b)."
"That's a pretty pattern."
"Yes, I call it 'check'."
"Why?"
"Because when you draw it you have to be careful to check you haven't made a mistake. I did the black squares with charcoal and the white with extract of arrowroot steeped in deadly nightshade."
"Why not use chalk?"
"That's a brilliant idea, Pnerd! It's never occurred to me that you can use chalk to write with. Imagine, writing with a rock instead of a burnt stick! Anyway, if you think about placing a domino on the board, you'll see that it must always cover one black square and one white. Because no two black squares are adjacent, and the same is true of the white ones. Pnerd: how many white squares are there --- no counting the two corners?"
Pnerd counted laboriously. "Thirty."
"Right. And how many black?"
"Um... Thirty-two."
"Precisely. Since any domino covers one of each, at least two black squares must remain uncovered. You're right that you won't have just one square left over. But that doesn't rule out having two left over! It's a general parity principle for dominoes: as well as the total number being even, you also have to have equal numbers of black and white squares."
"That," declared Rocknuttersson, "is absolutely brilliant, Snitchswisher. Except," he added, "that the squares in Quagville market are all the same colour." He gave her a withering look. "Typical ruddy theorist, no practical sense at all."
"But," said Snitchswisher, "you can always imagine the squares are coloured, and the same argument applies." Rocknuttersson thought about this for a few minutes, and then turned bright red. To cover his embarassment, he dispatched Pnerd back to Quagville to check that the statues of Gog and Magog had not been placed on squares that, if you imagined the marketplace coloured in a black-and-white check, had the same colour.
Two more days passed, during which time Rocky helped Snitchswisher Wishsnitchersdorter make enough bognettle soup to carry her and her aged father through the coming Winter. Then Pnerd reappeared.
"Bog, that was boring. I wrote a poem along the way to amuse myself, Snitchswisher. Would you like to hear it? It's about a fearsome creature of the forest."
"Proceed."
Pnerd drew in a breath and poked his skinny chest out. "Rabbit, rabbit! Burning bright, in the woodlands of the night. What immortal hand or eye---"
"Could turn you into rabbit pie," said Rocky. "Stop wasting time, Pnerd, and report on the placement of the statues."
"We're in business, Rocky! One statue is on a white square, one on a black one!"
"Which?"
"Eh?"
"Is Gog on black, or white?"
"Crumbs, Rocky ---"
"Look, it could be important, Pnerd. The priests of Gog wear black cloaks, whereas those of Magog wear ---"
"Oh. Look, they were only imaginary colours anyway, Rocky, I could always change them roun---"
Rocky suddenly shook his head. "It's not that easy, Pnerd. I've just realised that the priest of Magog wear black hats, whereas those of Gog ---"
"For Bog's sake," yelled Snitchswisher. "Who cares?" She grabbed Pnerd by the shoulder. "You don't happen to recall just where the two statues were, do you?"
"Nope."
"Oh, heck."
"Does it matter?" asked Rocky.
"I'm not sure. It might. Should we send Pnerd back to --- no, that'll take days."
"Two days," said Pnerd. "And I'm fed up flogging it to Quagville market, anyway."
Snitchswisher looked thougthful. "You know, maybe it doesn't matter," she said. "But you'd have to try an awful lot of possibilities to be sure. I think it's time we consulted my father."
"Her dad's a thaumaturge," Pnerd reminded Rocky. "Gets in touch with spirits, that sort of thing." Rocky seemed skeptical, possibly because he always ended up out of pocket when thaumaturgy was involved, but Snitchswisher trotted off through the bog to fetch him. Soon she and the old man --- Wishsnitcher Dishpitchersson by name --- reappeared. Suitably primed with silver from Rocknuttersson's purse, he fished some Tarot cards from his robes and began a divination.
"Below... the Moon. Above... the Leaping Cow. To west and east..."
"The Cat and the Fiddle," suggested Rocky.
"Yes, but the Cat is inverted, signifying drunkenness... Below, the Laughing Hound---"
"Signifying that these entire proceedings are a farce---"
"Signifying merriment. More cards... the Dish, the Spoon---"
"And the Knife and Fork."
"No... the deuce of Forks." The old man shook his head. "Which is strange, since there are no forks in the pack... Ah! A name... A spirit from the future... an acolyte of 'Big Blue', whatever mystic being that may be... Ralph... Ralph..."
"That's the hound. They always go 'Ralph! Ralph!' But it's called 'barking', not 'laughing'."
"No, it is a name... Ralph... er... Grimoire? Grimory? No --- Ralph Gomory, a future numerosophist of great ingenuity... A three-tined fork and a four-tined fork, a sigil of enormous power and beauty. Quick, the charcoal!" The old man drew swift lines on the board. (Fig.2) Then his trance faded.
2 Gomory's sigil creates a chain that can be filled by consecutive dominoes.
Rocknuttersson sourly handed over a further piece of silver. "I reckon your dad's a few stones short of a henge, Snitchswisher."
She sniffed and studied the charcoal lines. "I am not so sure, Rockchopper Rocknuttersson. Imagine the two forks are walls. Then a line of dominoes may be placed between them, in an endless loop. If two squares are occupied by statues, the loop is cut into two sections. Possibly just one if the squares are adjacent. If the statues are on squares of the opposite colour, then each section contains an even number of squares, so the chain of dominoes can fill it completely. The diagram represents a proof that no matter which two squares are occupied by statues --- provided only that they are of opposite colour --- the remainder can be covered by dominoes. Indeed it is a constructive proof, showing exactly how to achieve such a result in any given case." (Fig.3).
3 How to fill in the dominoes if the two omitted squares are of opposite colours.
Rocky was impressed. "Snitchswisher, I apologise to your father for my scepticism. He has uncovered a remarkable truth." The old man muttered something about 'fine words', 'butter', and 'no parsnips', and Rocky handed over another piece of silver to avoid further embarrassment. "Pnerd! Fetch my scribing-chisel, and the finest slab that is portable! We shall head the document "TENDER FOR RENOVATION OF QUAGVILLE MARKETPLACE, ROCKCHOPPER ROCKNUTTERSSON ROCK RENOVATORS, MURKLE MIRE."
"OK," said Pnerd. "Oops, I never told you about the two new statues, did I?"
Rocky stared at him. "Two... new..."
"Demagog and Wolligog. The priests decided to cover up some more cracks."
"Oh my Gog," said Rocky.
"They are on squares of different colours," said Pnerd helpfully. "Two statues on black squares, two on white."
"You don't happen to remember exactly wh--- no, of course you don't. Snitchswisher: does the sigil of Gomory work when there are four missing squares, two of each colour?"
Snitchswisher Wishsnitchersdorter's brow furrowed. "It does if the order in which the squares appear as one passes round the loop of dominoes is alternately black and white," she said. "But if black is followed by black, then the number of intervening squares is odd, and the proof breaks down."
"And could that happen?"
"I don't see why not. It's all rather confusing."
"You're right about that." There was a lengthy pause. Rocky started to say something, was interrupted.
"No, quiet! I'm getting an idea... Yes, of course. Cut the board into two pieces, such that each contains just one missing square of each colour. Do this so that each piece can be covered by an endless loop of dominoes, like Gomory's sigil but of whatever shape suffices. Then use the same argument to prove that each piece can be covered."
"Are there such sigil-bearing pieces?"
She thought for a moment. "Many. I shall draw some." (See Fig.4). "Hmmm... I haven't time to enter into every detail; but I'm pretty sure you can show that the only occasions on which the board cannot be so divided are when either the two black squares omitted, or the two white squares, are in the same corner. (See Fig.5). In one arrangement, it is obvious that the corner square is isolated from all the rest, and no solution can be found. In the other case... the board can again be divided into two regions, each containing just one omitted square of each colour, and each possessing a Gomory sigil of its own. (Fig.6). One region has to have a hole in it, but that doesn't alter the argument. I believe that a careful analysis will show that it is always possible to cover the board with dominoes, except when a corner configuration such as in Fig.5 occurs, for one or other colour." She shrugged. "It is not as elegant a proof as Gomory's however. Perhaps some future numerosophist can do better."
4 Some sigil-bearing regions.
5 Four problematic corner arrangements. C and D block the placement of a domino to cover the corner square, but A and B are harmless.
6 An example of how to handle case A of Fig.5. Each sigil-bearing region contains precisely one omitted square of each colour.
"Anyway," said Rocky, "it sounds as if we're probably in business." He leaped to his feet. "What we need is somebody to go and check that the statues haven't cut off one of the corner squares. To be on the safe side, Pnerd, this time you can also make a map of the positions of the statues, so that we know exactly what we're up against. Then we can use Snitchswisher's wooden pieces to find a solution before putting in our bid to tender."
Pnerd groaned. "Crumbs, why me? I've been twice already and it's a two-day walk every ---"
"You, Pnerd, are the apprentice. I am President of the Obelisker's Guild."
"Oh, right. I'll get started then." He borrowed a few strips of candied goat to eat on the journey, and headed for the door.
"Oh, and Pnerd?"
"Yes, Rocky?"
"It would be nice if you could get back before the priests put up any more statues."
FURTHER READING
Martin Gardner, Mathematical Puzzles and Diversions from Scientific American, Bell, London 1961.
Russ Honsberger, Mathematical Gems I, Dolciani Mathematical Expositions No. 1, Mathematical Association of America, 1973.
Maurice Kraitchik, Mathematical Recreations, Allen and Unwin, London 1943.