Combinatorics for RMO and IITJEE maths

Problem:

How many arrangements of 5 \alpha‘s, 5 \beta‘s and \gamma‘s are there with at least one \beta and at least one \gamma between each successive pair of \alpha‘s?

Solution:

There are three cases:

  1. Exactly one \beta and one \gamma between each pair of \alpha‘s: Between each of the four pairs of \alpha‘s, the \beta or the \gamma can be first — 2^{4} ways. The fifth \beta and fifth \gamma along with the sequence of the rest of the letters can be considered as 3 objects to be arranged — 3! ways. Altogether, 2^{4} \times 3!=96 ways.
  2. Exactly, one \beta between each pair of \alpha‘s and two \gamma‘s between some pair of \alpha‘s (or two \beta‘s between some pair of \alpha‘s and exactly one \gamma between each pair of \alpha‘s): there are four choices for between which pair of \alpha‘s the two \gamma‘s go and 3 ways to arrange the two \gamma‘s and one \beta there. There are two 2^{3} choices for whether the \beta or the \gamma goes first between the other 3 pairs of \alpha‘s and 2 choices for at which end of the arrangement the fifth \beta goes. Multiplying by 2 for the case of two \beta‘s between some pair of \alpha‘s, we obtain 2 \times (4 \times 3 \times 2^{3} \times 2)=384 ways.
  3. Two \beta‘s between some pair of \alpha‘s and two \gamma‘s between some pair of \alpha‘s. There are two subcases. If the two \beta‘s and two \gamma‘s are between the same pair of \alpha‘s, there are 4 choices for which pair of \alpha‘s, C(4,2) ways to arrange them between this pair of \alpha‘s, and 2^{3} choices for whether the \beta or the \gamma goes first between the other 3 pairs of \alpha‘s. If two \beta‘s and two \gamma‘s are between the different pairs of \alpha‘s, there are 4 \times 3 ways to pick between which \alpha‘s  the two \beta‘s and then between which \alpha‘s the two \gamma‘s go, 3^{2} ways to arrange the two \gamma‘s and one \beta and to arrange the one \gamma and two \beta‘s, and 2^{2} choices for whether the \beta or the \gamma goes first between the other 2 pair of \alpha‘s. Together, 4 \times C(4,2) \times 2^{3} + 4 \times 3 \times 3^{2} \times 2^{2}=1056 ways.

All together, the three cases give us a total of 96+384+1056=1536 arrangements.

More later,

Nalin Pithwa

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s