Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » Math Topics » alt.math.undergrad.independent

Topic: tiling a defective chess-board
Replies: 1   Last Post: May 20, 2000 10:25 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Kathleen

Posts: 58
Registered: 12/6/04
tiling a defective chess-board
Posted: May 18, 2000 1:00 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


I hope somebody can help me with this question. I'm kind of stuck ...


The qn is:

Suppose you are given a "chess-board" that has 2^n rows and 2^n
columns. You are given an endless supply of L-shaped tiles - each one
is a 2x2 chess-board with the upper right square removed. Now,
suppose somebody removes a single, random square from your original
chess-board. Show that you can completely cover the remaining squares
with your L-shaped pieces, without overlapping any of them.

HINT: If you divide your chess-board in half, vertically and
horizontally, you get four smaller versions of the same problem. Can
three of these sub-problems combine to leave a handy L-shaped hole?




I started by drawing out the first few defective chess-boards and
found that for a 2x2 board you had 1 L shaped piece (triomino)
4x4 --> 5 triominos
8x8 --> 21 "

that pattern seems to suggest that each board will have 4 times the
number of triominos the previous board has plus 1. Then I thought
this doesn't help me any with this qn....

Maybe some sort of constructive proof would be the way to go? I don't
know & I'm not sure how to get started. Could anyone help please?

Thank you,
Kathleen



Date Subject Author
5/18/00
Read tiling a defective chess-board
Kathleen
5/20/00
Read triominoes
macduff

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.