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

#### 万精油

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

#### packman

• Full Member
•   • Posts: 226 ##### 每周一题: 均贫富 (6/14/2004-6/20/2004)
« Reply #1 on: 六月 29, 2004, 12:10:36 pm »

#### 万精油

• 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).

#### 万精油

• 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.