Covering the 62 Squares with Dominoes

[Jimmy Snyder]

Start with a 8 by 8 board of squares (for instance, a chessboard) and take away the top-left and bottom-right corner squares so that there are 62 squares left. Take some dominoes that are the same size as two squares of the chessboard. Can you cover the 62 squares of the board with 31 such dominoes? If so, how? If not, why?

 

[ssj5harsh]

Using standard chessboard colouring

Here is a solution using the standard chessboard colouring(alternate white and black squares).:
On looking at a chessboard, we can see that the opposite blocks(as mentioned) have the same colour. So, after removing the two squares, we would have
- 32 white and 30 black squares OR
- 30 white and 32 black squares

The two cases are identical (due to symmetry of the chess board). So I will solve only the first.
Said domino covers two squares. On a chessboard, that means one white and one black square. 31 dominoes will cover 31 white and 31 black squares, but there are only 30 black squares. So 31 dominoes cannot cover the board.

 

[Jimmy Snyder]

Very good ssj5harsh. You got it. I hope you realize that although the colors are a good way of thinking about the problem, the board doesn't actually need to be colored for the solution to work.

 

[ArielGenesis]

actually, if we try, we can cover 6 squares in the chess board using the domino of the 2-chessboard-square size. as the question doesn't mention if we have to cover the square compleately. this way, it is possible, even with less then 31 dominos. if the number (31) in neccesary, we can just use the excess domino to pile up ontop of the other domino or fill uf the empty space.

 

[ssj5harsh]

without colouring?

I have tried as jimmysnyder told me to try without colouring[/color]. But I can't arrive at an unambiguous proof. Perhaps someone could guide me about it.

 

[Jimmy Snyder]

If there were a solution without coloring, the same solution would work on the colored board.

 

[what]

Think about it as if you had a regular chess board(8x8) full of dominoes(32), in any kind of arrangment. Now try to take away one domino and leave two empty spaces that aren't adjacent.

 

[Jimmy Snyder]

Think about it as if you had a regular chess board(8x8) full of dominoes(32), in any kind of arrangment. Now try to take away one domino and leave two empty spaces that aren't adjacent.

This is not a good way to think of the problem. For instance, take the chess board and remove the top left and top right corner squares. These squares are not adjacent, but the board can easily be covered with the 31 dominoes.

 

[what]

touche, just thinking out loud. I'm sure then that it has to do with the shape. Perhaps there has to be an even number of squares in each row.
edit* not sure if that would work either- no it wouldn't work, i'll think about it later when i have a fresh mind

 

[xJuggleboy]

Think about it as if you had a regular chess board(8x8) full of dominoes(32), in any kind of arrangment. Now try to take away one domino and leave two empty spaces that aren't adjacent.

Ah ha! I am going to try and make this simple =-) you have a 2x2 board. take out 2 diagonal squares. You can't cover the last 2 with one domino. So if you had a 8x8 board and cover the board however you wish. and remove any 2 squares that are at a diagonal. You can rearrange the remaining dominos to get your 2x2 square around them and the board becomes impossible to cover.

 

[Jimmy Snyder]

Ah ha! I am going to try and make this simple =-) you have a 2x2 board. take out 2 diagonal squares. You can't cover the last 2 with one domino. So if you had a 8x8 board and cover the board however you wish. and remove any 2 squares that are at a diagonal. You can rearrange the remaining dominos to get your 2x2 square around them and the board becomes impossible to cover.

The shortcoming of this approach is that it can't be extended to different configurations of the problem (besides the fact that I didn't understand it). For instance, if instead of removing the corner squares as in the original problem, we remove two squares from the board that are a knight's move away from each other, then looking at diagonals won't work, but ssj5harsh's solution will.

In my opinion, the easiest way to look at the problem is as ssj5harsh does in the first solution posted. Each domino must cover both a black and white square. In the problem, the two squares removed were the same color. That is a good and easy to understand solution. My comment about not needing the colors simply meant that this solution works even if the board is colored green and red, or is not colored at all. Just mentally assign colors to each square. Or assign odd and even numbers so that colors don't enter into it. Or do as I had suggested: Note that if you could cover the uncolored board with the dominos then the same solution would apply to the colored board.

 

[xJuggleboy]

Ok I reread my solution and I admit it may be a bit confusing... It was a bit of rambling I came up with real quick that mostly described what I was thinking =-) I was trying to come up with a proof that would describe the problem without using the 32 black squares and 30 white squares.

I was going to try and reiterate the solution here but It would be just as confusing as the first attempt =-(

The shortcoming of this approach is that it can't be extended to different configurations of the problem (besides the fact that I didn't understand it). For instance, if instead of removing the corner squares as in the original problem, we remove two squares from the board that are a knight's move away from each other, then looking at diagonals won't work, but ssj5harsh's solution will.

Im not sure what you mean by that. removing 2 squares a knights move away from each other would not be a problem as they would not hinder filling the board with 31 dominos.

As I said I am trying to come up with a solution that does not require a colord squares aproch. Or for that matter odd/even numbers.

 

[Jimmy Snyder]

Im not sure what you mean by that. removing 2 squares a knights move away from each other would not be a problem as they would not hinder filling the board with 31 dominos.

Of course you are right. What was I thinking? What I meant was that ssj5harsh's analysis works whenever you remove two squares of the same color whether they are on the same diagonal or not.

 

[Jimmy Snyder]

As I said I am trying to come up with a solution that does not require a colord squares aproch. Or for that matter odd/even numbers.

In general, it is good to try and come up with new approaches to problems that have already been solved. In this way, new insights are gained. However, if your goal is to come up with an approach that is simpler to understand than ssj5harsh's, I believe you have a daunting task ahead of you.

 

[JonF]

I have tried as jimmysnyder told me to try without colouring[/color]. But I can't arrive at an unambiguous proof. Perhaps someone could guide me about it.

Given any M by N board where M and N are even, that can be covered by 2 by 1 dominos:

Suppose there is a M by N grid of cells on the board with elements (j,k), with each squared labeled some number P where p is that squares j+k

Notice that the p’s alternate even an odd. So each domino will cover an even and a odd square.

The first square (1,1) has an even p.
The last square (M,N) is also even, since any two evens added equals a even.

By removing two squares with even p’s two dominos will not be able to be placed.

 

[xJuggleboy]

Given any M by N board where M and N are even, that can be covered by 2 by 1 dominos:

Suppose there is a M by N grid of cells on the board with elements (j,k), with each squared labeled some number P where p is that squares j+k

Notice that the p’s alternate even an odd. So each domino will cover an even and a odd square.

The first square (1,1) has an even p.
The last square (M,N) is also even, since any two evens added equals a even.

By removing two squares with even p’s two dominos will not be able to be placed.

Still the odd even aproch. The must be a better explanation than that.

Im just going to sit here pondering it

 

[Gokul43201]

Odd/even is no different from black/white.

But it should be clear that the problem can not be solved without retaining some information about the location of the square. The residue, mod 2 of the sum of co-ordinates is one such piece of info...but a necessary (bariing a choice which retains more info) piece, nevertheless.

 

[TenaliRaman]

I wish jimmy had originally given this board as uncoloured.

-- AI

 

[Jimmy Snyder]

Your wish was granted even before you made it known to me.

 

[JonF]

Here is what I am thinking, even though it may totally be wrong, unclear, and impossible to explain without pictures...

Given that the “board” is a even number by an even number in dimension.


Let there be groupings of the squares on the board such that every square is covered in a rectangular shape i.e. a “box”.


Now if we were able to place the tiles, one of the following would have to be true for all groupings of boxes:
i) Every box would be exactly covered by tiles
ii) There would be excess in ends of tiles in some boxes, overlapping into other boxes


For any possible grouping of “boxes” that cover the whole board with the two opposite corner squares removed there must be at least one box with “odd sized area” *


A box with an odd sized area cannot be exactly filled with 2x1 tiles, since the tiles have an even sized area and we are putting n tiles into the box.

If a box is filled with “left over” parts of tiles hanging over the sides of the “boxes” there must be an odd number of left over parts that end up in other boxes. Which in turn would then give another box an “odd amount of area”. Since we are only considering finite sized boards, some box would have to be left over with odd sized area, which implies it couldn’t be filled with tiles.


* This is what I haven’t figured out how to show yet, even though I am sure it’s true.

 

[BicycleTree]

You can establish that the board cannot be tiled with even-sized boxes through a checkeboard color argument. But your argument does not consider cases when odd sized boxes overlap into other odd sized boxes, or in general when there is more than one odd-sized box on the board.

Edit: also, not being able to divide the board into rectangles without one of them being odd-sized directly means that you can't tile it with dominoes, since all dominoes are even-sized and a domino tiling would be a rectangular division.

 

[Jimmy Snyder]

JonF, I haven't figured out if your approach works, but in my mind it is already more complicated than ssj5harsh's. Please tell me this. Does your approach handle the fact that if you take away the top right and top left corner squares of an 8 x 8 board, then the board can be covered by 31 dominos?

 

[ssj5harsh]

Here's another solution, very similar, yet using the pigeonhole principle.(I'm not sure that it does though)

Example 2

Consider a chess board with two of the diagonally opposite corners removed. Is it possible to cover the board with pieces of domino whose size is exactly two board squares?
Solution

No, it's not possible. Two diagonally opposite squares on a chess board are of the same color. Therefore, when these are removed, the number of squares of one color exceeds by 2 the number of squares of another color. However, every piece of domino covers exactly two squares and these are of different colors. Every placement of domino pieces establishes a 1-1 correspondence between the set of white squares and the set of black squares. If the two sets have different number of elements, then, by the Pigeonhole Principle, no 1-1 correspondence between the two sets is possible.

Its taken from here: http://www.cut-the-knot.org/do_you_know/pigeon.shtml