Author Topic: 四分巧克力(和packman对着干)  (Read 11732 times)

froid

  • Newbie
  • *
  • Posts: 16
四分巧克力(和packman对着干)
« on: 七月 14, 2004, 04:16:18 pm »
一矩形巧克力(2m x 2n),上面颜色如国际象棋的棋盘,黑白相间。但是其中有一块白巧克力和一块黑巧克力被吃掉了(这两块不一定连在一起,也不一定在边或角上,可以在任何可能的地方)。问:是否一定能将剩余的 (2m x 2n - 2) 块分成 (m x n - 1) 个“日”字型的小块?Why?

packman

  • Full Member
  • ***
  • Posts: 226
四分巧克力(和packman对着干)
« Reply #1 on: 七月 14, 2004, 04:39:10 pm »
Yes, you can.

First of all, Froid, you leaked out the answer of my question. :lol:

Here's the proof:
1. Draw a small rectangle that makes the two eaten pieces as two corners. No matter where these two missing pieces are, the small inner rectange has to be (2a + 1) x 2b.(to satisfy a black and white missing pieces). Let's assume the height (vertical) is 2a + 1.
2. For the remaining outside pieces on the right and left side of the small rectangle, break vertically, then each long stripe can be divided by 2.
3. After that, for the remaining outside pieces on the top and bottom of the small rectangle, break horizontally, then each long stripe can be divided by 2.(It's 2b)
4. For the small rectangle, the center pieces can be removed until it becomes a 2x3 size (with two missing pieces at the corner). One more break and it's done.

Prof. 10K, when can we upload pictures??
I am not satisfied with my own explanation. :lol:
简单==完美

froid

  • Newbie
  • *
  • Posts: 16
四分巧克力(和packman对着干)
« Reply #2 on: 七月 14, 2004, 05:06:12 pm »
啊,我出错题了,是2m*n,n不一定是偶数。这样packman你的解法就要改一下了 :P

packman

  • Full Member
  • ***
  • Posts: 226
四分巧克力(和packman对着干)
« Reply #3 on: 七月 14, 2004, 05:13:17 pm »
You still can.
Man, I wish I can draw here. Anyway, I will type the lengthy solution tomorrow or later. (gonna go).
简单==完美

packman

  • Full Member
  • ***
  • Posts: 226
四分巧克力(和packman对着干)
« Reply #4 on: 七月 14, 2004, 07:15:10 pm »
OK, here is the modified solution:
1. Still draw small rectangle (2a+1) x 2b, and assume (2a+1) is the height.
2. For the outsiders, if the height is even number, the solution is the same as before.
3. If the height is odd, break the very top (or bottom) stripe first, which it's width is even and can be divided. Then it's same as before.
4. If there's no extra stripes on top or bottom of the small rectangle, then
(a) The left or right stripes on sides of the the small rectangle have to be both even number or both odd number. If both are even, simple...
(b) If both are odd, strip down to a single extra stripe, and also reduce the small rectangle down to 2x3 as before. In the end, instead of 2x3, it should be 4x3, as I'll show you below:

XOYX
XYYX
XYOX

where "O"s are the missing pieces, "O"s and "Y"s made the small rectangle and "X"s belong to the extra single stripes on both sides. Now this formation can be divided as follows (same letter in one piece):

AOBB
ACCD
EEOD

The explanation is too lengthy. Sorry.
简单==完美

方信

  • Newbie
  • *
  • Posts: 15
四分巧克力(和packman对着干)
« Reply #5 on: 八月 22, 2004, 11:57:52 pm »
How about this proof.

1. first of all,  a board of 2m*n can be divided into m*n sub-pieces of size 2.

2. now consider the two bad ones. You can find a sequence of sub-pieces of size 2 in the step 1, which starts from the black bad one, and ends at the white bad one. And the front of next piece always connect with the end of the previous piece.  

3. re-organize the sub-pieces in the sequence. Such that each pair of the front of the next sub-piece and the end of the previous sub-peice in the sequence constructs a new sub-piece.

sean

  • Jr. Member
  • **
  • Posts: 86
方信的解法很好呀.
« Reply #6 on: 九月 05, 2004, 08:28:20 pm »
这题是所谓的二分图完美匹配, 比较有意思. 有一个掩盖问题实质的解法是数学归纳法.