home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / math / 18682 < prev    next >
Encoding:
Text File  |  1993-01-23  |  1.1 KB  |  30 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!pipex!warwick!pavo.csi.cam.ac.uk!emu.pmms.cam.ac.uk!gm115
  3. From: gm115@emu.pmms.cam.ac.uk (Gabor Megyesi)
  4. Subject: Re: Combinatorial Problems
  5. Message-ID: <1993Jan23.121800.2214@infodev.cam.ac.uk>
  6. Sender: news@infodev.cam.ac.uk (USENET news)
  7. Nntp-Posting-Host: emu.pmms.cam.ac.uk
  8. Organization: DPMMS University of Cambridge
  9. References: <93022.114846DCC117@psuvm.psu.edu>
  10. Date: Sat, 23 Jan 1993 12:18:00 GMT
  11. Lines: 17
  12.  
  13. In article <93022.114846DCC117@psuvm.psu.edu> <DCC117@psuvm.psu.edu> writes:
  14. >   Has anybody worked with, or know the solution to, the
  15. >following problem ?
  16. >
  17. >   A 6-by-6 chessboard is perfectly covered with 18 dominoes.
  18. > Prove that it is possible to cut it either horizontally or
  19. > vertically into two non-empty pieces without cutting through
  20. > a domino, that is, prove there must be a fault-line.
  21. >
  22.  
  23. There are 10 lines and 18 dominoes. For parity reasons any line must cut
  24. through an even number of dominoes, so if a line cuts through a domino, it
  25. must cut through at least 2. Therefore the 18 dominoes cannot cover all 10
  26. linmes, so there must be a fault-line. Q.E.D.
  27.  
  28. Gßbor Megyesi
  29. G.Megyesi@pmms.cam.ac.uk
  30.