wu :: forums - Print Page


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

        riddles >> medium >> Another Tiling Problem - But Even Cooler
        
(Message started by: william wu on Sep 25^th, 2003, 12:43am)

Title: Another Tiling Problem - But Even Cooler
Post by william wu on Sep 25^th, 2003, 12:43am

Another tiling problem. This time more different from the others though, I think.

Consider a gridded board of length 2ⁿ units and width 2ⁿ units, where n is any positive integer. Exactly one of the squares on this board is missing, although you don't know which square.

You have L-shaped tiles that consist of three unit side length squares: one for each leg of the L, and one for the joint. Can you cover the board with these tiles? (You don't want to cover the missing square.) Sometimes? Always? Never? Prove it.

[edit]12:50 PM 9/28/2003 Added that the squares of the L-shaped tiles are of unit side length.

Title: Re: Yet Another Tiling Problem
Post by towr on Sep 25^th, 2003, 3:45am

Yes, allways. [hide]Provable by induction.[/hide] (but I won't give it away)

Title: Re: Yet Another Tiling Problem
Post by James Fingas on Sep 25^th, 2003, 5:25am

That's a very cool puzzle.

Title: Re: Another Tiling Problem - But Even Cooler
Post by william wu on Sep 25^th, 2003, 5:53pm

Yup, pretty cool; also a good way to introduce people to a neat approach for solving problems, called ...

hint: :: [hide]divide and conquer[/hide] ::

[edit] 1:35 AM 10/22/2003 added this hint

Title: Re: Another Tiling Problem - But Even Cooler
Post by Margit Schubert-While on Sep 28^th, 2003, 4:18am

Well, I would say that the answer to the problem as stated is indeterminate. There is NO definition of the sizes of the 3 squares that make the tile. Now if you state that the size of the squares is related to "n", then that's another matter.
Margit

Title: Re: Another Tiling Problem - But Even Cooler
Post by william wu on Sep 28^th, 2003, 12:55pm

Added that the squares which compose the L-shaped tiles are of unit side length; let me know if there's anything else I can improve

Title: Re: Another Tiling Problem - But Even Cooler
Post by Barukh on Sep 28^th, 2003, 11:54pm

[smiley=blacksquare.gif]
[hide]1. Build a sequence of L-shapes L₁, L₂, ..., L_n, where L_i is a shape 2^i-1 units wide. 4 L_i-s may be combined to form an L_i+1.

2. Start tiling by putting L_n on a board so that the quadrant with the hole is left uncovered.[/hide]
[smiley=blacksquare.gif]