United States of America Mathematical Talent Search - Problem 1/1/24

1/1/24. Several children were playing in the ugly tree when suddenly they all fell.
• Roger hit branches Α, Β and Γ in that order on the way down.
• Sue hit branches Δ, E, and Φ in that order on the way down.
• Gillian hit branches Κ, A, and Γ in that order on the way down.
• Marcellus hit branches B, Δ, and H in that order on the way down.
• Juan-Phillipe hit branches I, Γ, and E in that order on the way down.
Poor Mikey hit every branch on the way down. Given only this information, in how many different orders could he have hit the 9 branches on his way down?

This is one of those beautiful combinatorial problems, that require a full and analytical solution through logic. No formula could give one a full solution. I solved this problem together with Demetres some day in July through Skype. Here's our solution.

From the hypothesis we can say that:

The possible configurations including Δ are:

The possible configurations including I are:

The possible configurations including Δ and H are:

We can now multiply the possible configurations including Δ and H with the first three possible configurations including I. From this we get a total of 21 possible configurations. For the last possible configuration including I we must take two cases: I will either be before or after Δ. Working similarly, we get 12 possible configurations.

In conclusion, the total amount of possible configurations is 21+12=33.