home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / math / 18801 < prev    next >
Encoding:
Internet Message Format  |  1993-01-28  |  1.9 KB
  1. Path: sparky!uunet!europa.eng.gtefsd.com!paladin.american.edu!news.univie.ac.at!hp4at!mcsun!julienas!corton!geocub!loeb
  2. From: loeb@greco-prog.fr (Daniel LOEB)
  3. Newsgroups: sci.math
  4. Subject: Re: Combinatorial Problems
  5. Message-ID: <1993Jan27.213413.8818@greco-prog.fr>
  6. Date: 27 Jan 93 21:34:13 GMT
  7. References: <93022.114846DCC117@psuvm.psu.edu> <1993Jan23.121800.2214@infodev.cam.ac.uk> <1993Jan27.141536.28877@greco-prog.fr>
  8. Reply-To: loeb@geocub.UUCP (Daniel LOEB)
  9. Organization: Greco Programmation du CNRS
  10. Lines: 35
  11.  
  12. n article <1993Jan27.141536.28877@greco-prog.fr> I wrote:
  13. >>In article <93022.114846DCC117@psuvm.psu.edu> <DCC117@psuvm.psu.edu>
  14. >>posed the following problem: 
  15. >>   A 6-by-6 chessboard is perfectly covered with 18 dominoes.
  16. >> Prove that it is possible to cut it either horizontally or
  17. >> vertically into two non-empty pieces without cutting through
  18. >> a domino, that is, prove there must be a fault-line.
  19. >
  20. >Gabor Megyesi gave a proof.
  21. >His proof also shows that there are no 2xn, or 4xn, or 6x1, or 6x3, or
  22. >fault-less rectangles. 
  23. >
  24. >We can now ask the following question. For what i (even) and what j is
  25. >there a fault-less rectangle of size i x j.
  26. >
  27. Since this afternoon I've not that if you take a fault-less rectangle
  28. and cut a line across it (breaking a few dominos) there is a canonical
  29. way to repair the damage and lengthen the rectangle by 2 in the
  30. process. 
  31.  
  32. I've already given examples of 5x6 rectangles and 6x8 rectangles.
  33. Thus there exist ixj fault-less rectangles if and only if
  34. either ixj are both even and one is at least 8 while the other is at
  35. least 6, or one is odd and at least 5 while the other is even and at
  36. least 6.
  37.  
  38. Now let me pose yet another problem thqt I haven't thought much about
  39. yet. For what i,jk does there exist an ixjxk fault-less block of 1x1x2
  40. dominos.
  41.  
  42. -- 
  43.  
  44. Yours, Daniel Loeb                loeb@geocub.greco-prog.fr
  45. HOME     150, cours Victor-Hugo; Appt D45; 33000 Bordeaux France
  46. WORK    LABRI; Universite de Bordeaux I; 33405 Talence Cedex France
  47.