HMMT 二月 2000 · ORAL 赛 · 第 10 题
HMMT February 2000 — ORAL Round — Problem 10
题目详情
英文原题
- [75] 23 frat brothers are sitting in a circle. One, call him Alex, starts with a gallon ofwater. On the first turn, Alex gives each person in the circle some rational fraction of hiswater. On each subsequent turn, every person with water uses the same scheme as Alexdid to distribute his water, but in relation to themselves. For instance, suppose Alex gave
1 / 2 and 1 / 6 of his water to his left and right neighbors respectively on the first turn andkept 1 / 3 for himself. On each subsequent turn everyone gives 1 / 2 and 1 / 6 of the waterthey started the turn with to their left and right neighbours (resp.) and keep the final thirdfor themselves. After 23 turns, Alex again has a gallon of water. What possibilities are there for the scheme he used in the first turn? (Note: you may find it useful to know that
2 22
1 + x + x + ... + x has no polynomial factors with rational coefficients.)
解析
英文解析
- Let ω be a 23 rd root of unity, a solution to the equation x = 1. We can encode thestate of the game as 23 rational numbers a , ..., a representing the amount of water
0 22
each person has, with Alex having the frction a of the water and continuing to hisright. Then we can look at the polynomial f ( x ) = a x + ... + a which still encodes 220
22 0
the state of the game. In this schema the original state is the constant 1, and we haveat all times the condition f (1) = 1 (conservation of water). However, we want a cyclicrepresentation in order to encode the play of the game, so we let the state of the gamebe f ( ω ) = a ω + ... + a . In this representation, a step in the game can be encoded 22
22 0
as multiplication by another polynomial in ω , g ( ω ) = b ω + ... + b where the b 22
22 0 iare the fraction of water that Alex initially gives to the i -th person on his right. The
1 1 1
example in the problem is represented by ω + + ω . So we would like to know 22
6 3 2
which g are solutions to g ( ω ) = 1. We can take 23 rd roots of both sides and find 23
22 kthat g ( ω ) = b ω + ... + b = ω for some integer k. To simplify this we need a small
22 0
lemma.
Lemma : If a ω + ... + a is some rational linear combination of the powers of ω and 222
22 0
is equal to 0, then a = a = ... = a .
22 21 0
Proof: Assume this is false. So there exists some polynomial A ( x ) = a x + ... + a 22
22 0
22 21
with ω as a root that is not a constant multiple of B ( x ) = x + x + ... + 1. Now apply
Euclid’s algorithm to find the G.C.D. of A ( x ) and B ( x ) and call it D ( x ). But D ( x )
is a rational polynomial that divides B ( x ), which has no non-trivial rational divisors.
Hence D ( x ) must be either a constant or of degree 22. Since A ( ω ) = B ( ω ) = 0 allthe terms in the algorithm have a root at ω and so does D ( x ). So since 0 is not anacceptable value for a G.C.D., D ( x ) must have degree 22. Since the degree of eachsuccessive term in Euclid’s algorithm decreases by at least one, this means that D ( x )
must be A ( x ) and hence that B ( x ) is a constant multiple of A ( x ). This contradicts theoriginal assumption and the Lemma is proved.
So the Lemma tells us that b = b = ... = b − 1 = ... = b . Since we already know
22 21 k 0
that g (1) = 1 and hence b + b + ... + b = 1, and that all the b are nonnegative,
22 21 0 iwe get that b = 0 for i 6 = k and b = 1. Since this is a solution for all k, the possiblei kschemes for Alex to use are just those involving giving all his water to any one otherperson. 3