PUMaC 2016 · 个人决赛（B 组） · 第 1 题

PUMaC 2016 — Individual Finals (Division B) — Problem 1

Let f ( n ) be the probability that, if k ∈ { 1 , 2 , . . . , 2 n } is randomly selected, then 1 + 2 + · · · + k will be divisible by n . Prove that f ( n ) is distinct for every positive integer n .

解析

is divisible by n if and only if k ( k + 1) is divisible by 2 n . Let 2 n = p p . . . p . Note m 1 2 2 that k and k + 1 are relatively prime, so the only way this is possible is if k is divisible by r i m some of the p and k + 1 is divisible by the others. There are 2 ways to break the factors up i like this, and each corresponds to exactly one k between 1 and 2 n , by the Chinese remainder m 2 theorem. Thus, f ( n ) = . It follows that f ( n ) = f ( n ) only if n and n are off by a power 1 2 1 2 2 n of 2. But observe that m is the same for all n ’s that are off by a power of 2, and so f ( n ) is distinct for all n , as desired. Problem written by Eric Neyman.