home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / math / 18802 < prev    next >
Encoding:
Internet Message Format  |  1993-01-28  |  1.5 KB
  1. Path: sparky!uunet!europa.eng.gtefsd.com!emory!swrinde!zaphod.mps.ohio-state.edu!howland.reston.ans.net!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.141536.28877@greco-prog.fr>
  6. Date: 27 Jan 93 14:15:36 GMT
  7. References: <93022.114846DCC117@psuvm.psu.edu> <1993Jan23.121800.2214@infodev.cam.ac.uk>
  8. Reply-To: loeb@geocub.UUCP (Daniel LOEB)
  9. Organization: Greco Programmation du CNRS
  10. Lines: 37
  11.  
  12. >In article <93022.114846DCC117@psuvm.psu.edu> <DCC117@psuvm.psu.edu>
  13. >posed the following problem: 
  14. >   A 6-by-6 chessboard is perfectly covered with 18 dominoes.
  15. > Prove that it is possible to cut it either horizontally or
  16. > vertically into two non-empty pieces without cutting through
  17. > a domino, that is, prove there must be a fault-line.
  18.  
  19. Gabor Megyesi gave a proof.
  20. His proof also shows that there are no 2xn, or 4xn, or 6x1, or 6x3, or
  21. fault-less rectangles. 
  22.  
  23. On the other hand here is a 6x5 fault-less rectangle:
  24. aabcc
  25. debff
  26. dehhg
  27. ijjkg
  28. innkl
  29. mmool
  30.  
  31. And here is a 6x8 fault-less rectange:
  32. aacced
  33. hbbfed
  34. hijfgg
  35. kijllm
  36. knwxxm
  37. onwvuu
  38. oqqvst
  39. pprrst
  40.  
  41. We can now ask the following question. For what i (even) and what j is
  42. there a fault-less rectangle of size i x j.
  43.  
  44. -- 
  45.  
  46. Yours, Daniel Loeb                loeb@geocub.greco-prog.fr
  47. HOME     150, cours Victor-Hugo; Appt D45; 33000 Bordeaux France
  48. WORK    LABRI; Universite de Bordeaux I; 33405 Talence Cedex France
  49.