Chronology Current Month Current Thread Current Date
[Year List] [Month List (current year)] [Date Index] [Thread Index] [Thread Prev] [Thread Next] [Date Prev] [Date Next]

Re: dominos on a chessboard-advanced version (was Re: multi-step reasoning)

Let's make the problem more interesting, then.
Definition: A covering is a 2-dimensional arrangement of the dominos on
the chessboard, and is identified by the locations of the two empty
spaces. That is, different orientations of dominos with the same two
empty spaces are to be regarded as identical.
Problem: How many possible coverings are there?
Hints:(1) The two vacant spaces must be of different colors.
(2) The construction to which Chuck is responding tells you how to
identify impossible coverings.
(3) The number of possible coverings is less than 1024.

On Sat, 24 Aug 2002, Chuck Britton wrote:

note that each domino MUST cover exactly one BLACK square and one RED square.
(I would have great trouble proving this assertion from basic
axioms etc! 8-)

The number of red squares = the number of black squares as an initial condition
and also for each step of the 'coverage process'.

The desired outcome of only the two diagonally opposing squares
remaining uncovered violates the 'equal number' result and is
therefore impossible.

This argument covers all even x even square checkerboards.
Odd x odd boards are even easier. The initial number of squares is
ODD and each successive stage of the process will have an ODD number
of squares remaining. Therefore the 'even' outcome is impossible)



At 6:46 PM -0500 on 8/24/02, Jack Uretsky wrote
In 2 dimensions, it is easy to show that the answer is no. I use
the pigeon-hole principle for the proof. Consider the two opposed corners
where there is no vacancy. Each 4x4 corner is filled by 8 dominos, and
the inner corners touch, so the remaining vacancies are in two bounded 4x4
sections, with 15 dominos remaining. The two vacant sections must be
filled symmetrically, since no domino can intersect both sections. This
is impossible with an odd number of dominos.
Going to 3 dimensions and the possibility of inserting a domino
edgewise, or some such trick, the answer would be different.
Regards,
Jack
On Tue, 20 Aug 2002, John S. Denker wrote:

> You are given a supply of 31 ordinary dominos. You are also
given a checkerboard with the ordinary arrangement of colored
squares, of a size-scale such that each domino just covers
two squares. Can you arrange the dominos so that all squares
are covered except for the two squares at the opposite ends
of the main NW/SE diagonal?

This seems like a pure math/logic puzzle, but there's something
> akin to a physics principle hiding in there. Hint, hint.



--
"But as much as I love and respect you, I will beat you and I will kill
you, because that is what I must do. Tonight it is only you and me, fish.
It is your strength against my intelligence. It is a veritable potpourri
of metaphor, every nuance of which is fraught with meaning."
Greg Nagan from "The Old Man and the Sea" in
<The 5-MINUTE ILIAD and Other Classics>