If a domino piece is exactly the size of two squares of the chessboard, it would take 32 domino pieces to cover the 64 squares.
Each domino can be either horizontal (long edges parallel to the ranks) or vertical (long edges parallel to the files).
Prove that the number of horizontal dominoes must be even.
Originally posted by David113Is zero an even number?
If a domino piece is exactly the size of two squares of the chessboard, it would take 32 domino pieces to cover the 64 squares.
Each domino can be either horizontal (long edges parallel to the ranks) or vertical (long edges parallel to the files).
Prove that the number of horizontal dominoes must be even.
*edit* I guess it is according to wikipedia.
Originally posted by David113Considering any single rank or file, it can only be fully covered by an even number of horizontal dominoes plus an even number of vertical dominoes(including possibly zero).
If a domino piece is exactly the size of two squares of the chessboard, it would take 32 domino pieces to cover the 64 squares.
Each domino can be either horizontal (long edges parallel to the ranks) or vertical (long edges parallel to the files).
Prove that the number of horizontal dominoes must be even.
Since this applies to any and every rank and file, the total must be an even number of both horizontal and vertical.
Originally posted by luskinWhy? a rank can have any number of horizontal dominoes from 0 to 4 - odd or even.
Considering any single rank or file, it can only be fully covered by an even number of horizontal dominoes
About vertical dominoes - the rank has an even number of HALFS of vertical dominoes. This only shows we have in total an even number of HALFS of vertical dominoes, which is trivially true. It doesn't show we have an even number of vertical dominoes.
Originally posted by David113
Why? a rank can have any number of horizontal dominoes from 0 to 4 - odd or even.
About vertical dominoes - the rank has an even number of HALFS of vertical dominoes. This only shows we have in total an even number of HALFS of vertical dominoes, which is trivially true. It doesn't show we have an even number of vertical dominoes.
This might be wrong and it certainly isn't snappy but I'll give it a go.
Suppose it can be arranged there are precisely k horizontal dominoes placed arbitrarily on the chess board (in such a way that placing vertical dominoes on the spaces which remain will yield a complete tiling)
Given this is the case then take any block of contiguous and isolated horizontal dominoes, if no such block exists go to (3)
1.a) If infront of each half horizontal domino there is at least empty two spaces, then move this block 2 spaces forwards. If not go to (2.a)
1.b) go to (1.a)
2.a) If infront of at least 1 domino in this block there is only one space then we necessarily need another horizontal tile (and would have needed one prior to any movements), contradicting that we have a full tiling with k horizontal tiles.
2.b) If (2.a) is not the case either there are no dominoes in the current block which have space in front, otherwise there is at least 1 half of a horizontal domino having an even number of spaces infront of it (otherwise we require another horizontal domino which is impossible). in either case choose another isolated block and proceed to (1.a)
3) Once we have dealt with all isolated blocks, and given our tiling is still valid then we should have an arrangement such that a single block of horizontal dominoes lies at the top of the board and below this block it is true that behind each domino there is an even number of spaces (else we require further horizontal dominoes which is impossible).
4) In between these horizontal dominoes may lie empty spaces and for each two ranks there will be space for an even number of vertical dominoes (since the space taken by the horizontal dominoes is even). Therefore we can fill these spaces with an even number of vertical dominoes, to create a rectangular block.
5) It follows then (by 3) that there must be an even number of vertical dominoes.
This implies an even number of horizontal dominoes.
If you place one horizontal domino you leave 7 squares in that file. This cannot be filled with vertical dominos (at most you need 3 verticals and one horizontal to fill the remaining square) so each file crossed by a horizontal domino needs to have another one to pair it with.
If these horizontal dominos are offset then the overhang will cause the same issues. It will be like bricks on a wall there will always be a problem square. So the horizontal dominos not only have to be in pairs but they have to be aligned in pairs too.
Is there a flaw in this thinking? More than likely a flaw in the explaining but I am convinced.
I think I've got a simple way of looking at it.
Consider the total number of filled squares on files 1, 3, 5, 7.
Every time you place a domino horizontally, you increase this number by 1. Every time you place one vertically, you increase it by either 0 or 2 (depending on whether you add it to an odd file or not).
The number starts even (0), and must end even (32). So the number of horizontal dominoes must be even.
Originally posted by mtthwI like that explanation a lot.
I think I've got a simple way of looking at it.
Consider the total number of filled squares on files 1, 3, 5, 7.
Every time you place a domino horizontally, you increase this number by 1. Every time you place one vertically, you increase it by either 0 or 2 (depending on whether you add it to an odd file or not).
The number starts even (0), and must end even (32). So the number of horizontal dominoes must be even.
Originally posted by luskinRight...I'll try again now, thinking more clearly this time I hope.
Looking at the 8th(top) rank, if there is any upper half of a vertical domino, there must be an even number of such. Each of these has a lower half, so we have an even number of vertical dominoes so far.
Moving now to the 7th rank, we have an even number of lower halves, which have already been accounted for, but if there are any upper halves here, then again there must be an even number of them, and they will each have lower half in the 6th rank. So far there are still an even number of vertical dominoes.
Continuing the count down each rank in this way, will give a total even number of vertical dominoes, an thus also an even number of horizontal.
Originally posted by mtthwThat is were my mind was leading me but you expressed it much better.
I think I've got a simple way of looking at it.
Consider the total number of filled squares on files 1, 3, 5, 7.
Every time you place a domino horizontally, you increase this number by 1. Every time you place one vertically, you increase it by either 0 or 2 (depending on whether you add it to an odd file or not).
The number starts even (0), and must end even (32). So the number of horizontal dominoes must be even.
Originally posted by David113Because with 21 dominoes you have 10 squares and one half square. You can't fill up a big square this way. If you divide a square into 16 smaller squares you will not end up with an odd number of half-squares.
And why can't I do that with 21 dominoes?
Basically you need 32 dominoes to make 16 2x2 squares to fill up the 8x8 square. Each domino must have a like partner to make a square.
Originally posted by mtthwNice!...I knew there was a more elegant way of showing this :]
I think I've got a simple way of looking at it.
Consider the total number of filled squares on files 1, 3, 5, 7.
Every time you place a domino horizontally, you increase this number by 1. Every time you place one vertically, you increase it by either 0 or 2 (depending on whether you add it to an odd file or not).
The number starts even (0), and must end even (32). So the number of horizontal dominoes must be even.