32

Recently my sister-in-law, who is training to become a high school mathematics teacher, asked me the following question:

Consider the following polygon constructed by adjoining three squares of equal area. (Aka, a "tromino".) Determine a method of subdividing this polygon into four congruent polygons.

enter image description here

After a some minutes, I came up with what I think is the most obvious answer (my apologies for my scribbled drawings).

(SPOILER!)

enter image description here

In retrospect, this is an intuitive answer because it consists of constructing the subdivisions by rescaling the original polygon and applying a Euclidean isometry to the result. To my great dismay, I can't think of another answer.

Question. How many answers are there to the question posed by my sister-in-law? If the answer above is unique, is it easily provable, and what is the proof?

Addendum. I'd also be interested if there were a tiling of the tromino consisting of four congruent, connected parts that are not necessarily polygons.

joshphysics
  • 1,821
  • 5
    FYI: This is an example of a "rep-tile" (that is, a "replicating-tile"). They're pretty nifty ... especially for how they lead nicely into the notion of self-similar fractals. – Blue Sep 03 '15 at 23:47
  • @Blue Very cool! Thanks for the terminology. I hope someone on math.SE is a rep-tile master. – joshphysics Sep 03 '15 at 23:49
  • I don't know if anyone here is, but Martin Gardner published much about them in his Mathematic Games columns in Scientific American. – Paul Sinclair Sep 04 '15 at 00:23
  • It's a quick exercise in cases to show that this is the only tiling of the ell by four shapes congruent to it and half its size. If the question is whether there's any other shape such that the ell can be split into four copies of that shape, I seem to remember that there is but I'll have to hunt it down. – Steven Stadnicki Sep 04 '15 at 01:12
  • @StevenStadnicki I'm asking the second question. Perhaps I'll make an edit to make that more clear, thanks. – joshphysics Sep 04 '15 at 02:13
  • Without thinking about it to hard, you essentially used Golomb's inductive proof of a tromino theorem to solve this problem. He was the person who coined the term tromino. http://people.rit.edu/mecsma/Professional/Puzzles/Pentominoes/P-Intro.html Martin Gardner attributed much of the games Paul talked about in SA. I'll try my hand at this problem but I need to think about it first. – jake mckenzie Sep 12 '15 at 07:28
  • @jakemckenzie Would you happen to know if anyone has studied tilings of polyominoes themselves as opposed to using polyominoes to tile other regions? – joshphysics Sep 14 '15 at 00:07
  • Would it be cheating to tile the L-Tronimo with non-connected polygons, or self-intersecting polygons (like a bow-tie)? See this image on wikipedia for some examples of what I am talking about. – Mike Pierce Sep 14 '15 at 16:46
  • @MikePierce If I understand your suggestion correctly, I'd consider that cheating. You should be able to cut along the boundaries between the subdivisions with scissors and obtain three congruent shapes without any extra left over. Am I interpreting your suggestion correctly? – joshphysics Sep 14 '15 at 17:38
  • @joshphysics Yeah I think you are interpreting my suggestion correctly. I'm really asking if something like the last packing in Jon Mark Perry's answer is valid, or if you would consider a shape like $\bowtie$ a polygon (since it can be thought of as a self-intersecting rectangle). – Mike Pierce Sep 14 '15 at 18:38
  • @MikePierce Oh gotcha. Yeah I would consider Jon Mark Perry's answer cheating. I'd be interested in a solution using something like the bowtie, but I don't think such a solution would be in line with the spirit of the original question. – joshphysics Sep 14 '15 at 18:42
  • The problem, with the pieces required only to be similar, not congruent, was asked at http://www.mathpuzzle.com/mine.html where there is a link to several answers. – Gerry Myerson Sep 17 '15 at 13:54
  • @GerryMyerson the conditions at http://www.mathpuzzle.com/mine.html say the pieces should be "solidly connected", I guess that means the interior is connected. – GEdgar Sep 18 '15 at 12:43

3 Answers3

24

Long ago my father came up with this one. Whether these pieces are "connected" depends on whether or not the pieces include their boundaries.

diagram

added
With Jon's method we can get a lot of these. And connected (if counting the boundary).

diagram2

GEdgar
  • 111,679
  • Nice. I wonder if there are an infinite number of these by modifying this slightly? – Colm Bhandal Sep 17 '15 at 14:33
  • you can swap the red/yellow, blue/green triangles for one – JMP Sep 17 '15 at 15:53
  • +1 This is clever. If it also answered the original polygons version, then I'd award your dad the bounty. Maybe I should anyway...I don't anticipate anyone proving it can't be done in another way with four polygons or coming up with another solution. – joshphysics Sep 17 '15 at 15:59
  • in fact if you cut the middle out of a triangle and embed it in its opposite (same with the rectangles) you get a fair few – JMP Sep 17 '15 at 16:17
  • I don't suppose you have an idea of how to do this if boundaries are excluded or an opinion on whether a solution besides the one I originally came up with is possible? – joshphysics Sep 17 '15 at 21:28
  • 3
    according to 4CT boundaries AREN'T connected - consider a n-pie chart - all regions are connected in the middle – JMP Sep 18 '15 at 05:00
  • 2
    Good observation Jon. I have thought about this further. I feel that a "true" solution should let you cut along the boundaries with a knife and obtain 4 congruent pieces. – Colm Bhandal Sep 18 '15 at 10:52
  • Perhaps this was addressed, but if you consider subdividing the rectangle into 4 pieces, each of which is a subset of $\mathbb{R}^2$, then two of these will not be connected. – Eric Naslund Nov 17 '15 at 16:52
4

No Convex Solutions with 8 or more sides

Theorem: The tromino cannot be tiled by convex tiles each of which has at least 8 sides.

Proof: Notice that a convex tile can have at most two vertical sides and at most two horizontal sides. Notice also that the sides of the tromino sides are all either vertical or horizontal. Now, let's assume towards a contradiction that a convex tiling exists, where all tiles have $8$ or more sides. Focus on any tile- call it $T$ so we can refer to it later. Since at most $4$ of its sides are either vertical or horizontal, at least $4$ of its sides must be neither vertical nor horizontal, and so must cross the interior of the tromino. Now, notice that for each such side, there must be at least one other tile adjacent to $T$ sharing this side. But all of these adjacent tiles must be distinct. Otherwise, by convexity we could draw a line through the interior of $T$ that is also in the interior of one of the other shapes. But the distinctness of these shapes implies that there at least $5$ tiles in total, contradicting the fact that we are only focused on $4$-tilings.

Notes: I believe this proof can be massively strengthened by someone with intelligence, patience and time. I would be delighted if someone could carry my ideas further.

There are no Convex Solutions

Update: As correctly pointed out in the comments below, this proof is $\color{red}{\text{incorrect}}$. It fails to consider the case where a convex green region remains. I am desperately working to patch up my shameful error. I leave this failed, miserable attempt up in the hope that it may rise from the ashes like the mythical bird, the phoenix.

Theorem: The tromino cannot be tiled by convex tiles.

Proof: Notice that the tromino is made of $3$ squares. For simplicity, let's assume they are unit squares. Then all tiles have area $\frac34$. Now, look at the rectangle in the bottom right hand corner of the tromino of length $1$ and breadth $\frac34$; call it $R$. $R$ has area $\frac34$, so it is a possible candidate for tiling. But it can easily be observed that no tiling with $R$ is possible.

Rectangular tile in the bottom right of the Tromino

Now, keep your focus on that bottom right region whose shape is $R$. Because there is no tiling with $R$, clearly there must be a tile crossing the left side of this region- otherwise the tile shape would just be $R$. Note that this must hold in any tiling. In the below I try to depict this in general, which is difficult, using a yellow ellipse to represent the tile crossing the line into the region $R$:

enter image description here

Now, assuming the tiles are convex, the remainder of the region $R$ that is to be tiled is concave*. So it cannot be tiled with a single convex tile. At least $2$ must be used. But notice that the tromino is self-similar. So all of the above must also apply to the top-left corner. Which means at least $1 + 2 + 2 = 5$ tiles will be needed, breaking the rule that there are only $4$ tiles.

*Note that the special case where the remainder of $R$ is convex can only be satisfied if this remainder is disconnected from the rest of the tromino. But then the area would be less than $\frac34$, and so is impossible to tile.

I realise that convexity may be a bit of a strong assumption, but I believe there are ideas here that can be carried further. If anyone wants a proof of the impossibility of a tiling by $R$, please comment and I will add it.

Colm Bhandal
  • 4,649
  • This is proof by wishful thinking, I'm afraid! What if the yellow region is a trapezoid, whose parallel sides are extensions of the top and bottom sides of $R$? Then the remainder of $R$ can be convex. – TonyK Sep 21 '15 at 22:40
  • @TonyK- correct. I will note that in the answer. I still think it can be proved roughly this way, but I'll need to use more methods obviously. – Colm Bhandal Sep 22 '15 at 11:41
2

The first part is true. First consider the possibilities for positioning the tromino in the lower right corner:

tromino1

The first two obviously don't work, the second two lead to:

tromino2

of which only the second has a solution:

tromino7

There is another packing:

tromino3

For connected packings we have that the axis of symmetry for the tromino can be crossed $0$, $2$ or $4$ times. An odd crossing number partitions the tromino into $2$ with an odd number of 'polytroms' left over.

tromino4

With $0$ crossing we would have to partition the trapezoid, but as this shape has no axis of symmetry, reflective or rotational, this is impossible.

tromino5

tromino6

With $4$ crossings, we are very limited as to options.

With $2$ crossings, we have your original and my disconnected versions. Others seem very remote due to various arguments of constraints and symmetries.

JMP
  • 21,771
  • 2
    This is nice if one wants an analysis of the tiling of the tromino by trominos, but that's not ultimately what the question is about. I'm asking if there is a tiling by another shape. – joshphysics Sep 09 '15 at 06:14
  • @joshphysics, it would be good to specify in your question that the shape needs to be connected. The packing here is tiled by exactly four congruent copies of the same shape, where the shape consists of three disconnected squares. – Mike Pierce Sep 14 '15 at 16:55
  • @MikePierce I'll make the appropriate edit. Thanks. – joshphysics Sep 14 '15 at 17:39
  • @MikePierce I don't think disconnected squares qualify as a polygon. – Rick Sep 14 '15 at 17:43
  • @Rick To be fair to Mike, I did mention "parts" in my addendum. – joshphysics Sep 14 '15 at 17:44
  • +1. OP considers the packing-by-disconnected-pieces "cheating", but I find it a clever outside-the-box interpretation of the problem. (I find the later discussion of "limited" and/or "remote" possibilities for solutions --to the extent this discussion is an expression of futility-- unconvincing.) – Blue Sep 17 '15 at 05:24
  • @Blue; OP changed the Q since I posted the original answer - it did fit the original q's requirement. wrt the packings, 4 crossings does have very limited possibilities, i'm looking into tightening the rest, but it does seem impossible to find another packing, connected or not. – JMP Sep 17 '15 at 05:28
  • "An odd crossing number partitions the tromino into 2 with an odd number of 'polytroms' left over." - I can see how this argument works to exclude a crossing number of 1: from an argument of area. But what above a crossing number of 3? What if $\frac23$ of each 'polytrom' is on one side (and so $\frac13$ is on the other)- the area argument doesn't work. Am I missing something? Can you elaborate in your answer please? Thanks! – Colm Bhandal Sep 17 '15 at 10:34
  • @ColmBhandal; with 3 crossings you need to fill one leg of the L leaving the other with a hole – JMP Sep 17 '15 at 11:36
  • I do not follow. How do you know the hole isn't already filled by the 3 tiles crossing the axis? A picture would be nice at this point. – Colm Bhandal Sep 17 '15 at 12:43
  • Also, in general, the same polygon might cross the axis many times. Polygons can be as complex as we want them to be: concave with many, many sides. – Colm Bhandal Sep 17 '15 at 12:47
  • @ColmBhandal; the last point wouldn't matter - it's the number of polygons that cross - i'll make an edit. if 3 polygons cross, then the axis is covered, so there must be a hole somewhere, and it can't (apparently) be on both sides of the axis) – JMP Sep 17 '15 at 12:51
  • Let us continue this discussion in chat. – Colm Bhandal Sep 17 '15 at 12:56