Covering problem (board and dominoes)

[doug]

We cut off some squares from the bottom row (rank) of a 2k x 2k board. We should prove that we can cover the board with 2 x 1 dominoes if and only if the number of the cut black and white squares are equal.

As far as I know proving 'only if' part is easy because a dominoe always cover one white square and one black square. There was even (2k*2k) square, so it is obvious than we should have cut off equal black as white squares. (If we had cut of more black squares, there would have been more white squares, so we couldn't cover the board.) So I proved that it is necessity. -Am I right?

But how can we prove the 'if' part? I don't see why it is a possibility?

I would really appreciate any help.

[tonio]

We cut off some squares from the bottom row (rank) of a 2k x 2k board. We should prove that we can cover the board with 2 x 1 dominoes if and only if the number of the cut black and white squares are equal.

As far as I know proving 'only if' part is easy because a dominoe always cover one white square and one black square. There was even (2k*2k) square, so it is obvious than we should have cut off equal black as white squares. (If we had cut of more black squares, there would have been more white squares, so we couldn't cover the board.) So I proved that it is necessity. -Am I right?

But how can we prove the 'if' part? I don't see why it is a possibility?

I would really appreciate any help.

Isn't it the same? I mean, isn't you above argument an iff one? If you can cover the chess board with domino pieces then you MUST have covered exactly the same number of white and black squares, which means they've been cut the same name of white and black squares...

Tonio

[awkward]

I think I would try induction on k.

Going from k to k+1, take the 2k+2 by 2k+2 board and trim off a border 2 squares wide along the top and right side. In so doing you have trimmed off the rightmost two squares along the bottom edge. These squares have opposite colors, so either both were included in the original board or both were cut off in the original board. See if you can work this around to showing that the 2k+2 by 2k+2 board can be covered by dominoes.

[Edit]I guess it's clear from the above that I disagree with Tonio, I think you have to demonstrate that a covering with dominoes exists. [/edit]

[tonio]

I think I would try induction on k.

Going from k to k+1, take the 2k+2 by 2k+2 board and trim off a border 2 squares wide along the top and right side. In so doing you have trimmed off the rightmost two squares along the bottom edge. These squares have opposite colors, so either both were included in the original board or both were cut off in the original board. See if you can work this around to showing that the 2k+2 by 2k+2 board can be covered by dominoes.

[Edit]I guess it's clear from the above that I disagree with Tonio, I think you have to demonstrate that a covering with dominoes exists. [/edit]

I don't think there is any problem with proving that an 8x8 board (or for that matter, 2k x 2k board) can be evenly covered by domino pieces (each covering two adjacent squares), and if this is clear I can't see any problem in "my proof"...
In fact, the main problem here is, I believe, that people have to know what is a chess-like board and what are domino pieces.

Tonio

[undefined]

I don't think it's obvious that a board like this can be tiled with dominoes..

[undefined]

Maybe one can prove a strategy like this will always work.

[tonio]

I don't think it's obvious that a board like this can be tiled with dominoes..

You are right, but I meant 2k x 2k chess-like boards, i.e. "complete" boards. which yours isn't.

Cetainly your example makes it clear that some care must be put, though.

Tonio

[Traveller]

Actually there is a partition which proves the fact. How do we post images here ?

[undefined]

Actually there is a partition which proves the fact. How do we post images here ?

If you right click on the reply link and open in new tab/window, or else if you click on "Go Advanced", you will get more options, then look for the Manage Attachments button further down.

Looking forward to seeing it!

[Traveller]

I think this algorithm successfully covers the board. I am not providing detailed analysis of each step, assuming that readers will be able to work those out themselves :

We will represent the white and black squares by W and B respectively. The squares which we cut off will be represented by E (empty).

Assume the chessboard's last row is of the form: WBWBWB...

1) We traverse the last row once from the left, and cover the sequences WB or BW of unremoved squares trivially by horizontal dominoes.

2) We again traverse the last row from the left, until we encounter the first uncovered square. Until then, for every pair of removed/ covered squares WB, we cover the whole column above them with horizontal dominoes stacked upon each other. Clearly the only time at which this step will stop is when we have EB at the last row.

3) We create a partial red pyramid of height two as in figure 1.

4) Till we encounter any more uncovered squares, we proceed by extending the frontier of the covered block and pyramid by the horizontal green and blue dominoes respectively.

5) If we encounter an uncovered black square next, we cover as shown in figure 5, to increase the height of the pyramid by two.

6) If we encounter an uncovered white square next, first we cover as in figure 3. cover the portion of the penultimate row stretching from the black to the white square with horizontal dominoes ( this is possible because the length concerned is even ), and then we cover the bottom two uncovered squares of each column to the right with vertical dominoes (coloured yellow in figure 6) . This will bring up the whole floor of the board and decrease the effective height of the pyramid by two.

7) If the number of uncovered white squares encountered becomes equal to the number of uncovered black squares encountered, then we use the very next column to the right to create a block of even breadth as in figure 4. This can be easily covered with horizontal dominoes.

8) If we have not encountered the last uncovered square yet, we go back to step 2.

P.S. If this is written too badly to understand, then let me know, I will write it afresh.