home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / 17230 < prev    next >
Encoding:
Internet Message Format  |  1992-12-21  |  3.0 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!destroyer!cs.ubc.ca!unixg.ubc.ca!unixg.ubc.ca!israel
  2. From: israel@unixg.ubc.ca (Robert B. Israel)
  3. Newsgroups: sci.math
  4. Subject: Re: Tiling problem
  5. Date: 20 Dec 92 09:26:50 GMT
  6. Organization: The University of British Columbia
  7. Lines: 64
  8. Message-ID: <israel.724843610@unixg.ubc.ca>
  9. References: <israel.723716857@unixg.ubc.ca> <israel.723837962@unixg.ubc.ca> <1gggutINN29q@access.usask.ca> <1gm373INNafn@access.usask.ca> <1992Dec18.002343.3944@infodev.cam.ac.uk> <1992Dec18.111210.2852@odin.diku.dk> <1992Dec20.000625.28213@infodev.cam.ac.uk>
  10. NNTP-Posting-Host: unixg.ubc.ca
  11.  
  12. In <1992Dec20.000625.28213@infodev.cam.ac.uk> cet1@cus.cam.ac.uk (C.E. Thompson) writes:
  13.  
  14. >But I then noticed, to my considerable astonishment, that Robert Israel's
  15. >later N = 13 solution:
  16.  
  17. >        0001101010110
  18. >        0101011000011
  19. >        1100001101110
  20. >        0110101011000
  21. >        0101100001101
  22. >        0000110101011
  23. >        1011101100001
  24. >        0110000110111
  25. >        0011010101100
  26. >        1010110000110
  27. >        1000011011101
  28. >        1101110110000
  29. >        1011000011010
  30.  
  31. >*does* satisfy the stronger condition, having no i x (13-i) rectangles with
  32. >four corners the same. Unless this is a consequence of his search strategy,
  33. >there is something very odd going on.
  34.  
  35. As a matter of fact, there *is* something odd going on.  A close look at
  36. this solution shows that all the rows are cyclic permutations of 
  37. 001101a101100, where "a" is either 0 or 1, each row being displaced 5
  38. places to the left from the previous one.  If you write one of these
  39. 13-tuples as <c_i>_{i=0..12}, it satisfies the condition that for all
  40. i and 1 <= j <= 12, c_i, c_{i+j}, c_{i+5j} and c_{i+6j} are not all the
  41. same (considering the subscripts mod 13).  Thus such a 13-tuple generates
  42. a square that works (with periodic boundary condition).  The only 13-tuples
  43. for which this works are these two and those obtained from them by cyclic
  44. permutation and interchanging 1 and 0.  I also tried shifts other than 5
  45. (so for some b, 1<=b<=12, you want c_i,c_{i+j},c_{i+bj} and c_{i+(b+1)j}
  46. never to be all the same).  No more examples except for b=8 (which is
  47. equivalent to b=5 by left<->right symmetry).  Unfortunately, there are no
  48. 14-, 15-, 16- or 17-tuples with the analogous properties either.
  49.  
  50. I don't think that my search strategy has any inherent bias towards 
  51. solutions with any particular regularity or periodicity.  I tried running
  52. the 13 x 13 square again, with the following result:
  53.  
  54. 1011010011010
  55. 0001111010110
  56. 0111001000011
  57. 1100011101010
  58. 1001010100111
  59. 0101110001101
  60. 0000100111011
  61. 1010111100001
  62. 0110010110101
  63. 0011001101100
  64. 1110101000110
  65. 1000001011101
  66. 1101100110000
  67.  
  68. If there's structure here, it's certainly more subtle than last time.  
  69. I haven't checked whether this satisfies the periodic boundary condition.
  70.  
  71. -- 
  72. Robert Israel                            israel@math.ubc.ca
  73. Department of Mathematics             or israel@unixg.ubc.ca
  74. University of British Columbia
  75. Vancouver, BC, Canada V6T 1Y4
  76.