PUMaC 2020 · 组合（A 组） · 第 3 题
PUMaC 2020 — Combinatorics (Division A) — Problem 3
题目详情
- Katie has a chocolate bar that is a 5-by-5 grid of square pieces, but she only wants to eat the center piece. To get to it, she performs the following operations: i. Take a gridline on the chocolate bar, and split the bar along the line. ii. Remove the piece that doesn’t contain the center. iii. With the remaining bar, repeat steps 1 and 2. Determine the number of ways that Katie can perform this sequence of operations so that eventually she ends up with just the center piece.
解析
- Katie has a chocolate bar that is a 5-by-5 grid of square pieces, but she only wants to eat the center piece. To get to it, she performs the following operations: i. Take a gridline on the chocolate bar, and split the bar along the line. ii. Remove the piece that doesn’t contain the center. iii. With the remaining bar, repeat steps 1 and 2. Determine the number of ways that Katie can perform this sequence of operations so that eventually she ends up with just the center piece. Proposed by Frank Lu Answer: 6384 . 1 Solution: Note that each sequence of operations is uniquely determined by which line Katie breaks along at each step, so we consider sequences of lines. Label the horizontal lines from top to bottom l , l , l , l , and the lines from left to right m , m , m , m . Since Katie ends up 1 2 3 4 1 2 3 4 with the center piece, the four lines that bound the center, l , l , m , m must have all been 2 3 2 3 broken along. Observe that if l was also broken along, it would have had to been before l , 1 2 as no portion of l exists on the same side of l as the center piece. A similar logic holds 1 2 for l , m , m with l , m , m , respectively. Note that beyond this restriction, however, every 4 1 4 3 2 3 sequence of these lines is a valid sequence of breaks (we can imagine as though Katie makes knife cuts through the whole bar first before taking out just the center piece). If Katie makes ( ) 4 i cuts, 4 ≤ i ≤ 8, then we have ways to pick which of the four lines that don’t bound i − 4 i − 4 the center have cuts made. Then, of i ! ways to arrange these lines, we divide by 2 to account for the fact that there is only one allowed relative ordering between an outer line and its corresponding inner line. This yields the following sum: 5! 6! 7! 8! 1 · 4! + 4 · + 6 · + 4 · + = 24 + 240 + 1080 + 2520 + 2520 = 264 + 5040 + 1080 = 6384 . 2 4 8 16