PUMaC 2015 · 代数（A 组） · 第 5 题

PUMaC 2015 — Algebra (Division A) — Problem 5

[ 5 ] Since counting the numbers from 1 to 100 wasn’t enough to stymie Gauss, his teacher 2 πi/ 15 devised another clever problem that he was sure would stump Gauss. Defining ζ = e 15 √ k where i = − 1, the teacher wrote the 15 complex numbers ζ for integer 0 ≤ k < 15 on the 15 board. Then, he told Gauss: On every turn, erase two random numbers a, b , chosen uniformly randomly, from the board and then write the term 2 ab − a − b + 1 on the board instead. Repeat this until you have one number left. What is the expected value of the last number remaining on the board? 3 2 2 3 2

解析

[ 5 ] Since counting the numbers from 1 to 100 wasn’t enough to stymie Gauss, his teacher 2 πi/ 15 devised another clever problem that he was sure would stump Gauss. Defining ζ = e 15 √ k where i = − 1, the teacher wrote the 15 complex numbers ζ for integer 0 ≤ k < 15 on the 15 board. Then, he told Gauss: On every turn, erase two random numbers a, b , chosen uniformly randomly, from the board and then write the term 2 ab − a − b + 1 on the board instead. Repeat this until you have one number left. What is the expected value of the last number remaining on the board? Solution: If we let the operation be defined as a b = 2 ab − a − b + 1, then it can be shown that is associative and commutative. Therefore we will get the same value regardless of how we erase the elements from the board. Then given an arbitrary sequence of numbers a , a , · · · , a , it 1 2 n is not hard to show by induction that: n ∏ n − 1 a a · · · a = 2 ( a − 1 / 2) + 1 / 2 1 2 n i i =1 Therefore we have that: 14 ∏ 0 1 14 14 k ζ ζ · · · ζ = 2 ( ζ − 1 / 2) + 1 / 2 15 15 15 15 k =0 But we can factor: 14 ∏ 15 k 1 − x = ( ζ − x ) 15 k =0 And hence our answer is: 14 ∏ 14 k 14 15 14 2 ( ζ − 1 / 2) + 1 / 2 = 2 (1 − (1 / 2) ) + 1 / 2 = 2 = 16384 15 k =0 Author: Roy Zhao 3 2 2 3 2