糖果传递游戏
Candy Game
题目详情
一群学生围成一圈，老师在中间。每个学生初始糖果数为偶数（不必相同）。
每次哨声：
- 每个学生把自己糖果的一半传给左边同学。
- 传完后，糖果数为奇数的学生会从老师处再得到 1 颗糖（使其变为偶数）。
证明：经过有限次哨声后，所有学生糖果数会变得相同。
提示：观察最小值与最大值。
A group of students are sitting in a circle with the teacher in the center. They all have an even number of candies (not necessarily equal). When the teacher blows a whistle, each student passes half his candies to the student on his left. Then the students who have an odd number of candies obtain an extra candy from the teacher. Show that after a finite number of whistles, all students have the same number of candies.
Hint
Look at minimum & maximum count of candies.
解析
关键单调性：
- 最大糖果数不会增加。
- 最小糖果数会在有限步内严格增加（若最小值暂时不涨，则“连续最小段”的最长长度会严格缩短，最终迫使最小值上涨）。
由于最小值不能无限上涨且不超过最大值，因此在有限步后最小值=最大值，所有人糖果数相同。
Original Explanation
Solution
- The maximum number of candies held by a single student can never increase.
- The minimum number of candies held by a single student always strictly increases, unless the student to his right also has the minimum number of candies, in which case the length of the longest consecutive segment of students who have minimum number of candies strictly decreases. Thus eventually the minimum has to strictly increase.
- Since the minimum has to strictly increase in a finite number of steps and cannot go beyond the maximum, all the numbers must eventually be equal in atmost n(max-min) steps.