home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / 17222 < prev    next >
Encoding:
Text File  |  1992-12-21  |  3.4 KB  |  89 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!pipex!pavo.csi.cam.ac.uk!camcus!cet1
  3. From: cet1@cus.cam.ac.uk (C.E. Thompson)
  4. Subject: Re: Tiling problem
  5. Message-ID: <1992Dec20.000625.28213@infodev.cam.ac.uk>
  6. Sender: news@infodev.cam.ac.uk (USENET news)
  7. Nntp-Posting-Host: grus.cus.cam.ac.uk
  8. Organization: U of Cambridge, England
  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>
  10. Date: Sun, 20 Dec 1992 00:06:25 GMT
  11. Lines: 76
  12.  
  13. In article <1992Dec18.111210.2852@odin.diku.dk>, torbenm@diku.dk
  14. (Torben AEgidius Mogensen) writes:
  15. |> cet1@cus.cam.ac.uk (C.E. Thompson) writes:
  16. |> 
  17. |> >It occured to me that one could put more constraints on the problem by using
  18. |> >periodic boundary conditions. This brings the probabilisticly suggested largest
  19. |> >square down from about 17 to about 11, and so it might be more ammenable to
  20. |> >a brute-force-and-ignorance computational attack.
  21. |> >
  22. |> >This version could be stated as: colour the tiles of the infinite plane square
  23. |> >lattice black and white, periodically with period N in both directions, such
  24. |> >that the only (orthogonally oriented) squares with all four corners the same
  25. |> >colour have both sides divisible by N.
  26. |> 
  27. |> Well, since someone already posted a 13x13 solution, an estimate of 11
  28. |> is a bit on the low side. But the suggestion sounds interesting.
  29.  
  30. My first reaction to this was to point out that the "periodic boundary
  31. conditions" version is really more restrictive -- in term of the original
  32. problem one is demanding that i x (N-i) rectangles ("wrap-round squares")
  33. have their 4 corners not all the same, as well as the i x i squares, for
  34. 1 <= i <= N-1. Thus the N = 12 solution that Robert Israel posted:
  35.  
  36.          bb
  37.          ||
  38.         000011011111
  39.         011010010101
  40.         001100110011
  41.         010110100110
  42.         010100101010
  43.         011001100101
  44.         101101001100
  45.         100101010110
  46.         110011010010
  47.     a-> 101010011001 <-a 
  48.     a-> 110011001011 <-a
  49.         100110100101
  50.          ||
  51.          bb
  52.  
  53. has several wrap-round squares (e.g. the 1x11 rectangles marked a and b)
  54. which violate the stronger condition. 
  55.  
  56. But I then noticed, to my considerable astonishment, that Robert Israel's
  57. later N = 13 solution:
  58.  
  59.         0001101010110
  60.         0101011000011
  61.         1100001101110
  62.         0110101011000
  63.         0101100001101
  64.         0000110101011
  65.         1011101100001
  66.         0110000110111
  67.         0011010101100
  68.         1010110000110
  69.         1000011011101
  70.         1101110110000
  71.         1011000011010
  72.  
  73. *does* satisfy the stronger condition, having no i x (13-i) rectangles with
  74. four corners the same. Unless this is a consequence of his search strategy,
  75. there is something very odd going on.
  76.  
  77. The probabilistic argument I had in mind, following Torben Morgensen's 
  78. original one, involves assuming that the probability of each sub-square
  79. violating the conditions is 7/8, independently of the others. For N=13 there 
  80. are 650 regular sub-squares (giving Torben's estimate of 2^169*(7/8)^650 =
  81. 1.511e13 solutions) and another 364 wrap-round ones, giving an estimate of
  82. 2^169*(7/8)^1014 = 1.175e-8 solutions. So the undoubted existence of at 
  83. least one solution suggests that the assumption of independence was not
  84. a very good one!
  85.  
  86. Chris Thompson
  87. JANET:    cet1@uk.ac.cam.phx
  88. Internet: cet1@phx.cam.ac.uk
  89.