home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / rec / puzzles / 5280 < prev    next >
Encoding:
Internet Message Format  |  1992-07-28  |  17.2 KB
  1. Path: sparky!uunet!mcsun!uknet!acorn!armltd!dseal
  2. From: dseal@armltd.co.uk (David Seal)
  3. Newsgroups: rec.puzzles
  4. Subject: Re: Tiling a plane
  5. Message-ID: <4719@armltd.uucp>
  6. Date: 28 Jul 92 16:19:14 GMT
  7. References: <dfs.712246849@ro>
  8. Sender: dseal@armltd.uucp
  9. Distribution: rec
  10. Organization: A.R.M. Ltd, Swaffham Bulbeck, Cambs, UK
  11. Lines: 390
  12.  
  13. In article <711892126.F00001@csource.oz.au> joe@csource.oz.au (Joe Slater) writes:
  14. >A plane can be tiled with three regular geometric shapes: squares, triangles and
  15. >hexagons. It can also be tiled with pairs of shapes: hexagons and triangles, or
  16. >octagons and squares.
  17. >
  18. >Are there any other pairs that will tile a plane? What about triplets? Answers
  19. >requiring fractal-like series to fill up gaps aren't counted.
  20.  
  21. Yes, there are other pairs and some triplets. I'll look at tilings in which
  22. every vertex appears identical to every other one and all the tiles are
  23. regular polygons. For these, we can use the known formula for the angle of a
  24. regular polygon with N sides:
  25.  
  26.   angle = 180 * (1 - 2/N) degrees
  27.  
  28. Suppose 3 polygons with A, B and C sides meet at each vertex. Then we know
  29. that the angles at the vertex must add up to 360 degrees:
  30.  
  31.   180*(1-2/A) + 180*(1-2/B) + 180*(1-2/C) = 360
  32.  
  33. Dividing through by 180:
  34.  
  35.   3 - 2/A - 2/B - 2/C = 2
  36.  
  37. Or:
  38.  
  39.   2/A + 2/B + 2/C = 1
  40.  
  41. Or:
  42.  
  43.   1/A + 1/B + 1/C = 1/2
  44.  
  45. So there is a possibility of such a tiling existing for any three integers
  46. whose reciprocals add up to 1/2. It is possible to enumerate such triplets
  47. quite easily. First, by reordering the polygons, we can assume that A <= B
  48. <= C. Now we know that 1/2 = 1/A + 1/B + 1/C <= 1/A + 1/A + 1/A = 3/A, which
  49. tells us that A <= 6. Since we know that A > 2, we can split into four
  50. cases:
  51.  
  52. (1) A=3, 1/B + 1/C = 1/6. Working similarly, we can find that there are five
  53.     possibilities:
  54.  
  55.       A   B   C
  56.      -----------
  57.       3   7  42
  58.       3   8  24
  59.       3   9  18
  60.       3  10  15
  61.       3  12  12
  62.  
  63. (2) A=4, 1/B + 1/C = 1/4. This gives us three possibilities:
  64.  
  65.       A   B   C
  66.      -----------
  67.       4   5  20
  68.       4   6  12
  69.       4   8   8
  70.  
  71. (3) A=5, 1/B + 1/C = 3/10. This gives one possibility:
  72.  
  73.       A   B   C
  74.      -----------
  75.       5   5  10
  76.  
  77. (4) A=6, 1/B + 1/C = 1/3. This also gives one possibility:
  78.  
  79.       A   B   C
  80.      -----------
  81.       6   6   6
  82.  
  83. There is then one further restriction, which you will find if you try to
  84. draw some of these patterns. Consider e.g. the A=3, B=8, C=24 triplet, and
  85. start trying to draw it. So we draw a triangle, an octagon and a 24-gon
  86. meeting at one vertex. The triangle and octagon share an edge: the vertex at
  87. the other end of that edge needs a 24-gon to make it complete. But now the
  88. remaining vertex of the triangle has two 24-gons adjacent to it: the tiling
  89. doesn't work. A diagram:
  90.  
  91.  
  92.           /\             The top vertex doesn't work.
  93.   24-gon /  \ 24-gon
  94.         /    \
  95.        /      \
  96.       /Triangle\
  97.     _------------_
  98.   _-   Octagon    -_
  99.  
  100. The same thing happens in general whenever one of A, B and C is odd: if the
  101. other two are not identical, we'll get a contradiction when we try to draw
  102. the tiling around the odd-sided polygon. So we get a rule:
  103.  
  104.   If any one of A, B and C is odd, the other two must be identical.
  105.  
  106. Applying this rule to the 10 possibilities we discovered above, we find that
  107. only 4 remain possible:
  108.  
  109.       A   B   C
  110.      -----------
  111.       3  12  12
  112.       4   6  12
  113.       4   8   8
  114.       6   6   6
  115.  
  116. It's not immediately obvious that all four of these exist, but they do. The
  117. last of these is the regular tiling with hexagons; the second to last is the
  118. tiling with octagons and squares that you observed. The other two can be
  119. constructed from the hexagonal tiling:
  120.  
  121. The (3,12,12) tiling:
  122.   Start with the hexagonal tiling. Select a vertex and mark off points the
  123.   same distance out along each of the three edges that come together at that
  124.   vertex (make the distance less than half the edge length). If you join
  125.   these three points together, you will get a small equilateral triangle
  126.   centred on the original vertex, and each of the three adjacent hexagons
  127.   has had a corner chopped off, becoming an irregular heptagon.
  128.  
  129.   Repeat this at each vertex, using the same distance every time. Each
  130.   hexagon has all 6 corners chopped off to form 6 additional edges. Because
  131.   the distance was less than half of the original edge length, some of the
  132.   original edges remain, so each hexagon has become a dodecagon.
  133.   Furthermore, the angles of these dodecagons are obviously all identical,
  134.   and their edges are alternately the remains of an original hexagon edge
  135.   and a triangle edge.
  136.  
  137.   If you vary the distance you mark off along each hexagon edge from 0 to
  138.   half the original edge length, the triangle edges vary in length from 0 up
  139.   to a positive amount and the remainders of the hexagon edges vary in
  140.   length from a positive amount down to 0. For some particular choice of
  141.   marked off distance, they will be the same, and you get a tiling with
  142.   regular triangles and dodecagons. An attempt at a diagram:
  143.  
  144.              |           |           |           |
  145.             / \         / \         / \         / \
  146.     _     _-----_     _-----_     _-----_     _-----_     _
  147.      -----       -----       -----       -----       -----
  148.       \ /         \ /         \ /         \ /         \ /
  149.        |           |           |           |           |
  150.       / \         / \         / \         / \         / \
  151.     _-----_     _-----_     _-----_     _-----_     _-----_
  152.            -----       -----       -----       -----
  153.             \ /         \ /         \ /         \ / 
  154.              |           |           |           |
  155.             / \         / \         / \         / \
  156.     _     _-----_     _-----_     _-----_     _-----_     _
  157.      -----       -----       -----       -----       -----
  158.       \ /         \ /         \ /         \ /         \ /
  159.        |           |           |           |           |
  160.       / \         / \         / \         / \         / \
  161.     _-----_     _-----_     _-----_     _-----_     _-----_
  162.            -----       -----       -----       -----
  163.             \ /         \ /         \ /         \ / 
  164.              |           |           |           |
  165.  
  166. The (4,6,12) tiling:
  167.   Again, start with the hexagonal tiling. This time, place a small square
  168.   centrally on each of the edges, with two of its edges parallel to the
  169.   original edge. Join each corner of each square to its nearest neighbour on
  170.   another square: this will produce an irregular hexagon around each
  171.   original vertex and an irregular dodecagon inside each original hexagon.
  172.   However, the only way in which the hexagon and the dodecagon are irregular
  173.   are that not all their edges are the same length, and if you choose the
  174.   size of the squares correctly, this goes away and you get a tiling with
  175.   regular squares, hexagons and dodecagons. Again, an attempt at a diagram:
  176.  
  177.                    |__|              |__|              |__|
  178.      \            /    \            /    \            /    \
  179.       \          /      \          /      \          /      \
  180.       / -  __  - \      / -  __  - \      / -  __  - \      / - 
  181.      /   /    \   \ __ /   /    \   \ __ /   /    \   \ __ /   /
  182.       - /      \ -      - /      \ -      - /      \ -      - /
  183.         \      /          \      /          \      /          \
  184.          \ __ /            \ __ /            \ __ /            \
  185.           |  |              |  |              |  |              |
  186.           |__|              |__|              |__|              |
  187.          /    \            /    \            /    \            /
  188.         /      \          /      \          /      \          /
  189.       - \      / -  __  - \      / -  __  - \      / -  __  - \
  190.      \   \ __ /   /    \   \ __ /   /    \   \ __ /   /    \   \
  191.       \ -      - /      \ -      - /      \ -      - /      \ -
  192.       /          \      /          \      /          \      /
  193.      /            \ __ /            \ __ /            \ __ /
  194.     |              |  |              |  |              |  |
  195.     |              |__|              |__|              |__|
  196.      \            /    \            /    \            /    \
  197.       \          /      \          /      \          /      \
  198.       / -  __  - \      / -  __  - \      / -  __  - \      / - 
  199.      /   /    \   \ __ /   /    \   \ __ /   /    \   \ __ /   /
  200.       - /      \ -      - /      \ -      - /      \ -      - /
  201.         \      /          \      /          \      /          \
  202.          \ __ /            \ __ /            \ __ /            \
  203.           |  |              |  |              |  |              |
  204.  
  205. We can do exactly the same thing with four polygons (with A, B, C and D
  206. sides) meeting at each vertex. The equation corresponding to 1/A + 1/B + 1/C
  207. = 1/2 is now 1/A + 1/B + 1/C + 1/D = 1. Forcing A <= B <= C <= D, we get the
  208. following solutions:
  209.  
  210.    A   B   C   D
  211.   ---------------
  212.    3   3   4  12
  213.    3   3   6   6
  214.    3   4   4   6
  215.    4   4   4   4
  216.  
  217. The criteria that ensure the tiling is possible are more complicated for
  218. these, due to the fact that there is more than one possible cyclic order of
  219. the polygons around the vertex. E.g. in the first case above, the two
  220. triangles may be adjacent to each other, separated on one side by the square
  221. and the dodecagon, or opposite each other, separated on one side by the
  222. square and on the other by the dodecagon. Neither of these leads to a
  223. possible tiling on its own, by similar arguments to those that established
  224. the "if one odd, the other two are identical" rule. A more complicated
  225. argument (which I will leave as an exercise) establishes that it also isn't
  226. possible to tile the plane using both types of vertex in the tiling.
  227. However, it *is* possible to tile the plane with triangles, squares and
  228. dodecagons if we allow other types of vertex as well. For instance, if we
  229. allow six triangles to meet at a vertex, we can derive such a tiling from
  230. the (4,6,12) tiling above by splitting each hexagon into 6 equilateral
  231. triangles.
  232.  
  233. Similarly, the (3,3,6,6) vertex can have the two triangles adjacent to each
  234. other or opposite each other. Having them opposite each other leads to a
  235. completely regular tiling:
  236.  
  237.     _\____/__\____/__\____/_
  238.       \  /    \  /    \  /
  239.        \/      \/      \/
  240.        /\      /\      /\
  241.     __/__\____/__\____/__\__
  242.      /    \  /    \  /    \
  243.     /      \/      \/      \
  244.     \      /\      /\      /
  245.     _\____/__\____/__\____/_
  246.       \  /    \  /    \  /
  247.        \/      \/      \/
  248.        /\      /\      /\
  249.     __/__\____/__\____/__\__
  250.      /    \  /    \  /    \
  251.  
  252. Less regular tilings with a mixture of the two types of vertex are also
  253. possible - e.g.:
  254.  
  255.     __/__\____/__\____/__\__
  256.       \  /    \  /    \  /
  257.        \/      \/      \/
  258.        /\      /\      /\
  259.     __/__\____/__\____/__\__
  260.       \  /    \  /    \  /
  261.        \/      \/      \/
  262.        /\      /\      /\
  263.     __/__\____/__\____/__\__
  264.       \  /    \  /    \  /
  265.        \/      \/      \/
  266.        /\      /\      /\
  267.     __/__\____/__\____/__\__
  268.       \  /    \  /    \  /
  269.  
  270. For (3,4,4,6), the two squares may be adjacent or opposite each other. A
  271. completely regular tiling is possible with the squares opposite each other -
  272. it's yet another modification of the hexagonal tiling:
  273.  
  274.      |  _- \            / -_  |      |  _- \            / -_  |
  275.     _| -    \          /    - |______| -    \          /    - |_
  276.       \      \ ______ /      /        \      \ ______ /      /
  277.        \   _- |      | -_   /          \   _- |      | -_   /
  278.         \ -   |      |   - /            \ -   |      |   - /
  279.         / -_  |      |  _- \            / -_  |      |  _- \
  280.        /    - |______| -    \          /    - |______| -    \
  281.     _ /      /        \      \ ______ /      /        \      \ _
  282.      | -_   /          \   _- |      | -_   /          \   _- |
  283.      |   - /            \ -   |      |   - /            \ -   |
  284.      |  _- \            / -_  |      |  _- \            / -_  |
  285.     _| -    \          /    - |______| -    \          /    - |_
  286.       \      \ ______ /      /        \      \ ______ /      /
  287.        \   _- |      | -_   /          \   _- |      | -_   /
  288.         \ -   |      |   - /            \ -   |      |   - /
  289.         / -_  |      |  _- \            / -_  |      |  _- \
  290.        /    - |______| -    \          /    - |______| -    \
  291.     _ /      /        \      \ ______ /      /        \      \ _
  292.      | -_   /          \   _- |      | -_   /          \   _- |
  293.      |   - /            \ -   |      |   - /            \ -   |
  294.  
  295. Again, there are also tilings that mix the two types - e.g.:
  296.  
  297.            |          |      |      |      |          |
  298.       -----+_        _+------+------+------+_        _+-----
  299.           /  --_  _--  \    /        \    /  --_  _--  \
  300.       \  /      /\      \  /          \  /      /\      \
  301.        \/_     /  \     _\/            \/_     /  \     _\
  302.        /  --_ /    \ _--  \            /  --_ /    \ _--  \
  303.       /      +------+      \          /      +------+      \
  304.             /        \      \        /      /        \
  305.            /          \     _+------+_     /          \
  306.       --_ /            \ _--  \    /  --_ /            \ _--
  307.          /\            /\      \  /      /\            /\
  308.         /  \          /  \     _\/_     /  \          /  \
  309.        /    \        /    \ _--    --_ /    \        /    \
  310.       +------+------+------+          +------+------+------+
  311.       |      |      |      |          |      |      |      |
  312.       |      |      |      |          |      |      |      |
  313.       |      |      |      |          |      |      |      |
  314.       +------+------+------+_        _+------+------+------+
  315.        \    /        \    /  --_  _--  \    /        \    /
  316.         \  /          \  /      /\      \  /          \  /
  317.         _\/            \/_     /  \     _\/            \/_
  318.       --  \            /  --_ /    \ _--  \            /  --
  319.            \          /      +------+      \          /
  320.             \        /      /        \      \        /
  321.       \     _+------+_     /          \     _+------+_     /
  322.        \ _--  \    /  --_ /            \ _--  \    /  --_ /
  323.        /\      \  /      /\            /\      \  /      /\
  324.       /  \     _\/_     /  \          /  \     _\/_     /  \
  325.           \ _--    --_ /    \        /    \ _--    --_ /
  326.       -----+          +------+------+------+          +-----
  327.            |          |      |      |      |          |
  328.  
  329. The (4,4,4,4) is of course the normal tiling with squares.
  330.  
  331. For 5 tiles meeting at a vertex, the formula becomes 1/A + 1/B + 1/C + 1/D +
  332. 1/E = 3/2. With the usual re-ordering, this has two solutions:
  333.  
  334.    A   B   C   D   E
  335.   -------------------
  336.    3   3   3   3   6
  337.    3   3   3   4   4
  338.  
  339. Both of these lead to completely regular tilings. The completely regular
  340. (3,3,3,3,6) tiling is interesting because it is "skew" - i.e. it is not the
  341. same as its mirror image:
  342.  
  343.   /____\/____\/____\/          \/____\ ____ /____\
  344.   \    /      \    /\          /\    /\    /\    /
  345.    \  /        \  /  \        /  \  /  \  /  \  /
  346.   __\/          \/____\ ____ /____\/____\/____\/
  347.     /\          /\    /\    /\    /      \    /\
  348.    /  \        /  \  /  \  /  \  /        \  /  \
  349.   /____\ ____ /____\/____\/____\/          \/____\
  350.   \    /\    /\    /      \    /\          /\    /
  351.    \  /  \  /  \  /        \  /  \        /  \  /
  352.   __\/____\/____\/          \/____\ ____ /____\/__
  353.     /      \    /\          /\    /\    /\    / 
  354.    /        \  /  \        /  \  /  \  /  \  /   
  355.   /          \/____\ ____ /____\/____\/____\/     
  356.   \          /\    /\    /\    /      \    /\     
  357.    \        /  \  /  \  /  \  /        \  /  \   
  358.   __\ ____ /____\/____\/____\/          \/____\ __
  359.     /\    /\    /      \    /\          /\    /\
  360.    /  \  /  \  /        \  /  \        /  \  /  \
  361.   /____\/____\/          \/____\ ____ /____\/____\
  362.         \    /\          /\    /\    /\    /      
  363.          \  /  \        /  \  /  \  /  \  /      
  364.           \/____\ ____ /____\/____\/____\/        
  365.           /\    /\    /\    /      \    /\      
  366.          /  \  /  \  /  \  /        \  /  \      
  367.    ____ /____\/____\/____\/          \/____\ ____ 
  368.   \    /\    /      \    /\          /\    /\    /
  369.  
  370. There are two completely regular (3,3,3,4,4) tilings - I'll leave people to
  371. investigate these for themselves.
  372.  
  373. With 6 polygons meeting at a vertex, the only solution is obviously that all
  374. six polygons are triangles, and we get the standard triangular tiling, and
  375. it is clearly impossible to produce such tilings with 7 or more polygons
  376. meeting at a vertex.
  377.  
  378. So to summarise, the possibilities for these tilings (all polygons regular,
  379. all vertices appear exactly the same) are:
  380.  
  381. A) A triangle and two dodecagons meet at each vertex.
  382. B) A square, a hexagon and a dodecagon meet at each vertex.
  383. C) A square and two octagons meet at each vertex.
  384. D) Three hexagons meet at each vertex.
  385. E) Two triangles and two hexagons meet at each vertex.
  386. F) A triangle, two squares and a hexagon meet at each vertex.
  387. G) Four squares meet at each vertex.
  388. H) Four triangles and a hexagon meet at each vertex.
  389. I) Three triangles and two squares meet at each vertex (two variants)
  390. J) Six triangles meet at each vertex.
  391.  
  392. If you don't require all vertices to appear exactly the same, many more
  393. combinations are possible. E.g. it is possible to tile the plane with a
  394. combination of triangles, squares, hexagons and dodecagons, by taking tiling
  395. B) above and splitting some of the hexagons into six triangles (or some of
  396. the dodecagons into six triangles, six squares and a hexagon, which is also
  397. possible).
  398.  
  399. David Seal
  400. dseal@armltd.co.uk
  401.  
  402. All opinions are mine only...
  403.