[seqfan] Re: L-reptiles
Benoît Jubin
benoit.jubin at gmail.com
Tue Apr 13 03:50:05 CEST 2010
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.
>
>
>
More information about the SeqFan
mailing list