2007 Indonesia MO Problems/Problem 4

Revision as of 14:28, 17 February 2020 by Rockmanex3 (talk | contribs) (Solution to Problem 4 — short counting problem)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)


A 10-digit arrangement $0,1,2,3,4,5,6,7,8,9$ is called beautiful if (i) when read left to right, $0,1,2,3,4$ form an increasing sequence, and $5,6,7,8,9$ form a decreasing sequence, and (ii) $0$ is not the leftmost digit. For example, $9807123654$ is a beautiful arrangement. Determine the number of beautiful arrangements.


To start, the first digit of the arrangement must be a 9. For the next nine digits, five of them are in the set $\{ 0,1,2,3,4 \}$ and four of them are in the set $\{ 5,6,7,8 \}$.

We can approach counting the number of beautiful arrangements by counting the number of ways to arrange 5 blue balls and 4 blue balls because by letting the blue balls represent elements in the set $\{ 0,1,2,3,4 \}$ and letting the red balls represent elements in the set $\{ 5,6,7,8 \}$, there is only one way to order the elements in each set.

With this one-to-one correspondence, there are $\binom{9}{5} = \boxed{126}$ beautiful arrangements.

See Also

2007 Indonesia MO (Problems)
Preceded by
Problem 3
1 2 3 4 5 6 7 8 Followed by
Problem 5
All Indonesia MO Problems and Solutions