# Trominoes Induction Pf?

• Sep 29th 2006, 09:48 PM
harold
Trominoes Induction Pf?
Hi guys,

Help...!!!

Prove by induction why a "3 by odd" tiling of trominoes won't work.
Also, prove by induction why a 2^k by 2^k tiling of trominoes WOULD work.
• Sep 30th 2006, 12:23 AM
CaptainBlack
Quote:

Originally Posted by harold
Hi guys,

Help...!!!

Prove by induction why a "3 by odd" tiling of trominoes won't work.
Also, prove by induction why a 2^k by 2^k tiling of trominoes WOULD work.

You had better tell us what you mean by trominoes, and what
restrictions there are on how you do the tillings.

RonL
• Sep 30th 2006, 10:33 AM
Soroban
Hello, harold!

Quote:

Prove by induction why a "3 by odd" tiling of trominoes won't work.
Also, prove by induction why a 2^k by 2^k tiling of trominoes WOULD work.

If a tromino is a three-unit polyomino (as defined by Solomon W. Golomb),
. . there are two possible shapes.
Code:

```      *---*       |  |       * - *---*      *---*---*---*       |  :  |      |  :  :  |       *---*---*      *---*---*---*         "L"              "I"```

I must be missing something . . . I don't understand the questions.

A "3 by odd" can be tiled with a number of I-trominos.

And a "2^k by 2^k" region has 4^k square units
. . which can not be a multiple of 3.

• Sep 30th 2006, 10:40 AM
harold
I'm not sure either...this is a page that talks about trominoes and gives some induction but I still don't get it...

A Geometric Induction Example: the Tromino Puzzle
• Sep 30th 2006, 04:17 PM
Soroban
Hello again, Harold!

It would have helped if you had explained the problems clearly.

First of all, we're limited to the L-shaped tromino.

Secondly, for the tiling of a "2^n by 2^n" square, you neglected to tell us
. . that one unit square is already covered.

• Oct 1st 2006, 03:14 PM
harold
Sorry bout that Soroban...I didn't know myself--new territory for me. I see what they're getting at with the discussion about the induction but how do I formally write it out for both cases??