[seqfan] Re: L-reptiles

[Benoît Jubin]

Thanks David for this proof (below) of the impossibility of a
replicate tiling of an L with three pieces.  It inspired me to provide
an almost proof for 5 pieces:
If the original "L" is composed of three squares of side 1, as follows:
A
BC
then every tile touching the top edge of A (say there are T of them)
is actually included in A (because all sides of all pieces are
necessarily horizontal or vertical...), and similarly
every tile touching the right edge of C (say there are R of them) is
included in C.  Now any region containing B cannot be covered by a
unique tile (such a tile would cover all of the original L...).
Therefore R+T<=3.
By symmetry, we can assume 1<=R<=T. So the only possibility is R=1 and
T=2.  The region not covered by these three tiles is of the form
bb
bbc
or
bbc
bb
(where the four b's cover the initial B) plus a part of the inital A.
It has to be covered by two tiles.  One of these two tiles has to be
b
bc
or
bc
b
respectively, and the remaining region is not L-shaped.
This was long yet non-rigorous...  What is frustrating is that we
"see" such tilings are clearly "very" impossible, yet I cannot use all
the constraints in an efficient way.
Benoit

On Mon, Apr 12, 2010 at 5:01 PM, David Wilson <davidwwilson at comcast.net> wrote:
> 3 is not hard to disprove.
>
>
> Let A be the area to be tiled, oriented like an L. A then has short top and
> right edges.
>
> The only way that a tile can abut both top and right edges of A is if it is
> congrent to A, not 3 tiles.
>
> Let R be the number of tiles against the right edge, and T the number
> against the top edge of A.
>
> Since each edge must be tiled, R >= 1 and T >= 1.
>
> Since right and top edges cannot abut the same tile, R+T <= 3.
>
> By symmetry symmetry of A, we can assume R <= T wlog.
>
> This gives us the following possibilities:
>
> R = 1, T = 2. This does not cover A.
>
> R = 1, T = 1. No matter how we place the two tiles, the remaining area is
> not L-shaped.
>
> QED.
>
>
> ----- Original Message ----- From: "Benoīt Jubin" <benoit.jubin at gmail.com>
> To: "Sequence Fanatics Discussion list" <seqfan at list.seqfan.eu>
> Sent: Monday, April 12, 2010 2:49 PM
> Subject: [seqfan] Re: L-reptiles
>
>
> After several attempts, I think there is no replicate tiling of the
> "L" shape with 8 pieces, but I have no proof of this.  Actually, I
> have no proof of this impossibility for 3 and 5 pieces neither.  How
> do you prove such things ?  Here is a proof for 2 pieces (which is
> geometrically obvious...), but this method would give lengthy and
> inelegant proofs (if any) for more pieces.
>
>
>