返回题库

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

HMMT November 2020 — GEN Round — Problem 8

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. 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?
解析

英文解析

  1. 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.