HMMT 二月 2016 · 冲刺赛 · 第 29 题

HMMT February 2016 — Guts Round — Problem 29

[ 16 ] Katherine has a piece of string that is 2016 millimeters long. She cuts the string at a location chosen uniformly at random, and takes the left half. She continues this process until the remaining string is less than one millimeter long. What is the expected number of cuts that she makes?

解析

[ 16 ] Katherine has a piece of string that is 2016 millimeters long. She cuts the string at a location chosen uniformly at random, and takes the left half. She continues this process until the remaining string is less than one millimeter long. What is the expected number of cuts that she makes? Proposed by: Answer: 1 + log(2016) Letting f ( x ) be the expected number of cuts if the initial length of the string is x , we get the integral ∫ ∫ x x 1 1 equation f ( x ) = 1 + f ( y ) dy . Letting g ( x ) = f ( y ) dy , we get dg/dx = 1 + g ( x ). Using x 1 1 x integrating factors, we see that this has as its solution g ( x ) = x log( x ), and thus f ( x ) = 1 + log( x ).