From: Michael Ulm Date: 2005-05-20T23:18:46+09:00 Subject: Re: [QUIZ] Tiling Turmoil (#33) Adriano Ferreira wrote: > On 5/20/05, Jason Bailey 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