Maths Olympiad Prep

Library / /273 of 348

Combinatorics Difficulty 5.1 AIME, harder Find the answer

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 number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

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 XX and YY. 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 XX to be broken, and some other edge connecting to YY to be broken. We have 252^{5} choices for the edges connecting to XX, of which 1 fails. Similarly, we have 2512^{5}-1 valid choices for the edges connecting to YY. This yields (251)2=961\left(2^{5}-1\right)^{2}=961 possibilities. If the center edge is not broken, then the only forbidden arrangements are those with exactly one broken edge at XX or those with exactly one broken edge at YY. Looking at just the edges connecting to XX, we have 5 cases with exactly one broken edge. Thus, there are 255=272^{5}-5=27 ways to break the edges connecting to XX. Similarly there are 27 valid choices for the edges connecting to YY. This yields 2721=72827^{2}-1=728 cases, once we subtract the situation where no edges are broken. The final answer is 961+728=1689961+728=1689.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.