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 contiguouspieces?
解析
英文解析
- 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 contiguouspieces?
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 toanother 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, andsome 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
5 2
(2 − 1) = 961 possibilities.
If the center edge is not broken, then the only forbidden arrangements are those with exactly onebroken edge at X or those with exactly one broken edge at Y . Looking at just the edges connectingto X , we have 5 cases with exactly one broken edge. Thus, there are 2 − 5 = 27 ways to break the 5
edges connecting to X . Similarly there are 27 valid choices for the edges connecting to Y . This yields
27 − 1 = 728 cases, once we subtract the situation where no edges are broken.2
The final answer is 961 + 728 = 1689.