PUMaC 2017 · 组合（B 组） · 第 3 题

PUMaC 2017 — Combinatorics (Division B) — Problem 3

There are 2017 turtles in a room. Every second, two turtles are chosen uniformly at random and combined to form one super-turtle. (Super-turtles are still turtles.) The probability that after 2015 seconds (meaning when there are only two turtles remaining) there is some turtle p that has never been combined with another turtle can be written in the form where p and q q are relatively prime positive integers. Find p + q .

解析

Fix a particular turtle. The probability it does not get combined with another turtle when 2 there are n total turtles is 1 − . Therefore, the probability it is not combined in 2015 seconds n is ( ) 2014 2014 ∏ ∏ 2 2015 − k 2 1 − = = . 2017 − k 2017 − k (2017)(2016) k =0 k =0 Since it is impossible for more than one turtle to never be combined, the desired probability is 2 1 2017 = . (2017)(2016) 1008 So our final answer is 1 + 1008 = 1009 . Problem written Matt Tyler