PUMaC 2020 · 组合（B 组） · 第 7 题

7. Jacob has a piece of bread shaped like a figure 8, marked into sections and all initially connected as one piece of bread. The central part of the “8” is a single section, and each of the two loops of “8” is divided into an additional 1010 pieces. For each section, there is a 50 percent chance that Jacob will decide to cut it out and give it to a friend, and this is done independently for each section. The remaining sections of bread form some number of connected pieces. If E is the expected number of these pieces, and k is the smallest positive integer so that k 2 ( E − b E c ) ≥ 1 , find b E c + k. (Here, we say that if Jacob donates all pieces, there are 0 pieces left). Proposed by Frank Lu Answer: 1515 . n ∑ Solution: Let n = 1010 for convenience. We compute the sum c , where c is the number k k k =0 of ways for Jacob to cut out the pieces to form k pieces. We divide this into two cases. First, if the middle piece is taken, notice that this can be viewed as having two “rows.” In this case, suppose that we have a pieces from one loop, and b connected pieces from the other loop. Then, notice that, along this row, we can split it up by considering the number of sections taken, going counterclockwise, from the the central (taken) piece to the first remaining piece, and so on. This can be viewed as some equation x + x + · · · + x = n, where the x ≥ 1 , 1 2 2 a +1 i ( ) ( ) n − 2 a +1+2 a n +1 save for x and x . We see that the number of solutions for this is = . 1 2 a +1 2 a 2 a ( ) n +1 Similarly, we see that for b this is . 2 b For the other case, if we have the middle piece, suppose that we have a other pieces not with the middle on one loop, and b on the other. We see that we have now two equations, again. ( ) n +1 On one hand, we have x + x + x + · · · + x + x = n, which again has solutions 0 1 2 2 a +1 2 a +2 2 a +2 to it. However, there is one slight issue here: notice that if we take a = 0 , we have another valid solution, namely with just x = 0 (so that the entire loop is taken). Similarly, we have 1 ( ) ( ) n +1 n +1 solutions in this case, where b 6 = 0 , and for b = 0 we have + 1 . 2 b +2 2 Notice that our expected value is thus ( )( ) ( )( ) n n n n ∑ ∑ ∑ ∑ n + 1 n + 1 n + 1 n + 1 ( a + b ) + ( a + b + 1) + 2 a 2 b 2 b + 2 2 a + 2 a =0 b =0 a =1 b =1 (( ) ) ( ) (( ) ) ( ) (( ) ) n n 2 ∑ ∑ n + 1 n + 1 n + 1 n + 1 n + 1 ( b +1) + 1 + ( a +1) + 1 + + 1 , 2 2 b + 2 2 2 a + 2 2 b =1 a =1 4 where we set the “invalid” binomial coefficients to just be 0 . But notice that we can write this sum as just ( )( ) ( )( ) n n n n ∑ ∑ ∑ ∑ n + 1 n + 1 n + 1 n + 1 ( a + b ) + ( a + b + 1) 2 a 2 b 2 b + 2 2 a + 2 a =0 a =0 b =0 b =0 ( ) ( ) ( ) n n ∑ ∑ n + 1 n + 1 n + 1

• ( b + 1) + ( a + 1) + 2 + 1 . 2 b + 2 2 a + 2 2 a =1 b =1 We can then further re-write this then as (( )( ) ( )( )) (( )( ) n n n n ∑ ∑ ∑ ∑ ( n + 1) n n + 1 n + 1 n ( n + 1) n n + 1

2 2 a − 1 2 b 2 a 2 b − 1 2 2 a − 1 2 b a =0 b =0 a =1 b =1 ( )( ) ( )( ) ( ( )) ( ) n n n ∑ ∑ ∑ n + 1 n n + 1 n + 1 n + 1 n n + 1

• − + 2 + 2 + 1 . 2 a 2 b − 1 2 b 2 a 2 2 b + 1 2 a =1 b =1 b =1 n ( ) ∑ n n − 1 Finally, noticing that = 2 , this can be written as 2 a a =0 ( ) ( ) n + 1 n + 1 2 n − 1 2 n − 1 n − 1 n n − 1 n · 2 + 2 + · 2 (2 − 1) + 2 (2 − 1) 2 2 ( ) ( ) n + 1 n ( n + 1) n + 1 n 2 n − 1 − (2 − 1) + 2 2 − + 2 + 1 . 2 2 2 2 n n +1 We do one last set of combinations of like terms to get n 2 + 2 . 2 n +1 Finally, to get the expected value, we divide by 2 , the number of total ways that we can 1 choose the pieces. This gives our expected value of n/ 2 + . Finally, plugging in our value of n 2 1 n gives 505 + , yielding our answer of 1515 . 1010 2