PUMaC 2021 · 组合（A 组） · 第 2 题
PUMaC 2021 — Combinatorics (Division A) — Problem 2
题目详情
- Eighteen people are standing in a (socially-distanced) line to enter a grocery store. Five people are wearing a black mask, 6 are wearing a gray mask, and 7 are wearing a white mask. Suppose that these 18 people got on line in a random order. The expected number of pairs of adjacent a people wearing different-colored masks can be given by , where gcd( a, b ) = 1. Compute a + b . b
解析
- Change the first bit after the first 1 . Let M be the minimum number of such moves it takes to get from 1 . . . 1 to 0 . . . 0 (both of length 12), and N the number of starting sequences with 12 bits that Cassidy can turn into all 0s. Find M + N. Proposed by: Frank Lu Answer: 6826 To show that one such sequence exists, we employ induction. Our base cases are n = 1 and n = 2 , which are clear. Now, suppose that it is possible to do this for all n ≤ k. For the string with k + 1 bits, we can perform the following procedure using our inductive hypothesis. First, turn the first k − 1 bits into all zeroes. Then, convert the k + 1st bit into a zero using the second step. From here, turn the first k − 1 bits back into ones; this is possible from the fact that both of these steps are involutions, so they their own inverses (so reversing the moves used to go from all 1s to all 0s will perform this). The result is k 1s followed by a 0 , which again can be turned into all 0s by the inductive hypothesis. Thus, we have N = 4096 . To compute M, notice that in order to turn our sequence into all zeroes, we need to reach the state 00 . . . 011 , in order to turn the last bit into a 0 . Let a be the minimal number of moves n it takes to go from 11 . . . 1 to 00 . . . 0 , and b the minimal number of moves it takes to go from n 00 . . . 01 to 00 . . . 0 . Then, we see that a = a + 1 + b , using the above logic. We just n n − 2 n − 1 need to find b now. n For b , in order to reach all zeroes, the same logic tells us that we need to first go from 00 . . . 01 n to 00 . . . 011 , which takes b moves. Applying the logic above yields us that b = 2 b + 1 . n − 1 n n − 1 Substituting in the first recurrence yields us with the linear recurrence a − 2 a − a + n +1 n n − 1 2 a = 0 . Using the theory of linear recurrences, we know that this takes the form a = n − 2 n n n n 3 2 c r + c r + c r , where the r are roots of the equation r − 2 r − r + 2 = 0 . But these roots 1 2 3 i 1 2 3 n n are 2 , 1 , − 1 . Therefore, we have that a = c 2 + c + c ( − 1) . n 1 2 3 We just need to find the value of these c . It’s not hard to manually compute that a = 1 , a = i 1 2 2 , a = 5 . Substituting these values into the above recurrence and solving the resulting system 3 n +1 n +1 ( − 1) 2 1 8192 1 1 8190 yields a = − + . Substituting n = 12 yields a = − − = = 2730 . n 12 3 2 6 3 2 6 3 So our answer is 4096 + 2730 = 6826 .