PUMaC 2021 · 团队赛 · 第 14 题
PUMaC 2021 — Team Round — Problem 14
题目详情
- Heron is going to watch a show with n episodes which are released one each day. Heron wants to watch the first and last episodes on the days they first air, and he doesn’t want to have two days in a row that he watches no episodes. He can watch as many episodes as he wants in a day. Denote by f ( n ) the number of ways Heron can choose how many episodes he watches each day satisfying these constraints. Let N be the 2021st smallest value of n where f ( n ) ≡ 2 mod 3. Find N . ◦ ◦
解析
- Heron is going to watch a show with n episodes which are released one each day. Heron wants to watch the first and last episodes on the days they first air, and he doesn’t want to have two days in a row that he watches no episodes. He can watch as many episodes as he wants in a day. Denote by f ( n ) the number of ways Heron can choose how many episodes he watches each day satisfying these constraints. Let N be the 2021st smallest value of n where f ( n ) ≡ 2 mod 3. Find N . Proposed by: Daniel Carter Answer: 265386 Let a ( x, y ) be the number of ways Heron can watch episodes through the x th day such that he watches at least one episode on the x th day and there are y episodes he has left to watch after the x th day. We have a (1 , 0) = 1 and f ( n ) = a ( n, 0). P P We also have the recurrence a ( x, y ) = a ( x − 1 , z )+ a ( x − 2 , z ): the first sum counts z ≥ x z ≥ x − 1 the number of ways Heron could have watched an appropriate number of episodes assuming he watched at least one on day x − 1 and the second sum counts the number assuming he did not watch any episode on day x − 1. Given this, one can easily prove the simpler recurrence a ( x, y ) = a ( x − 2 , y − 1) + a ( x − 1 , y ) + a ( x, y + 1). Now one may iterate this recurrence many times to find a ( x, y ) = a ( x − 2 , y − 1) + a ( x − P x − 2 1 , y ) + a ( k, 0) a ( x − k − 1 , y ) (this process is similar to the process one may use to prove k =1 certain identities of the binomial coefficient). In particular this holds for y = 0, whence P n − 2 f ( n ) = f ( n − 1) + f ( k ) f ( n − k − 1). k =1 Then one may prove the sequence ( f ( n ) mod 3)) is as follows: - Begin with 1 , 1 , 2 , 1. - n Append 3 · 1 copies of 0. - Append 1 , 2 , 1 , 1 , 2 , 1. - Append 3 · 4 copies of 0. - Append 1 , 2 , 1 , 1 , 2 , 1. - Append 3 · 1 copies of 0. - etc. The number of zeros added every other step is b n 3 · (3 − 1) / 2, where b = (1 , 2 , 1 , 3 , 1 , 2 , 1 , 4 ... ) is often known as the ”ruler sequence.” Then n one may prove the value of n corresponding to the m th occurrence of 2 is equal to 3 M where the ternary digits of M are the same as the binary digits of m . 7 In our case, m = 2021 = 11111100101 , so M = 11111100101 = 88462, and our answer is 2 3 3 M = 265386. ◦ ◦