home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / 17182 < prev    next >
Encoding:
Internet Message Format  |  1992-12-21  |  2.7 KB
  1. Path: sparky!uunet!mcsun!sun4nl!tuegate.tue.nl!rw6.urc.tue.nl!rcbaaw
  2. From: rcbaaw@rw6.urc.tue.nl (Angelo Wentzler)
  3. Newsgroups: sci.math
  4. Subject: Re: Tiling problem
  5. Message-ID: <rcbaaw.724687510@rw6.urc.tue.nl>
  6. Date: 18 Dec 92 14:05:10 GMT
  7. References: <israel.723716857@unixg.ubc.ca> <israel.723837962@unixg.ubc.ca> <1gggutINN29q@access.usask.ca> <1gm373INNafn@access.usask.ca>
  8. Sender: root@tuegate.tue.nl
  9. Reply-To: rcbaaw@urc.tue.nl
  10. Lines: 63
  11.  
  12. choy@skorpio.usask.ca (I am a terminator.) writes:
  13.  
  14. >In article <1gggutINN29q@access.usask.ca>, choy@skorpio.usask.ca (I am a terminator.) writes:
  15. >|> In article <israel.723837962@unixg.ubc.ca>, israel@unixg.ubc.ca (Robert B. Israel) writes:
  16. >|> |> In <rcbaaw.723228012@rwb.urc.tue.nl>, rwb.urc.tue.nl (Angelo
  17. >|> |> Wentzler) writes:
  18. >|> |> 
  19. >|> |> >Given a grid of squares, tile it with black and white tiles and make
  20. >|> |> >the largest possible square so that no square contained in it has four
  21. >|> |> >equally colored corners.
  22.  
  23. >Never mind my previous post, but can such an n x n square be constructed
  24. >as a permutation of an n x n checkerboard?
  25.  
  26. >Henry Choy
  27. >choy@cs.usask.ca
  28.  
  29. Not all of them. There is only one 2x2 square that can be constructed from 
  30. a 2x2 checkerboard. Manually (my search program is at home) I found some
  31. squares with the same property for the smaller sizes. I have also added
  32. some counterexamples.
  33.  
  34. solution       checkerboard         Counterexample
  35.  
  36. 10             10                   11
  37. 01             01                   01
  38.  
  39. 101            101                  111
  40. 011            010                  010
  41. 100            101                  011
  42.  
  43. 1010           1010                 1111
  44. 0110           0101                 0101
  45. 1001           1010                 0110
  46. 0110           0101                 1100
  47.  
  48.  
  49. For such solutions the following holds:
  50. odd dimension: #black=#white+1
  51. even dimension: #black=#white
  52. So "balanced squares" would be a good name.
  53. Note that a balanced square doesn't necessarily have two white and two black
  54. corners.
  55.  
  56. In the small example each solution is derived from the previous one, but
  57. I don't think that's necessary. You could make a balanced square from an
  58. unbalanced smaller one. Just mirror the 3x3 to get an example.
  59. Still, could the following be true?
  60.  
  61. Any balanced NxN square must contain at least one balanced ixi subsquare for
  62. each 1<i<N
  63.  
  64. If this were true, then the same approach for normal squares would be
  65. possible: just take a 2x2 balanced square (*the* 2x2 balanced square) and
  66. just keep expanding it to obtain one for any dimension (up to a certain
  67. limit...)
  68. Because if the above holds, those balanced ixi subsquares in particular will
  69. contain balanced subsquares too, etc.
  70.  
  71. Could make a nice subset of the correct solutions...
  72.  
  73.  
  74. Angelo Wentzler
  75.