15 May 10
Originally posted by afxI think rather an inductive method will solve the problem.
There must be a simpler way to prove that like in "chess and domino"
where simple coloring does the thing.
But I have not found it yet
Start with the trivial case, a chess board with 2x2 squares and prove it.
Then show that when if nxn chess board does the trick, then (n+2)x(n+2) also does the trick.
Hence 8x8 also does the trick, and the problem is solved.
- Joined
- 26 Apr 03
- Moves
- 26771
15 May 10
Colour alternate columns black / white in vertical stripes.
There are 32 black squares.
A horizontal domino covers one black square.
A vertical domino covers 0 or 2 black squares.
To cover an even number of black squares there must be an even number of horizontal dominoes.
16 May 10
Originally posted by iamatigerHow can a vertical domino cover 0 or 2 black squares?
Colour alternate columns black / white in vertical stripes.
There are 32 black squares.
A horizontal domino covers one black square.
A vertical domino covers 0 or 2 black squares.
To cover an even number of black squares there must be an even number of horizontal dominoes.
- Joined
- 26 Apr 03
- Moves
- 26771
17 May 10
Originally posted by AThousandYoungThis is is a very good one in its own right!
Two dominoes side by side make a square. You can rotate that square 90 degrees without affecting anything outside of it. You can't do that with one domino. Thus, you have to have pairs of dominoes that are offset from the rest.
Is it possible to cover a chessboard with dominoes, such that there are no two dominoes which are exactly side-by-side, i.e. no internal 2*2 squares as described by AThousandYoung?
17 May 10
1 edit
Originally posted by iamatigerInteresting...no, it isn't. I used the following argument.
Is it possible to cover a chessboard with dominoes, such that there are no two dominoes which are exactly side-by-side, i.e. no internal 2*2 squares as described by AThousandYoung?
Place a domino in a corner. Let's say a1/b1. Then there must be one at a2/a3 (because if it was at a2/b2 we'd have a square).
We can keep using similar arguments to force lots of other placements. There must be dominoes at: b2/c2, c1/d1, b3/b4, a4/a5, c3/d3, d2/e2, e1/f1, c4/c5, b5/b6, a6/a7, a8/b8, b7/c7, c6/d6...
But now, either we place a domino at d4/d5 (making a square with c4/c5), or at both d4/e4 and d5/e5 (making a square between them). So it's not possible.
(You can continue and fill the board with only 1 such square, though).