HMMT 十一月 2020 · GEN 赛 · 第 8 题

HMMT November 2020 — GEN Round — Problem 8

A bar of chocolate is made of 10 distinguishable triangles as shown below: How many ways are there to divide the bar, along the edges of the triangles, into two or more contiguous pieces?

解析

A bar of chocolate is made of 10 distinguishable triangles as shown below: How many ways are there to divide the bar, along the edges of the triangles, into two or more contiguous pieces? Proposed by: Steven Noah Raphael Answer: 1689 Solution: Every way to divide the bar can be described as a nonempty set of edges to break, with the condition that every endpoint of a broken edge is either on the boundary of the bar or connects to another broken edge. Let the center edge have endpoints X and Y . We do casework on whether the center edge is broken. If the center edge is broken, then we just need some other edge connecting to X to be broken, and 5 some other edge connecting to Y to be broken. We have 2 choices for the edges connecting to X , 5 of which 1 fails. Similarly, we have 2 − 1 valid choices for the edges connecting to Y . This yields 5 2 (2 − 1) = 961 possibilities. If the center edge is not broken, then the only forbidden arrangements are those with exactly one broken edge at X or those with exactly one broken edge at Y . Looking at just the edges connecting 5 to X , we have 5 cases with exactly one broken edge. Thus, there are 2 − 5 = 27 ways to break the edges connecting to X . Similarly there are 27 valid choices for the edges connecting to Y . This yields 2 27 − 1 = 728 cases, once we subtract the situation where no edges are broken. The final answer is 961 + 728 = 1689.