All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Shapes
Triominoes (Posted on 2002-05-21) Difficulty: 3 of 5
This is a triomino piece:
(A 2 x 2 cell square with one of the corner cells removed)

Prove that a square, 2^n cells to the side, with one square cell removed from the corner can be covered with triomino pieces without any overlapping or going over the border for any natural value of n. The triominos can be rotated.

(For example if n = 1, the result is a triomino shape to begin with - a 2 x 2 square with one cell removed.)

See The Solution Submitted by levik    
Rating: 3.1667 (12 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Inductive proof Comment 7 of 7 |
Inductive proof:

Clearly this holds for N=1 (by using one Triomino).  We will now show that if it holds for N, it holds for N+1.

The N+1 case is, of course, twice as big as the N case, in each direction.  Take our solution for the N case, and use it to cover the lower-right quadrant of the N+1 case.  It will fill it in perfectly.  Now we are left with a six-sided figure -- the other three quadrants, each of which is a perfect (and complete!) square of 2^N size.  Put another copy of our solution for the N case on the top-left quadrant, which leaves the lower-right cell of that quadrant empty.  Rotate our solution for the N case counter-clockwise by 90 degrees, and put the result into the lower-left quadrant, which leaves the upper-right cell of that quadrant empty.  Rotate the original solution for the N case clockwise by 90 degrees, and put that result into the upper-right quadrant, which leaves the lower-left cell of that quadrant empty.  Now, one more single Triomino can cover the three cells we left empty -- the lower-right cell of the upper-left quadrant, the upper-right cell of the lower-left quadrant, and the lower-left cell of the upper-right quadrant.

  Posted by Caleb on 2012-08-26 17:59:14
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (14)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information