Sample problem

Source: Harvard-MIT Math Tournament November 2020 general problem #8

Click for the solution

How many ways are there to divide the bar, along the edges of the triangles, into two or more contiguous pieces?

A bar of chocolates is made of 10 distinguishable triangles as shown below:

Can you solve this sample problem?

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 some other edge connecting to Y to be broken. We have 2^5 choices for the edges connecting to X, of which 1 fails. Similarly, we have 2^5 − 1 valid choices for the edges connecting to Y . This yields (2^5 − 1)^2 = 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 to X, we have 5 cases with exactly one broken edge. Thus, there are 2^5 − 5 = 27 ways to break the edges connecting to X. Similarly there are 27 valid choices for the edges connecting to Y . This yields 27^2 − 1 = 728 cases, once we subtract the situation where no edges are broken. The final answer is 961 + 728 = 1689.