I think that was a projective plane. I sh'd've identified d ----- c| |e b | | f g ----------------------- a| | | | |a | | | | | ----------------------- b c | | g d| |f ----- e R. On Tue, 19 Nov 2002, Richard Guy wrote:

On Tue, 19 Nov 2002 asimovd@aol.com wrote:

...

Clearly any portion of a checkered board that can be covered by dominoes must have an equal number of squares of each color, but does the converse hold? d No! --- bc| | --------------- a| | | | |a --------------- | |cb --- R. d (Does identifiying opposite edges of the board to make a torus affect the answer?)

You said `any portion of'. If the portion is rectangular, then th answer is trivial, torus or otherwise. In the above board, if you identify a b c d ... you can tile the result. Is it a torus?? R.

...

AND: Would someone please recall for me a problem that was posted here several months ago, but never answered, regarding properties of some kind of balanced two-color designs on a 4x4 square.

Was this (something to do with) Barry Cipra's Sol LeWitt puzzle? P127 in The Inquisitive Problem Solver. R.

...

--Dan

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

Let me fill in / correct a little from Conway's message. There are good methods to tell if a region can be filled in with dominoes, or lozenges, but it's slightly more than this: On Wed, Nov 27, 2002 at 02:50:05PM -0500, John Conway wrote: ...

I recall Bill Thurston's showing me an exact characterization of the regions that CAN be filled by dominos, in terms of some property of the boundary curve.

It's easier for fillability by rhombs in the "cubix" pattern, in which "the move" replaces __ __ /\_\ by /_/\ \/_/ \_\/

There, the condition is that if you regard the boundary path as 3-dimensional, then it still closes. The solution in the domino case is essentially the same, but I've forgotten the details.

The three-dimensional pattern that explains a lot about dominoes is this: you replace each black square in an infinite checkerboard with an right-handed infinite square helix. This has the effect of replacing each white square with a left-handed square helix. It's like an infinite parking garage, where going counterclockwise around the boundary of any black square takes you up a level, but going counterclockwise around a white square takes you down a level. Going around any two adjacent squares (the boundary of a domino) brings you back to where you are. If the pitch of the spirals is chosen just right, This infinite graph is the same as the structure of a diamond crystal, with stacks of carbon atoms above each vertex in the checkerboard, each linked to 4 neighbors. Any *simply-connected* region in the plane that can be tiled by dominoes lifts to the parking garage, so its boundary curve has to close. This in itself doesn't actually give much new information: it's equivalent to saying the curve encloses the same number of black as white squares, i.e. you're spiraling up as much as you're spiraling down. This is necessary, but not sufficient, to be fillable by dominoes. If you assign integer coordinates to the vertices of the 3-d graph so that each directed edge with a black helix to its left goes up by 1, then a domino tiling gives a function on the vertices of the region in the plane such that each directed edge with black on its left either goes up by 1 (if it's on the edge of a domino) or down by 3 (if it cuts across a domino. Conversely, such a height function gives a domino tiling. Given any two valid height functions, their sup and their inf is also a valid height function. Thus one quick algorithm to find a domino tiling, if it exists, is to first jot down the values of the height function on the boundary of the region, then try to construct the greatest height function in the region satisfying the above condition. You just start with the lowest values, use these to bound the values of their neighbors, and proceed upward. It's very easy (especially if you're a computer) once you get the hang of it. ============ A necessary and sufficient condition, whether simply-connected or not, which is a special case of the "marriage" problem of matching in a bipartite graph: a region can be filled by dominoes if and only if a. it has an equal number of black and white squares, and b. for any "fence" i.e. union of directed arcs that cuts the region in two, where the fence has black squares on the left and white squares on the right, the imbalance black-white on the left region is not greater than the total number of dominoes that can straddle the fence, i.e. the lesser of black squares on its left or white squares on its right. =========== The height-function method can also be generalized to the non-simply connected setting---you can think of it either as a multi-valued function, or in modern terms, namely a 1-cocycle (the coboundary of a multi-valued function). But I haven't worked through how well this applies to the original question of a nXn checkerboard with a small number of squares removed. Bill Bill