1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Checkerboard problem

  1. Feb 26, 2010 #1
    1. The problem statement, all variables and given/known data
    Consider an 8x8 checkerboard with two squares from each of two opposite corners deleted so that 60 squares are left (i.e the top row has 6 squares with the 2 far right squares missing, and the bottom row has 6 squares left with the 2 far left missing). Prove that the remaining squares cannot be covered exactly by T-shaped dominos consisting of four squares and their rotations.

    I figured that if the domino is centered on a white piece, then its must cover 3 black pieces surrounding it, and vice versa. this would mean that centering the domino on 10 white pieces automatically covers the 30 black pieces, and thus there is no way to cover the remaining 20 white pieces. Unfortunately, I don't know how to formalize this proof and show that this must be the case.
     
  2. jcsd
  3. Feb 26, 2010 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi morbius27! :smile:

    It might be easier to start by considering how many Ts are needed. :wink:
     
  4. Feb 26, 2010 #3
    well, then obviously 15 Ts would be needed to cover the board, since there are 60 spots and 4 squares to a T. If you alternated centering them on white then black pieces, the 14th one would give 28 covered for both black and white. But since two of each are left, and a T requires 1 w/b and 3 b/w, then it obviously fails...is there any way to show this in a proof format?
     
  5. Feb 26, 2010 #4

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Yes, you've almost proved it.

    Now use the fact that difference between the number of white and black squares for each T is always ±2. :wink:
     
  6. Feb 26, 2010 #5
    Ahh, that does definitely make sense, but how can I show that the optimum way of putting down the Ts is by alternating centering them on black and white squares. i.e. why is that method favorable to, say, centering the first 8 on white then the rest on black, or something similar?
     
  7. Feb 26, 2010 #6

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    What's 15 times ±2 ? :wink:
     
  8. Feb 26, 2010 #7
    well 30 of course =P. So what you're saying is that in order to cover the entire board, the T would have to cover two white and two black, but since it covers 1 white and 3 black (or vice versa) there will always be two left over from each color in the end?
     
  9. Feb 26, 2010 #8

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    I can't tell whether you've got it or not :confused:

    why will there always be two left over?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Checkerboard problem
  1. A problem (Replies: 2)

  2. Problem - (Replies: 7)

  3. Limits problem (Replies: 4)

Loading...