From: dseal@armltd.co.uk (David Seal)
Newsgroups: rec.puzzles
Subject: Re: Tiling a plane
Date: 28 Jul 92 16:19:14 GMT
Distribution: rec
Organization: A.R.M. Ltd, Swaffham Bulbeck, Cambs, UK

In article <711892126.F00001@csource.oz.au> joe@csource.oz.au (Joe Slater) writes:
>A plane can be tiled with three regular geometric shapes: squares, triangles and
>hexagons. It can also be tiled with pairs of shapes: hexagons and triangles, or
>octagons and squares.
>
>Are there any other pairs that will tile a plane? What about triplets? Answers
>requiring fractal-like series to fill up gaps aren't counted.

Yes, there are other pairs and some triplets. I'll look at tilings in which
every vertex appears identical to every other one and all the tiles are
regular polygons. For these, we can use the known formula for the angle of a
regular polygon with N sides:

  angle = 180 * (1 - 2/N) degrees

Suppose 3 polygons with A, B and C sides meet at each vertex. Then we know
that the angles at the vertex must add up to 360 degrees:

  180*(1-2/A) + 180*(1-2/B) + 180*(1-2/C) = 360

Dividing through by 180:

  3 - 2/A - 2/B - 2/C = 2

Or:

  2/A + 2/B + 2/C = 1

Or:

  1/A + 1/B + 1/C = 1/2

So there is a possibility of such a tiling existing for any three integers
whose reciprocals add up to 1/2. It is possible to enumerate such triplets
quite easily. First, by reordering the polygons, we can assume that A <= B
<= C. Now we know that 1/2 = 1/A + 1/B + 1/C <= 1/A + 1/A + 1/A = 3/A, which
tells us that A <= 6. Since we know that A > 2, we can split into four
cases:

(1) A=3, 1/B + 1/C = 1/6. Working similarly, we can find that there are five
    possibilities:

      A   B   C
     -----------
      3   7  42
      3   8  24
      3   9  18
      3  10  15
      3  12  12

(2) A=4, 1/B + 1/C = 1/4. This gives us three possibilities:

      A   B   C
     -----------
      4   5  20
      4   6  12
      4   8   8

(3) A=5, 1/B + 1/C = 3/10. This gives one possibility:

      A   B   C
     -----------
      5   5  10

(4) A=6, 1/B + 1/C = 1/3. This also gives one possibility:

      A   B   C
     -----------
      6   6   6

There is then one further restriction, which you will find if you try to
draw some of these patterns. Consider e.g. the A=3, B=8, C=24 triplet, and
start trying to draw it. So we draw a triangle, an octagon and a 24-gon
meeting at one vertex. The triangle and octagon share an edge: the vertex at
the other end of that edge needs a 24-gon to make it complete. But now the
remaining vertex of the triangle has two 24-gons adjacent to it: the tiling
doesn't work. A diagram:


          /\             The top vertex doesn't work.
  24-gon /  \ 24-gon
        /    \
       /      \
      /Triangle\
    _------------_
  _-   Octagon    -_

The same thing happens in general whenever one of A, B and C is odd: if the
other two are not identical, we'll get a contradiction when we try to draw
the tiling around the odd-sided polygon. So we get a rule:

  If any one of A, B and C is odd, the other two must be identical.

Applying this rule to the 10 possibilities we discovered above, we find that
only 4 remain possible:

      A   B   C
     -----------
      3  12  12
      4   6  12
      4   8   8
      6   6   6

It's not immediately obvious that all four of these exist, but they do. The
last of these is the regular tiling with hexagons; the second to last is the
tiling with octagons and squares that you observed. The other two can be
constructed from the hexagonal tiling:

The (3,12,12) tiling:
  Start with the hexagonal tiling. Select a vertex and mark off points the
  same distance out along each of the three edges that come together at that
  vertex (make the distance less than half the edge length). If you join
  these three points together, you will get a small equilateral triangle
  centred on the original vertex, and each of the three adjacent hexagons
  has had a corner chopped off, becoming an irregular heptagon.

  Repeat this at each vertex, using the same distance every time. Each
  hexagon has all 6 corners chopped off to form 6 additional edges. Because
  the distance was less than half of the original edge length, some of the
  original edges remain, so each hexagon has become a dodecagon.
  Furthermore, the angles of these dodecagons are obviously all identical,
  and their edges are alternately the remains of an original hexagon edge
  and a triangle edge.

  If you vary the distance you mark off along each hexagon edge from 0 to
  half the original edge length, the triangle edges vary in length from 0 up
  to a positive amount and the remainders of the hexagon edges vary in
  length from a positive amount down to 0. For some particular choice of
  marked off distance, they will be the same, and you get a tiling with
  regular triangles and dodecagons. An attempt at a diagram:

             |           |           |           |
            / \         / \         / \         / \
    _     _-----_     _-----_     _-----_     _-----_     _
     -----       -----       -----       -----       -----
      \ /         \ /         \ /         \ /         \ /
       |           |           |           |           |
      / \         / \         / \         / \         / \
    _-----_     _-----_     _-----_     _-----_     _-----_
           -----       -----       -----       -----
            \ /         \ /         \ /         \ / 
             |           |           |           |
            / \         / \         / \         / \
    _     _-----_     _-----_     _-----_     _-----_     _
     -----       -----       -----       -----       -----
      \ /         \ /         \ /         \ /         \ /
       |           |           |           |           |
      / \         / \         / \         / \         / \
    _-----_     _-----_     _-----_     _-----_     _-----_
           -----       -----       -----       -----
            \ /         \ /         \ /         \ / 
             |           |           |           |

The (4,6,12) tiling:
  Again, start with the hexagonal tiling. This time, place a small square
  centrally on each of the edges, with two of its edges parallel to the
  original edge. Join each corner of each square to its nearest neighbour on
  another square: this will produce an irregular hexagon around each
  original vertex and an irregular dodecagon inside each original hexagon.
  However, the only way in which the hexagon and the dodecagon are irregular
  are that not all their edges are the same length, and if you choose the
  size of the squares correctly, this goes away and you get a tiling with
  regular squares, hexagons and dodecagons. Again, an attempt at a diagram:

                   |__|              |__|              |__|
     \            /    \            /    \            /    \
      \          /      \          /      \          /      \
      / -  __  - \      / -  __  - \      / -  __  - \      / - 
     /   /    \   \ __ /   /    \   \ __ /   /    \   \ __ /   /
      - /      \ -      - /      \ -      - /      \ -      - /
        \      /          \      /          \      /          \
         \ __ /            \ __ /            \ __ /            \
          |  |              |  |              |  |              |
          |__|              |__|              |__|              |
         /    \            /    \            /    \            /
        /      \          /      \          /      \          /
      - \      / -  __  - \      / -  __  - \      / -  __  - \
     \   \ __ /   /    \   \ __ /   /    \   \ __ /   /    \   \
      \ -      - /      \ -      - /      \ -      - /      \ -
      /          \      /          \      /          \      /
     /            \ __ /            \ __ /            \ __ /
    |              |  |              |  |              |  |
    |              |__|              |__|              |__|
     \            /    \            /    \            /    \
      \          /      \          /      \          /      \
      / -  __  - \      / -  __  - \      / -  __  - \      / - 
     /   /    \   \ __ /   /    \   \ __ /   /    \   \ __ /   /
      - /      \ -      - /      \ -      - /      \ -      - /
        \      /          \      /          \      /          \
         \ __ /            \ __ /            \ __ /            \
          |  |              |  |              |  |              |

We can do exactly the same thing with four polygons (with A, B, C and D
sides) meeting at each vertex. The equation corresponding to 1/A + 1/B + 1/C
= 1/2 is now 1/A + 1/B + 1/C + 1/D = 1. Forcing A <= B <= C <= D, we get the
following solutions:

   A   B   C   D
  ---------------
   3   3   4  12
   3   3   6   6
   3   4   4   6
   4   4   4   4

The criteria that ensure the tiling is possible are more complicated for
these, due to the fact that there is more than one possible cyclic order of
the polygons around the vertex. E.g. in the first case above, the two
triangles may be adjacent to each other, separated on one side by the square
and the dodecagon, or opposite each other, separated on one side by the
square and on the other by the dodecagon. Neither of these leads to a
possible tiling on its own, by similar arguments to those that established
the "if one odd, the other two are identical" rule. A more complicated
argument (which I will leave as an exercise) establishes that it also isn't
possible to tile the plane using both types of vertex in the tiling.
However, it *is* possible to tile the plane with triangles, squares and
dodecagons if we allow other types of vertex as well. For instance, if we
allow six triangles to meet at a vertex, we can derive such a tiling from
the (4,6,12) tiling above by splitting each hexagon into 6 equilateral
triangles.

Similarly, the (3,3,6,6) vertex can have the two triangles adjacent to each
other or opposite each other. Having them opposite each other leads to a
completely regular tiling:

    _\____/__\____/__\____/_
      \  /    \  /    \  /
       \/      \/      \/
       /\      /\      /\
    __/__\____/__\____/__\__
     /    \  /    \  /    \
    /      \/      \/      \
    \      /\      /\      /
    _\____/__\____/__\____/_
      \  /    \  /    \  /
       \/      \/      \/
       /\      /\      /\
    __/__\____/__\____/__\__
     /    \  /    \  /    \

Less regular tilings with a mixture of the two types of vertex are also
possible - e.g.:

    __/__\____/__\____/__\__
      \  /    \  /    \  /
       \/      \/      \/
       /\      /\      /\
    __/__\____/__\____/__\__
      \  /    \  /    \  /
       \/      \/      \/
       /\      /\      /\
    __/__\____/__\____/__\__
      \  /    \  /    \  /
       \/      \/      \/
       /\      /\      /\
    __/__\____/__\____/__\__
      \  /    \  /    \  /

For (3,4,4,6), the two squares may be adjacent or opposite each other. A
completely regular tiling is possible with the squares opposite each other -
it's yet another modification of the hexagonal tiling:

     |  _- \            / -_  |      |  _- \            / -_  |
    _| -    \          /    - |______| -    \          /    - |_
      \      \ ______ /      /        \      \ ______ /      /
       \   _- |      | -_   /          \   _- |      | -_   /
        \ -   |      |   - /            \ -   |      |   - /
        / -_  |      |  _- \            / -_  |      |  _- \
       /    - |______| -    \          /    - |______| -    \
    _ /      /        \      \ ______ /      /        \      \ _
     | -_   /          \   _- |      | -_   /          \   _- |
     |   - /            \ -   |      |   - /            \ -   |
     |  _- \            / -_  |      |  _- \            / -_  |
    _| -    \          /    - |______| -    \          /    - |_
      \      \ ______ /      /        \      \ ______ /      /
       \   _- |      | -_   /          \   _- |      | -_   /
        \ -   |      |   - /            \ -   |      |   - /
        / -_  |      |  _- \            / -_  |      |  _- \
       /    - |______| -    \          /    - |______| -    \
    _ /      /        \      \ ______ /      /        \      \ _
     | -_   /          \   _- |      | -_   /          \   _- |
     |   - /            \ -   |      |   - /            \ -   |

Again, there are also tilings that mix the two types - e.g.:

           |          |      |      |      |          |
      -----+_        _+------+------+------+_        _+-----
          /  --_  _--  \    /        \    /  --_  _--  \
      \  /      /\      \  /          \  /      /\      \
       \/_     /  \     _\/            \/_     /  \     _\
       /  --_ /    \ _--  \            /  --_ /    \ _--  \
      /      +------+      \          /      +------+      \
            /        \      \        /      /        \
           /          \     _+------+_     /          \
      --_ /            \ _--  \    /  --_ /            \ _--
         /\            /\      \  /      /\            /\
        /  \          /  \     _\/_     /  \          /  \
       /    \        /    \ _--    --_ /    \        /    \
      +------+------+------+          +------+------+------+
      |      |      |      |          |      |      |      |
      |      |      |      |          |      |      |      |
      |      |      |      |          |      |      |      |
      +------+------+------+_        _+------+------+------+
       \    /        \    /  --_  _--  \    /        \    /
        \  /          \  /      /\      \  /          \  /
        _\/            \/_     /  \     _\/            \/_
      --  \            /  --_ /    \ _--  \            /  --
           \          /      +------+      \          /
            \        /      /        \      \        /
      \     _+------+_     /          \     _+------+_     /
       \ _--  \    /  --_ /            \ _--  \    /  --_ /
       /\      \  /      /\            /\      \  /      /\
      /  \     _\/_     /  \          /  \     _\/_     /  \
          \ _--    --_ /    \        /    \ _--    --_ /
      -----+          +------+------+------+          +-----
           |          |      |      |      |          |

The (4,4,4,4) is of course the normal tiling with squares.

For 5 tiles meeting at a vertex, the formula becomes 1/A + 1/B + 1/C + 1/D +
1/E = 3/2. With the usual re-ordering, this has two solutions:

   A   B   C   D   E
  -------------------
   3   3   3   3   6
   3   3   3   4   4

Both of these lead to completely regular tilings. The completely regular
(3,3,3,3,6) tiling is interesting because it is "skew" - i.e. it is not the
same as its mirror image:

  /____\/____\/____\/          \/____\ ____ /____\
  \    /      \    /\          /\    /\    /\    /
   \  /        \  /  \        /  \  /  \  /  \  /
  __\/          \/____\ ____ /____\/____\/____\/
    /\          /\    /\    /\    /      \    /\
   /  \        /  \  /  \  /  \  /        \  /  \
  /____\ ____ /____\/____\/____\/          \/____\
  \    /\    /\    /      \    /\          /\    /
   \  /  \  /  \  /        \  /  \        /  \  /
  __\/____\/____\/          \/____\ ____ /____\/__
    /      \    /\          /\    /\    /\    / 
   /        \  /  \        /  \  /  \  /  \  /   
  /          \/____\ ____ /____\/____\/____\/     
  \          /\    /\    /\    /      \    /\     
   \        /  \  /  \  /  \  /        \  /  \   
  __\ ____ /____\/____\/____\/          \/____\ __
    /\    /\    /      \    /\          /\    /\
   /  \  /  \  /        \  /  \        /  \  /  \
  /____\/____\/          \/____\ ____ /____\/____\
        \    /\          /\    /\    /\    /      
         \  /  \        /  \  /  \  /  \  /      
          \/____\ ____ /____\/____\/____\/        
          /\    /\    /\    /      \    /\      
         /  \  /  \  /  \  /        \  /  \      
   ____ /____\/____\/____\/          \/____\ ____ 
  \    /\    /      \    /\          /\    /\    /

There are two completely regular (3,3,3,4,4) tilings - I'll leave people to
investigate these for themselves.

With 6 polygons meeting at a vertex, the only solution is obviously that all
six polygons are triangles, and we get the standard triangular tiling, and
it is clearly impossible to produce such tilings with 7 or more polygons
meeting at a vertex.

So to summarise, the possibilities for these tilings (all polygons regular,
all vertices appear exactly the same) are:

A) A triangle and two dodecagons meet at each vertex.
B) A square, a hexagon and a dodecagon meet at each vertex.
C) A square and two octagons meet at each vertex.
D) Three hexagons meet at each vertex.
E) Two triangles and two hexagons meet at each vertex.
F) A triangle, two squares and a hexagon meet at each vertex.
G) Four squares meet at each vertex.
H) Four triangles and a hexagon meet at each vertex.
I) Three triangles and two squares meet at each vertex (two variants)
J) Six triangles meet at each vertex.

If you don't require all vertices to appear exactly the same, many more
combinations are possible. E.g. it is possible to tile the plane with a
combination of triangles, squares, hexagons and dodecagons, by taking tiling
B) above and splitting some of the hexagons into six triangles (or some of
the dodecagons into six triangles, six squares and a hexagon, which is also
possible).

David Seal
dseal@armltd.co.uk

All opinions are mine only...
Newsgroups: rec.puzzles