Author Topic: 每周一题: 再分巧克力 (6/28/2004-7/4/2004)  (Read 17731 times)

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1830
每周一题: 再分巧克力 (6/28/2004-7/4/2004)
« on: 六月 27, 2004, 11:42:53 pm »
上周的题目应该说很简单。我觉得它的趣味在於它的解,简单优美。

第一题要我们证明无论怎样掰,所掰次数一样。我的证明是用规纳法。只有一个小块的时候(1X1),不需要掰,零次。只有两个小块的时候(1X2),只需掰一次。现假设,当块数小於N块时所需次数是块数减一,现要证明当块数是N+1块时,需要N次。从任意一个地方把这个N+1块的巧克力掰成两块,一块个数为X,一块个数为Y。显然,X〈=N,Y〈=N,X+Y=N+1。根据假设,把第一块完全掰开需要X-1次,把第二块完全掰开需要Y-1次,总共需要X-1+Y-1=N+1-2=N-1次,再加上我们开始把它掰成两块所需要的一次,总共N次,证毕。

我把这道题出给一个高中生,他马上就解出来了。他的解法是:我们开始只有一个大块,每掰一次,不管怎样掰,块数总是加一。要把每块都掰开,所需次数总是块数减一。这是我认为非常优美的证明,可惜不是我想到的。

第二题,差不多的证明是对的,只需给对方留正方块就行了。这道题还有另一个版本,就是我们这周的题目。

本周题目一个  M  x  N  巧克力,已知左下角那块是坏的。两个人分吃这个巧克力。两人都想把左下角那块留给对方。两人的吃法是,要吃的人从剩下的巧克力中随便选一小块,就可以(必须)把这一小块右面和上面的都掰下来吃掉(也包括那一小块)。试证明,只要开始的块数多于一块,则第一人总可以有一种办法使得他能把坏的那块留给对方。

packman

  • Full Member
  • ***
  • Posts: 226
每周一题: 再分巧克力 (6/28/2004-7/4/2004)
« Reply #1 on: 六月 29, 2004, 11:35:55 am »
if M (or N) = 1, just pick the one next to the "bad bottom-left corner" piece, that leaves the bad corner only for your friend.

if M > 1 and N > 1, just pick the upper-right piece next to it. (i.e., if the coordinate of the bad one is (0,0), then pick (1,1)), that leaves 3 pieces including the bad one to your friend....
简单==完美

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1830
每周一题: 再分巧克力 (6/28/2004-7/4/2004)
« Reply #2 on: 六月 29, 2004, 12:36:50 pm »
Your approach will not work.

If the original is 2 x 3,  after your pick, it will have the following shape left

  X
  X X X

your opponent will pick the right most one, you will be left with

  X
  X X

and you will lose no matter what

packman

  • Full Member
  • ***
  • Posts: 226
每周一题: 再分巧克力 (6/28/2004-7/4/2004)
« Reply #3 on: 六月 29, 2004, 12:40:51 pm »
You said:
就可以(必须)把这一小块右面和上面的都掰下来吃掉(也包括那一小块)

So, if the original is 2x3, after my pick, it will become
x
xx,

not
x
xxx

all the pieces on the "RIGHT" side are all gone too, right?


Quote from: 万精油
Your approach will not work.

If the original is 2 x 3,  after your pick, it will have the following shape left

  X
  X X X

your opponent will pick the right most one, you will be left with

  X
  X X

and you will lose no matter what
简单==完美

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1830
每周一题: 再分巧克力 (6/28/2004-7/4/2004)
« Reply #4 on: 六月 29, 2004, 01:00:03 pm »
May be I was not clear. When I said on the right and above, I do mean AND. i.e. pieces that are both on the right side (including its own column) and above it (including its own row). If we use coordinate system, suppose the small rectangle you pick is (a,b), then, all (and only) those with  x>=a AND y>=b will be take off.

七把叉

  • Jr. Member
  • **
  • Posts: 27
    • http://www.sevenforks.com
    • Email
每周一题: 再分巧克力 (6/28/2004-7/4/2004)
« Reply #5 on: 六月 29, 2004, 01:02:39 pm »
packman理解错了,但也要怪万教授的表述有歧义。

万教授说的是“右面&上面”,而不是“右面|上面”。

Heng

  • Newbie
  • *
  • Posts: 3
每周一题: 再分巧克力 (6/28/2004-7/4/2004)
« Reply #6 on: 六月 29, 2004, 01:06:13 pm »
I think packman had a nice try. His way (takeing (1,1)) can work when M>2 and N>2, and when M=2 and N=2, at least to me.

When M=2 and N>2, such as 2X3, take (2,3). Would that work?

packman

  • Full Member
  • ***
  • Posts: 226
每周一题: 再分巧克力 (6/28/2004-7/4/2004)
« Reply #7 on: 六月 29, 2004, 01:07:22 pm »
Yes, that is how I interpret it too: right AND above.
After I pick "o", all the "y"s and "o" are gone, right?

yyyyyyyy
xoyyyyyy
xxyyyyyy

Quote from: 万精油
May be I was not clear. When I said on the right and above, I do mean AND. i.e. pieces that are both on the right side (including its own column) and above it (including its own row). If we use coordinate system, suppose the small rectangle you pick is (a,b), then, all (and only) those with  x>=a AND y>=b will be take off.
简单==完美

packman

  • Full Member
  • ***
  • Posts: 226
每周一题: 再分巧克力 (6/28/2004-7/4/2004)
« Reply #8 on: 六月 29, 2004, 01:08:48 pm »
Sorry, I mis-interpretted. Forget about my previous post.

Quote from: packman
Yes, that is how I interpret it too: right AND above.
After I pick "o", all the "y"s and "o" are gone, right?

yyyyyyyy
xoyyyyyy
xxyyyyyy

Quote from: 万精油
May be I was not clear. When I said on the right and above, I do mean AND. i.e. pieces that are both on the right side (including its own column) and above it (including its own row). If we use coordinate system, suppose the small rectangle you pick is (a,b), then, all (and only) those with  x>=a AND y>=b will be take off.
简单==完美

七把叉

  • Jr. Member
  • **
  • Posts: 27
    • http://www.sevenforks.com
    • Email
每周一题: 再分巧克力 (6/28/2004-7/4/2004)
« Reply #9 on: 六月 29, 2004, 01:22:09 pm »
packman的误解是有道理的。万教授的问题出在他是用自然语言表述
的。比如我们说“把苹果和梨都吃了”,这里分明是“苹果|梨”而不
是“苹果&梨”。

packman

  • Full Member
  • ***
  • Posts: 226
每周一题: 再分巧克力 (6/28/2004-7/4/2004)
« Reply #10 on: 六月 29, 2004, 01:43:58 pm »
那是米丘林的苹果梨。 哈哈。
谢谢万教授和七大侠的指正。

javascript:emoticon(':lol:')javascript:emoticon(':lol:')

Quote from: 七把叉
packman的误解是有道理的。万教授的问题出在他是用自然语言表述
的。比如我们说“把苹果和梨都吃了”,这里分明是“苹果|梨”而不
是“苹果&梨”。
简单==完美