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 of water. On the first turn, Alex gives each person in the circle some rational fraction of his water. On each subsequent turn, every person with water uses the same scheme as Alex did 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 and kept 1 / 3 for himself. On each subsequent turn everyone gives 1 / 2 and 1 / 6 of the water they started the turn with to their left and right neighbours (resp.) and keep the final third for 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 23rd root of unity, a solution to the equation x = 1. We can encode the state 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 his 0 22 right. Then we can look at the polynomial f ( x ) = a x + ... + a which still encodes 22 0 the state of the game. In this schema the original state is the constant 1, and we have at all times the condition f (1) = 1 (conservation of water). However, we want a cyclic representation in order to encode the play of the game, so we let the state of the game 22 be f ( ω ) = a ω + ... + a . In this representation, a step in the game can be encoded 22 0 22 as multiplication by another polynomial in ω , g ( ω ) = b ω + ... + b where the b 22 0 i are the fraction of water that Alex initially gives to the i -th person on his right. The 1 1 1 22 example in the problem is represented by ω + + ω . So we would like to know 6 3 2 23 which g are solutions to g ( ω ) = 1. We can take 23rd roots of both sides and find 22 k that g ( ω ) = b ω + ... + b = ω for some integer k. To simplify this we need a small 22 0 lemma. 2 22 Lemma : If a ω + ... + a is some rational linear combination of the powers of ω and 22 0 is equal to 0, then a = a = ... = a . 22 21 0 22 Proof: Assume this is false. So there exists some polynomial A ( x ) = a x + ... + a 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 all the terms in the algorithm have a root at ω and so does D ( x ). So since 0 is not an acceptable value for a G.C.D., D ( x ) must have degree 22. Since the degree of each successive 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 the original 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 i we get that b = 0 for i 6 = k and b = 1. Since this is a solution for all k, the possible i k schemes for Alex to use are just those involving giving all his water to any one other person. 3