Results 1 to 3 of 3

Math Help - Checkerboard: Use proof by contradiction

  1. #1
    Newbie
    Joined
    Nov 2006
    Posts
    15

    Checkerboard: Use proof by contradiction

    ee
    Attached Files Attached Files
    Last edited by chillerbros17; February 28th 2007 at 03:33 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by chillerbros17 View Post
    checkerboard.doc

    The problem is in the attachment.
    Suppose it can be made from the given tiles, then there will be 15 of them.
    This is because there are 60 small squares on the board to be covered, 30
    light and 30 dark.

    So there must be an even number of one type of tiles and an odd number of
    the other.

    Now the tile type that is used an even number of times is covering an even
    number of light squares and an even number of dark squares.

    Also the tile type that is used an odd number of times is covering an odd
    number of light squares and an odd number of dark squares (as the two
    tile types both have an odd number of light and dark squares in them).

    So the tiling covers an odd number of light squares and an odd number of
    dark squares, which as the board actualy has an even number of both
    is a contradiction. Hence no such tiling exists.

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,912
    Thanks
    776
    Hello, chillerbros17!

    There are 30 black squares and 30 white squares to be covered.

    Each type-A tile covers 1 black and 3 white squares.
    Each type-B tile covers 3 black and 1 white squares.

    A pair (AB) covers 4 black and 4 white squares.

    Using seven pairs of tiles, we can cover 28 black and 28 white squares.

    But there will be 2 black and 2 white squares remaining to be covered.
    It is impossible to cover them with either a type-A or a type-B tiles.

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proof by contradiction
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 22nd 2011, 02:17 AM
  2. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 11:07 PM
  3. Proof by contradiction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 5th 2010, 05:17 PM
  4. Proof by Contradiction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 7th 2009, 02:08 PM
  5. Proof of checkerboard pieces
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 14th 2007, 01:11 PM

Search Tags


/mathhelpforum @mathhelpforum