Author Topic: 每周一题: 均贫富 (6/14/2004-6/20/2004)  (Read 10241 times)

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题: 均贫富 (6/14/2004-6/20/2004)
« on: 六月 14, 2004, 07:53:01 pm »
均贫富

大圆形赌桌上坐着很多人。有些人面前放着一些红筹码,有些人面前放着一些蓝筹码。红筹码表示正分,蓝筹码表示负分。随着赌局的进行,牌打得好的人面前红筹码越来越多,牌打得不好的人蓝筹码越来越多。这时庄家出来说要搞一搞均贫富。他的方法是:从有蓝筹码的人中随机选一个出来,把他的蓝筹码都变成红筹码,同时,为保持总分平衡,从他的两个左右邻居中每人减掉相应的红筹码(或添加相应的蓝筹码)。比如,A有5个蓝筹码,他的左邻有8个红筹码,右邻有3个红筹码。对A均贫富以后,A的5个蓝筹码变成5个红筹码。他的左邻变成3个红筹码,而他的右邻变成2个蓝筹码。再比如,A有15个蓝筹码,他的左邻有18个红筹码,右邻有3个蓝筹码。对A均贫富以后,A的15个蓝筹码变成15个红筹码。他的左邻变成3个红筹码,而他的右邻变成18个蓝筹码。现在知道,桌面上红筹码的总数比蓝筹码多。试证明如果一直这样均贫富下去(赌局暂停),一定能使桌上不存在任何有蓝筹码的人。

packman

  • Full Member
  • ***
  • Posts: 226
每周一题: 均贫富 (6/14/2004-6/20/2004)
« Reply #1 on: 六月 29, 2004, 12:10:36 pm »
万教授能否在出题后的第二个星期给个答案?象这题没人应答半个多月了。
简单==完美

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题: 均贫富 (6/14/2004-6/20/2004)
« Reply #2 on: 六月 29, 2004, 12:41:40 pm »
Ok, I will give a hint:  Consider the accumulated sum,

e.g. if the original table has  5 -8 3 10 -7, then, the accumulated sum will be

P = (5, -3, 0, 10, 3, 8, 0, 3, 13, 6, 11,....)

you need to prove every flip will sort P in the positive direction, and the process will end nicely (since the total sum of the table is positive).

Heng

  • Newbie
  • *
  • Posts: 3
每周一题: 均贫富 (6/14/2004-6/20/2004)
« Reply #3 on: 六月 29, 2004, 03:05:50 pm »
It took me a while to figure out what does 'accumulated sum' mean. If it means sum(m)=[sum(m-1)+m's chips] and goes around the table, then the 'accumulated sum' should be the same (when chip=0) or increase when there is no blue chip on the table.

Say n(m) equals accumulated sum up to person m, only when m has blue chip, i.e. n(m-1)>n(m), would flip on him. Because the total chip number is balanced, all the accumulated sums before n(m-1) and after n(m) will not be affected by the flipping (unless the adding goes around the table again).

It is then clear that after fliping, n'(m)=n(m-1) and n'(m-1)=n(m). Since n(m-1)>n(m), the fliping sorted the accumulated sum by swarping the two numbers towards positive direction.

Since the starting sum around the table is positive (red chips more than blue chips), flipping will eliminant all the decrease of the sum, i.e. rid of the blue chips.

Is that it?



Quote from: 万精油
Ok, I will give a hint:  Consider the accumulated sum,

e.g. if the original table has  5 -8 3 10 -7, then, the accumulated sum will be

P = (5, -3, 0, 10, 3, 8, 0, 3, 13, 6, 11,....)

you need to prove every flip will sort P in the positive direction, and the process will end nicely (since the total sum of the table is positive).

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题: 均贫富 (6/14/2004-6/20/2004)
« Reply #4 on: 七月 02, 2004, 09:27:37 am »
Yes, that's the idea, missing some details. I will write it down in Chinese over the weekend.

方信

  • Newbie
  • *
  • Posts: 15
每周一题: 均贫富 (6/14/2004-6/20/2004)
« Reply #5 on: 八月 22, 2004, 03:14:22 pm »
I am quite impressed with the sorting of the accumulative sum. But two things I still could not figure out. Have the professor posted the correct answer?

1. The flip of the first one, will possibly result in increasing disorder numbers of the sequence. How do we solve the boundary condition here?

2. the positiveness of the total sum is very important. How do we use that condition?

If the total sum is 0, then the question will become invalid. A simple example, two people, one with 1 red and the other 1 blue. You will never get into a situation where both are 0. It is always 1 red and 1 blue after each flip.

Or 3 people,  with 1 red, 1 blue and 0. Any flip will result in the same situation as the starting point.