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

Home > Shapes
Tiling with Triominoes (Posted on 2023-09-22) Difficulty: 4 of 5
There are two triominoes. One is simple a 1x3 rectangle and the other is a small L-shaped piece.

Using any combination of these two triominoes and in any orientation, how many ways can a 3 by N rectangle be tiled?
Rotations and reflections of an asymmetrical solution are to be considered distinct.

No Solution Yet Submitted by Brian Smith    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
re: thanks | Comment 5 of 6 |
(In reply to thanks by Steven Lord)

I haven't tried to read the paper you cited, but I do have my own proof that our building blocks are the 2 oddballs and 3 infinite sets.


First let's make our blocks out of only the straight triomino.  A single vertical piece has a fault line on each side.  So a vertical piece by itself is a block.
The other option is placing the pieces horizontally, then we need to start all three pieces at the same edge. (we don't have the L-piece available)  So then we get a 3x3 square of three horizontal pieces stacked on each other - and again we have a fault line on either side.  So this is our second block; and that is all the blocks we can make with just the straight triomino.

So now let's move on to adding the L-triomino.  Consider this diagram:
.AB..
..C..
..CC.
The C's represent a placed L-triomino.  Assume a single other triomino covers both A and B.  But then draw a vertical line at the tall vertical edge of triomino C.  This cuts between A and B - so now we have a partial triomino to the left and right of the line.  
But the line also splits the rectangle into two smaller rectangles each with area that is a multiple of 3.  But since each rectangle has a partial triomino in it we run into a problem since the untiled area is not a multiple of 3.
This is a contradiction. So our assumption of placing a single triomino to cover both A and B is wrong.  
This means that every possible placement of a L-triomino is at a fault line in the tiling. Which means that an L-triomino can only occur at the left end or right end of a building block.

Also, we can infer that every block with an L-triomino at one end must have a mate at the other end to match up the parity of the rows.  Then at this point we can construct the three infinite families of blocks by choosing how the two L-triominos are placed relative to each other.

  Posted by Brian Smith on 2023-11-09 11:51:35
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 (2)
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