I want to ask about CheckerBoard Problem, which
Prof.McCarthy presented at QED-II,
As I understand, Prof.McCarthy intended to use the problem
simply as an example of containing "obvious" reasoning, so
I'm afraid what I want to ask is a digression.
Here is the theorem and the proof.
(omitting the definitions...)
Theorem:
not exist Z s.t. ( partial-covering(Z) and mutilated-board = Union(Z) )
Proof(briefly):
We define a function COLOR(X) for each X in Board,
COLOR(X) := 0 if the addition of the coordinates of X is even,
1 if the addition of the coordinates of X is odd.
If X is a domino on board, then X contains two partitions U and V s.t.
the color of U is 0 and the color of V is 1.
If Z is a partial covering of the board, then
the number of partitions with color 0 and
the number of partitions with color 1 are the same.
>From the definition of the board,
the number of partitions with color 0 and
the number of partitions with color 1 are different.
(actually, there are two more color 1 partitions.)
Hence contradiction.
q.e.d.
In the proof above, color function is defined for partitions of the board.
But the theorem says "there is no ways to put domino on the board
in such way ..."
I don't understand why the color is defined without
mentioning to the domino as above.
A color of each partition of the board should be defined
from the domino which is on?
I heard CheckerBoard problem for the first time at QED-II.
If there are any literature about this, let me know.
BTW, I try another proof for Z4 x Z4.
Alternative Proof Trial:
With the covering we must cover a partition (0,0).
To cover it a domino "should be" put as {(0,0),(1,0)} or {(0,0),(0,1)}.
In the following we show we cannot put a domino in either way.
0 1 2 3
0 o o o x
1 o o o o
2 o o o o
3 x o o o
Assume we put a domino {(0,0),(1,0)}.
Then we must put another {(2,0),(2,1)} to cover a partition (2,0).
Continuing the same reasoning we put
{(0,0),(1,0)}, {(2,0),(2,1)},{(3,1),(3,2)},{(3,3),(2,3)},{(1,3),(1,2)}.
Now it's clear we cannot cover a partition (2,2).
With the similar reasoning, we cannot put a domino {(0,0),(0,1)}.
Consequently (0,0) cannot be covered.
q.e.d.
I don't know if this argument can be extended to Z8 x Z8.
- -- yozo.