[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Re: [QUIZ] Tiling Turmoil (#33

Jason Bailey

5/20/2005 12:56:00 PM

5 Answers

Mike

5/20/2005 1:08:00 PM

0

> Is there an assumption that this is a square or can it be a rectangle?
>
> ie 4 by 4096 ??
>

"You're going to tile L-trominos on a 2**n by 2**n board that is missing a
single square. What's an L-tromino? It's simply a 2 by 2 square with a
corner missing that looks like an L."

Since "n" will be the same, the sides will always have the same length - so
you only have to worry about squares.

-M

Brian Schröder

5/20/2005 1:12:00 PM

0

On 20/05/05, Jason Bailey <azrael@demonlords.net> wrote:
> Is there an assumption that this is a square or can it be a rectangle?
>
> ie 4 by 4096 ??
>
The definition states 2^n x 2^n, that would seem like a square to me.

best regards,

Brian

James Gray

5/20/2005 1:12:00 PM

0

On May 20, 2005, at 7:55 AM, Jason Bailey wrote:

> Is there an assumption that this is a square or can it be a rectangle?
>
> ie 4 by 4096 ??

From the quiz:

On May 20, 2005, at 7:37 AM, Ruby Quiz wrote:

> You're going to tile L-trominos on a 2**n by 2**n board that is
> missing a single

Or in other words, it's always square. :)

James Edward Gray II

Adriano Ferreira

5/20/2005 1:12:00 PM

0

On 5/20/05, Jason Bailey <azrael@demonlords.net> wrote:
> Is there an assumption that this is a square or can it be a rectangle?
>
> ie 4 by 4096 ??

The man said "on a 2**n by 2**n board". This assumption guarantees the
board has at least a number of squares (2**(2n)-1) which is multiple
of 3 (proof left to the interested reader). Probably it also
guarantees that the L-trominos (with 3 squares) can be fitted into the
board. The situation is different with rectangles: for example, a 4 by
8 board has 31 squares which are not divisible by 3. So you can't fill
it with L-trominos without leaving a blank square.

Regards.
Adriano.

Michael Ulm

5/20/2005 2:19:00 PM

0

Adriano Ferreira wrote:

> On 5/20/05, Jason Bailey <azrael@demonlords.net> wrote:
>
>>Is there an assumption that this is a square or can it be a rectangle?
>>
>>ie 4 by 4096 ??
>
>
> The man said "on a 2**n by 2**n board". This assumption guarantees the
> board has at least a number of squares (2**(2n)-1) which is multiple
> of 3 (proof left to the interested reader). Probably it also
> guarantees that the L-trominos (with 3 squares) can be fitted into the
> board. The situation is different with rectangles: for example, a 4 by
> 8 board has 31 squares which are not divisible by 3. So you can't fill
> it with L-trominos without leaving a blank square.
>

OTOH, the "canonical" solution of this problem should (with minor
modification) work for a 2**n by 2**m board whenever n + m is even
(i.e. whenever the number of empty squares is divisible by 3).

Michael


--
Michael Ulm
R&D Team
ISIS Information Systems Austria
tel: +43 2236 27551-219, fax: +43 2236 21081
e-mail: michael.ulm@isis-papyrus.com
Visit our Website: www.isis-papyrus.com