PUMaC 2016 · 组合（B 组） · 第 7 题

PUMaC 2016 — Combinatorics (Division B) — Problem 7

Let a , a , a , . . . be an infinite sequence where for all positive integers i , a is chosen to be a 1 2 3 i random positive integer between 1 and 2016, inclusive. Let S be the set of all positive integers k such that for all positive integers j < k , a 6 = a . (So 1 ∈ S ; 2 ∈ S if and only if a 6 = a ; j k 1 2 p 3 ∈ S if and only if a 6 = a and a 6 = a ; and so on.) In simplest form, let be the expected 1 3 2 3 q number of positive integers m such that m and m + 1 are in S . Compute pq .

解析

Let s be the k th element of S (ordered by size). k elements of { 1 , . . . , 2016 } appear among k { a , a , . . . , a } , so the probability that a has not appeared among { a , a , . . . , a } is 1 2 s s +1 1 2 s k k k 2016 − k , and this is the probability that s + 1 is also in S . Thus, by linearity of expectation, k 2016 p 2015 2014 1 2015 · 2016 2015 we have = + + · · · + = = , so pq = 4030 . q 2016 2016 2016 2 · 2016 2 Problem written by Eric Neyman.