Maths Olympiad Prep

Library / /129 of 520

Combinatorics Difficulty 6.5 National olympiad Find the answer

Several children were playing in the ugly tree when suddenly they all fell.
 \bullet Roger hit branches AA, BB, and CC in that order on the way down.
 \bullet Sue hit branches DD, EE, and FF in that order on the way down.
 \bullet Gillian hit branches GG, AA, and CC in that order on the way down.
 \bullet Marcellus hit branches BB, DD, and HH in that order on the way down.
 \bullet Juan-Phillipe hit branches II, CC, and EE in that order on the way down.
Poor Mikey hit every branch A through II on the way down. Given only this information, in how many different orders could he have hit these 9 branches on the way down?

Solution

To solve this problem, we need to determine the number of different orders in which Mikey could have hit the branches AA through II while satisfying the given constraints. We will use the inequalities derived from the order in which each child hit the branches.

1. Derive Inequalities:
- Roger: A>B>CA > B > C
- Sue: D>E>FD > E > F
- Gillian: G>A>CG > A > C
- Marcellus: B>D>HB > D > H
- Juan-Phillipe: I>C>EI > C > E

2. Combine Inequalities:
From the given inequalities, we can combine them to form a single chain of inequalities:
- From Roger and Gillian: G>A>B>CG > A > B > C
- From Sue and Juan-Phillipe: I>C>E>FI > C > E > F
- From Marcellus: B>D>HB > D > H

Combining these, we get:
G>A>B>D>H>C>E>F G > A > B > D > H > C > E > F
and
I>C I > C

3. **Insert DD, HH, and II into the Chain:**
We need to insert DD, HH, and II into the chain while maintaining the order constraints.

- B>D>HB > D > H
- I>C>EI > C > E

4. Case Analysis:
We will analyze different cases based on the position of DD and II.

**Case 1: G>A>B>D>C>E>FG > A > B > D > C > E > F**
- D>HD > H
- I>CI > C

For D>HD > H:
- D>H>CD > H > C
- D>C>HD > C > H

For I>CI > C:
- II can be placed in 4 positions: before DD, before BB, before AA, or before GG.

Combining these, we get:
- D>H>I>CD > H > I > C
- D>I>H>CD > I > H > C
- D>I>C>H>E>FD > I > C > H > E > F
- D>I>C>E>H>FD > I > C > E > H > F
- D>I>C>E>F>HD > I > C > E > F > H

Total for this case: 55 ways.

**Case 2: G>A>B>C>D>E>FG > A > B > C > D > E > F**
- D>HD > H
- I>CI > C

For D>HD > H:
- D>HD > H can be placed in 3 positions: after DD, after EE, after FF.

For I>CI > C:
- II can be placed in 4 positions: before CC, before BB, before AA, before GG.

Total for this case: 3×4=123 \times 4 = 12 ways.

**Case 3: G>A>B>D>H>C>E>FG > A > B > D > H > C > E > F**
- I>CI > C

For I>CI > C:
- II can be placed in 6 positions: directly after HH, directly after DD, directly after BB, directly after AA, directly after GG, directly before GG.

Total for this case: 66 ways.

5. Summing Up:
Summing the number of ways from all cases:
5+12+6=23 5 + 12 + 6 = 23

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.