PUMaC 2022 · 团队赛 · 第 4 题
PUMaC 2022 — Team Round — Problem 4
题目详情
- Patty is standing on a line of planks playing a game. Define a block to be a sequence of adjacent planks, such that both ends are not adjacent to any planks. Every minute, a plank chosen uniformly at random from the block that Patty is standing on disappears, and if Patty is standing on the plank, the game is over. Otherwise, Patty moves to a plank chosen uniformly at random within the block she is in; note that she could end up at the same plank from which she started. If the line of planks begins with n planks, then for sufficiently large n , the expected number of minutes Patty lasts until the game ends (where the first plank disappears a minute after the game starts) can be written as P (1 /n ) f ( n ) + Q (1 /n ), where P, Q are polynomials P n 1 and f ( n ) = . Find P (2023) + Q (2023). i =1 i 2 iπ/ 13 10 iπ/ 13 16 iπ/ 13 24 iπ/ 13
解析
- Patty is standing on a line of planks playing a game. Define a block to be a sequence of adjacent planks, such that both ends are not adjacent to any planks. Every minute, a plank chosen uniformly at random from the block that Patty is standing on disappears, and if Patty is standing on the plank, the game is over. Otherwise, Patty moves to a plank chosen uniformly at random within the block she is in; note that she could end up at the same plank from which she started. If the line of planks begins with n planks, then for sufficiently large n , the expected number of minutes Patty lasts until the game ends (where the first plank disappears a minute after the game starts) can be written as P (1 /n ) f ( n ) + Q (1 /n ), where P, Q are polynomials P n 1 and f ( n ) = . Find P (2023) + Q (2023). i =1 i Proposed by Frank Lu Answer: 4045 Let E ( n ) be the expected value given that the block that Masie is standing on has length n. Then, notice that if the i th plank from the left disappears, then the expected number of minutes i − 1 n − i that Masie lasts afterwards is equal to E ( i )+ E ( n − i ); therefore, we see that we have that n n P P n n − 1 1 i − 1 n − i 2 2 E ( n ) = ( E ( i )+ E ( n − i )+1) . Therefore, we see that n E ( n ) = n + 2 jE ( j ) . i =1 j =0 n n n 2 2 In particular, we therefore see that ( n + 1) E ( n + 1) − n E ( n ) = 2 nE ( n ) + 2 n + 1 . Now, let nE ( n ) 2 n +1 3 1 F ( n ) = ; it therefore follows that F ( n + 1) − F ( n ) = = − . However, n +1 ( n +1)( n +2) n +2 n +1 n − 1 P 1 1 3 1 we also know that E (1) = 1 , so F (1) = . It therefore follows that F ( n ) = + − = 2 2 n +2 n +1 j =1 2 n P 1 3 1 2 3 3
- − = + 2 f ( n ) − 3 . But this means then that E ( n ) = (( n + 1) /n )( + 2 n +1 2 i n +1 n +1 j =3 2 f ( n ) − 3) = (2 + 2 /n ) f ( n ) + 3 /n − 3( n + 1) /n = (2 + 2 /n ) f ( n ) − 3 . But therefore we see that P ( x ) = 2 + 2 x, Q ( x ) = − 3 , and so therefore we have that our answer is 2 + 2 · 2023 − 3 = 4045. 2 iπ/ 13 10 iπ/ 13 16 iπ/ 13 24 iπ/ 13