wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Cover with L-shaped trominos
        
(Message started by: BNC on May 10^th, 2004, 3:30pm)

Title: Cover with L-shaped trominos
Post by BNC on May 10^th, 2004, 3:30pm

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.

Title: Re: Cover with L-shaped trominos
Post by Icarus on May 10^th, 2004, 3:51pm

The first and most obvious condition is: [hide] N = 0 or N = 1 mod 3.[/hide]

Title: Re: Cover with L-shaped trominos
Post by Barukh on May 10^th, 2004, 11:40pm

Unless I misunderstood the problem, I don't think Icarus's conditions are true.

Here's a sufficient condition: [hide]N is a power of 2[/hide]. The way to tile it in this case is somewhere on the site.

Title: Re: Cover with L-shaped trominos
Post by towr on May 10^th, 2004, 11:57pm

on 05/10/04 at 15:51:44, Icarus wrote:

The first and most obvious condition is: [hide] N = 0 or N = 1 mod 3.[/hide]

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 ::[hide]N = 1 or N = 2 mod 3
as ((3k+1)²-1) = 0 and ((3k+2)²-1) = 0 mod 3, but ((3k)²-1) isn't[/hide]::
[/edit]

Title: Re: Cover with L-shaped trominos
Post by THUDandBLUNDER on May 11^th, 2004, 3:19am

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.

Title: Re: Cover with L-shaped trominos
Post by Barukh on May 11^th, 2004, 3:45am

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?

Title: Re: Cover with L-shaped trominos
Post by rmsgrey on May 11^th, 2004, 4:02am

A moment's thought gives a tiling for 5*5 with a hole in the center ::[hide]Two L's form a 3*2 rectangle. Four of them arranged with rotational symmetry...[/hide]::

I suspect there are other related cases as well.

[e]A quick search comes up with this (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1064475819) thread in medium that covers the powers of two case[/e]

Title: Re: Cover with L-shaped trominos
Post by towr on May 11^th, 2004, 4:23am

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.

Title: Re: Cover with L-shaped trominos
Post by Icarus on May 11^th, 2004, 4:15pm

on 05/10/04 at 23:57:50, 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" :P).

Of course the number of squares is actually N² - 1 = (N-1)(N+1). Since this number must be divisible by 3, either N-1 is divisible by 3 or N+1 is.

Title: Re: Cover with L-shaped trominos
Post by towr on May 12^th, 2004, 2:09am

I think I can tile a 7 by 7 board with any square missing.. So it doesn't only work for powers of 2

Title: Re: Cover with L-shaped trominos
Post by yadayada on May 12^th, 2004, 5:56pm

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.

Title: Re: Cover with L-shaped trominos
Post by towr on May 12^th, 2004, 11:39pm

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]

Title: Re: Cover with L-shaped trominos
Post by rmsgrey on May 13^th, 2004, 4:53am

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?

Title: Re: Cover with L-shaped trominos
Post by towr on May 13^th, 2004, 5:18am

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

Title: Re: Cover with L-shaped trominos
Post by grimbal on May 18^th, 2004, 7:31pm

on 05/13/04 at 04:53:02, 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