Author |
Topic: Cover with L-shaped trominos (Read 4781 times) |
|
BNC
Uberpuzzler
Gender: 
Posts: 1732
|
 |
Cover with L-shaped trominos
« on: May 10th, 2004, 3:30pm » |
 Quote  Modify
|
Not sure if it's not on the site already -- but couldn't find it.
An L-shape tromino is a shape composed of 3 squares, in the shape of an (surprise surprise) L.
A chessboard with NXN squares is used. One square is removed at random (leaving N*N-1 squares).
Can the mutilated chessboard be totally tiled with L-shaped trominos? Can you find conditions for N?
PS: I only know some of the possibilities.
|
|
 IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Cover with L-shaped trominos
« Reply #1 on: May 10th, 2004, 3:51pm » |
Quote Modify
|
The first and most obvious condition is: N = 0 or N = 1 mod 3.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Cover with L-shaped trominos
« Reply #2 on: May 10th, 2004, 11:40pm » |
Quote Modify
|
Unless I misunderstood the problem, I don't think Icarus's conditions are true.
Here's a sufficient condition: N is a power of 2. The way to tile it in this case is somewhere on the site.
|
| « Last Edit: May 10th, 2004, 11:43pm by Barukh » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Cover with L-shaped trominos
« Reply #3 on: May 10th, 2004, 11:57pm » |
Quote Modify
|
on May 10th, 2004, 3:51pm, Icarus wrote:| The first and most obvious condition is: N = 0 or N = 1 mod 3. |
|
You can solve it for N=2 as well, so maybe it should be
N = 0 or N = 1 or N = 2 mod 3 
[edit]
reconsidering, I suppose you probably meant ::N = 1 or N = 2 mod 3
as ((3k+1)2-1) = 0 and ((3k+2)2-1) = 0 mod 3, but ((3k)2-1) isn't::
[/edit]
|
| « Last Edit: May 11th, 2004, 12:31am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
I agree with Barukh.
For n = 2 (4 x 4) it is easy to arrange them.
For n = 3 (8 by 8) arrange 3 sets of the 4 x 4 configuration such that the three extra squares form one extra triomino, with the fourth one having the extra square in the corner.
For each additional n repeat the n-1 x n-1 configuration four times, rotating in such as way as to create one extra triomino.
|
| « Last Edit: May 11th, 2004, 7:12pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Cover with L-shaped trominos
« Reply #5 on: May 11th, 2004, 3:45am » |
Quote Modify
|
The interesting question is whether this also a necessary condition.
And, in case there are other N, for which removed squares the tiling is possible?
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2874
|
|
Re: Cover with L-shaped trominos
« Reply #6 on: May 11th, 2004, 4:02am » |
Quote Modify
|
A moment's thought gives a tiling for 5*5 with a hole in the center ::Two L's form a 3*2 rectangle. Four of them arranged with rotational symmetry...::
I suspect there are other related cases as well.
[e]A quick search comes up with this thread in medium that covers the powers of two case[/e]
|
| « Last Edit: May 11th, 2004, 4:11am by rmsgrey » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Cover with L-shaped trominos
« Reply #7 on: May 11th, 2004, 4:23am » |
Quote Modify
|
There are certainly more boards with a square removed that can be tiled with triominos, but if we're looking for boards which can always be tiled regardless of which square is removed that's a lot harder.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Cover with L-shaped trominos
« Reply #8 on: May 11th, 2004, 4:15pm » |
Quote Modify
|
on May 10th, 2004, 11:57pm, towr wrote:| I suppose you probably meant ::N = 1 or N = 2 mod 3 |
|
Yes. I realized I'd messed up after I logged off yesterday, but haven't gotten back until now. I based my comment on BNC's formula N*N-1, without bothering to think it out myself. Otherwise I would have realized that I had foolishly interpreted it as N(N-1) (why I don't know - somewhere along the way I do recall hearing about an "order of operations"  ).
Of course the number of squares is actually N2 - 1 = (N-1)(N+1). Since this number must be divisible by 3, either N-1 is divisible by 3 or N+1 is.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Cover with L-shaped trominos
« Reply #9 on: May 12th, 2004, 2:09am » |
Quote Modify
|
I think I can tile a 7 by 7 board with any square missing.. So it doesn't only work for powers of 2
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
yadayada
Guest
|
|
Re: Cover with L-shaped trominos
« Reply #10 on: May 12th, 2004, 5:56pm » |
Quote Modify
 Remove
|
Here is one more observation:
If NxN is tilable (one square removed), then if N > 6 and N is even (N+6)x(N+6) is also tilable.
Proof is as follows:
let X = N+6.
Given X by X board with a square removed.
We can divide the board up into NxN, two 6xN and one 6x6 board with the hole lying in the NxN part.
We can easily tile the 6x6 and 6xN parts completely with L-shaped dominoes.
So we can tile 14x14 etc.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Cover with L-shaped trominos
« Reply #11 on: May 12th, 2004, 11:39pm » |
Quote Modify
|
It also works when N is odd
so we've got
7+6k,
8+6k,
I've also tiled 10 (easy starting from 8), so 10+6k
So if someone can tile 11 we've got every N > 6 non-divisible by 3
[edit]Also got 11 now (based on 7)
so the necessary and sufficient condition is that N is a positive whole number which isn't a multiple of 3 nor is [e]1 or[/e] 5 [/edit]
|
| « Last Edit: May 13th, 2004, 5:14am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: Cover with L-shaped trominos
« Reply #12 on: May 13th, 2004, 4:53am » |
Quote Modify
|
For n=1, the solution is trivial. It is very easy to find a tiling that covers all but one square for any possible missing square of a 1*1 square.
That just leaves the 5*5 case which is presumably provably impossible?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Cover with L-shaped trominos
« Reply #13 on: May 13th, 2004, 5:18am » |
Quote Modify
|
It's not too hard to proof it is impossible.
if the square (1,2) is empty, there must be a triomino covering
(1,1), (2,1) and (2,2), and with that 2 by 2 subboard taken it's impossible to tile the rest.
This is because the only way to tile a 3xN piece is with 3x2 blocks (consisting of two triominos) So we end up with a 3x1 piece which can't be tiled
|
| « Last Edit: May 13th, 2004, 5:21am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Cover with L-shaped trominos
« Reply #14 on: May 18th, 2004, 7:31pm » |
Quote Modify
|
on May 13th, 2004, 4:53am, rmsgrey wrote:| That just leaves the 5*5 case which is presumably provably impossible? |
|
Yes, the 5x5 case is not possible.
Only the squares marked X are removable.
X _ X _ X
_ _ _ _ _
X _ X _ X
_ _ _ _ _
X _ X _ X
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print