home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / 16847 < prev    next >
Encoding:
Internet Message Format  |  1992-12-14  |  1.5 KB
  1. Path: sparky!uunet!mcsun!sunic!dkuug!diku!torbenm
  2. From: torbenm@diku.dk (Torben AEgidius Mogensen)
  3. Newsgroups: sci.math
  4. Subject: Re: Tiling problem
  5. Message-ID: <1992Dec14.121909.1308@odin.diku.dk>
  6. Date: 14 Dec 92 12:19:09 GMT
  7. References: <israel.723716857@unixg.ubc.ca> <israel.723837962@unixg.ubc.ca> <1gggutINN29q@access.usask.ca>
  8. Sender: torbenm@thor.diku.dk
  9. Organization: Department of Computer Science, U of Copenhagen
  10. Lines: 43
  11.  
  12. choy@skorpio.usask.ca (I am a terminator.) writes:
  13.  
  14. >In article <israel.723837962@unixg.ubc.ca>, israel@unixg.ubc.ca (Robert B. Israel) writes:
  15. >|> In <rcbaaw.723228012@rwb.urc.tue.nl>, rwb.urc.tue.nl (Angelo
  16. >|> Wentzler) writes:
  17. >|> 
  18. >|> >Given a grid of squares, tile it with black and white tiles and make
  19. >|> >the largest possible square so that no square contained in it has four
  20. >|> >equally colored corners.
  21.  
  22.  
  23. >Would the following be a recursive solution?
  24.  
  25. >0
  26.  
  27. >1
  28.  
  29. >Kinda small--let's double the size.
  30.  
  31. >00
  32. >00
  33.  
  34. >Um ... no internal squares in these little squares so no 4 colored corners.
  35.  
  36. Note that the posting did not say INTERNAL squares. The whole square
  37. also counts.
  38.  
  39. >Doubling again:
  40.  
  41. >0011
  42. >0011
  43. >1100
  44. >1100
  45.  
  46. >Now your starting to worry. The internal squares have 4 (colored) corners.
  47. >In general, the internal 0 (or the internal 1) has two 0 corners and two
  48. >1 corners. So that's OK.
  49.  
  50. Note also that ALL subsquares must be considered, not just those that
  51. are centered. The top-left 2x2 subsquare (and many more) has for
  52. identical corners.
  53.  
  54.     Torben Mogensen (torbenm@diku.dk)
  55.