home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10217 < prev    next >
Encoding:
Text File  |  1992-08-13  |  2.6 KB  |  78 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!mcsun!Germany.EU.net!news.uni-bielefeld.de!umatf071
  3. From: umatf071@unibi.uni-bielefeld.de (0105)
  4. Subject: Re: A Word-Problem
  5. Message-ID: <1992Aug13.135704.2280@unibi.uni-bielefeld.de>
  6. Date: Thu, 13 Aug 92 13:57:04 GMT
  7. References: <1992Aug9.172411.26212@unibi.uni-bielefeld.de> <Bstrq9.MKr@cs.psu.edu> <1992Aug11.132731.14626@husc3.harvard.edu>
  8. Organization: Universitaet Bielefeld
  9. Lines: 67
  10.  
  11. This is the problem the word-problem comes from:
  12.  
  13.                    1
  14.                   1 1
  15.                  2 2 3
  16.                 3 2 3 3
  17.                3 3 1 1 2
  18.               1 2 2 1 2 2
  19.              1 1 2 3 3 1 1
  20.             2 3 3 1 3 2 1 3
  21.            2 2 3 1 1 2 2 3 3
  22.                                                             o
  23. This figure shows that you can tile a triangle T9 with T2: o o
  24.  
  25. QUESTION: which T(n) can be tiled with T2?
  26.  
  27. SOLUTION:
  28.  The number of points of T(n) is ( n+1 \choose 2 ) = t(n).
  29.  3 | t(n)  iff  n = 0, 2 (mod 3).
  30.  
  31.  CASE I: if n = 0, 2, 9, 11 (mod 12) then T(n) is tileable.
  32.    From T9 you can get T11 and T12 adding:
  33.  
  34.       1 2 2 1 2 2 1 2 2 1
  35.      1 1 2 1 1 2 1 1 2 1 1
  36.  
  37.    or
  38.       1 1 2 2 3 3 1 1 2 2
  39.      2 1 3 2 1 3 2 1 3 2 1
  40.     2 2 3 3 1 1 2 2 3 3 1 1
  41.  
  42.    With T11, T12, and k times
  43.  
  44.      1 2 2 1 2 2 1 2 2 1 2 2
  45.     1 1 2 1 1 2 1 1 2 1 1 2
  46.  
  47.    you can construct T(n+12) from T(n).
  48.  
  49.  CASE II: if n = 3, 5, 6, 8 (mod 12) then T(n) is not tileable.
  50.    This is the hard case. You can look at the equivalent triomino
  51.    puzzle. In this case T5 would look like:
  52.  
  53.               o                The allowed L-triominoes are:
  54.             o o                      o         o o
  55.           o o o   = T5             o o   and   o
  56.         o o o o
  57.       o o o o o                (only 180-degree rotation)
  58.  
  59.    Now let's try group theory:
  60.    You can read about this technique in the article:
  61.      Dmitry V. Fomin, Getting it together with "polyominoes",
  62.      quantum 2:2 (Nov/Dec 1991) 20-23, 61
  63.    So you get the group: G = < a, b| aabb=baba, bbaa=abab >.
  64.    If a^n b^n <> (ba)^n for n = 3, 5, 6, 8 (mod 12) then is T(n) not
  65.    tileable. Is a^n b^n = (ba)^n for some n = 3, 5, 6, 8 (mod 12) then
  66.    a^3 b^3 = (ba)^3. This you can see be the same technique as in CASE I.
  67.    You have the additional possibility of reduction in the group. If you
  68.    show a^3 b^3 <> (ba)^3 then CASE II is solved. David Sibley found a
  69.    homomorphism, which shows this inequality. So CASE II is proofed.
  70.  
  71. Annotation:
  72.   Noam Elkies is right, that the homomorphis of David Sibley shows that
  73.   it is implossible to tile an odd rectangle with the L-triomino (only
  74.   180-degree rotation allowed) too. In this case you have to show that
  75.   a^3 b <> b a^3.
  76.  
  77. Torsten Sillke
  78.