Results 1 to 10 of 10

Math Help - Covering problem (board and dominoes)

  1. #1
    Junior Member
    Joined
    Sep 2010
    Posts
    43

    Covering problem (board and dominoes)

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by doug View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    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]
    Last edited by awkward; September 28th 2010 at 01:58 PM. Reason: add p.s.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by awkward View Post
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    I don't think it's obvious that a board like this can be tiled with dominoes..
    Attached Thumbnails Attached Thumbnails Covering problem (board and dominoes)-1212board.png  
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Maybe one can prove a strategy like this will always work.
    Attached Thumbnails Attached Thumbnails Covering problem (board and dominoes)-1212board2.png  
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by undefined View Post
    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
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    Actually there is a partition which proves the fact. How do we post images here ?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Traveller View Post
    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!
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    Covering problem (board and dominoes)-pic.bmpCovering problem (board and dominoes)-screenshot1.png


    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.
    Attached Thumbnails Attached Thumbnails Covering problem (board and dominoes)-screenshot2.png  
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Covering board with dominoes
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 27th 2011, 06:19 PM
  2. Fixed radius disjoint ball covering vs. open covering
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: November 22nd 2010, 07:01 AM
  3. Dominoes
    Posted in the Statistics Forum
    Replies: 1
    Last Post: March 24th 2010, 05:37 PM
  4. Super Slanted wooden board beam problem
    Posted in the Geometry Forum
    Replies: 3
    Last Post: August 11th 2009, 09:56 PM
  5. board problem
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 11th 2009, 08:25 PM

Search Tags


/mathhelpforum @mathhelpforum