Dancing order
Task number: 4514
The dance course covers standard dances: waltz, tango, Viennese waltz, slowfox and quickstep; Latin dances: cha-cha, rumba, jive; as well as polka, bachata, blues and country. Of these dances, the Viennese waltz, quickstep and jive are significantly faster than the others.
The program for the final ball is divided into several blocks of six dances. No block starts with a fast dance, and no two fast dances are in a row.
How many ways can all 12 dances be arranged in the first two blocks according to the above conditions, so that country is the last dance in the second block just before the break, as is the custom in the course?
Solution
We can narrow the task down to the placement of the 11 dances, because we have no other position for country than the last 12th.
First, we note that if each selected position for fast and slow dances corresponds to \(3!8!\) possibilities to deploy fast and slow dances respectively in these positions.
We distinguish four cases in the solution according to the number of fast dances in the first and second blocks:
If there are three fast dances in the first block, they must be in the 2nd, 4th and 6th positions, all the other dances are slow dances, so it is one choice of positions for the fast dances.
We can simplify the analysis if we consider the following fact: If there is a block of \(f\) fast dances and \(s\) slow dances, then after each slow dance is a potential position for a fast dance. The number of possible positions for the fast ones is given by the expression \(\binom{s}{f}\), because we first arrange the slow dances and then select those that will always be followed by a fast dance.
For two fast dances in the first block and one in the second, we get \(\binom{4}{2}\binom{4}{1}\) possibilities. For placing one fast in the first block and two in the second, we get \(\binom{5}{1}\binom{3}{2}\) possibilities. It is not possible to have three quick dances in the second block, because then two quick dances would be consecutive or the block would start with a quick one.
Answer
The total number of possibilities for the first two blocks of the dance order is \(3!8!\left(1+ \binom{4}{2}\binom{4}{1}+\binom{5}{1}\binom{3}{2}\right)=9\,676\,800\).
Variant
How would the calculation change if we additionally require that both standard and Latin dances form continuous pairs or triples within the block? (Having more than three in a block or just one in a row would not fit in the program.)Answer
In total, there are \(59\,904\) ways to assemble the first two blocks of the program.Comment
For the complete case analysis see the Czech version.
The variation of the problem illustrates how a quite natural additional condition can complicate the analysis of cases.
It would also be possible to use the principle of inclusion and exclusion, but the analysis would probably be similarly complicated.
