Collection of Maths Problems

Nationalities

Task number: 3490

• Variant

  A souvenir vendor has the following figures for sale: three identical figures of Pope John Paul II, four of Juraj Jánošík and five of the Good Soldier Švejk. In how many ways can he arrange the figures into a single row in a shop window such that all the figures of the same person never form a single contiguous block?

• Solution

  The total number of arrangements is \(\binom{12}{5{,}4,3}=27{,}720\).

  The number of arrangements in which all Švejks are adjacent is \(\binom{8}{1{,}4,3}=280\) (we can imagine the figure in the first group to be a single quintuple of Švejks). Similarly there are \(\binom{9}{5{,}1,3}=504\) arrangements in which all Jánošíks are adjacent, and \(\binom{10}{5{,}4,1}=1{,}260\) in which the popes are adjacent.

  If all Švejks are adjacent and at the same time all Jánošíks, there are \(\binom{5}{1{,}1,3}=20\) possible arrangements, similarly for Švejks and popes \(\binom{6}{1{,}4,1}=30\) and for Jánošíks and popes \(\binom{7}{5{,}1,1}=42\). If all types of figures form consecutive blocks, there are \(\binom{3}{1{,}1,1}=6\) possible arrangements.

  It remains to compute \(\binom{12}{5{,}4,3}-\binom{8}{1{,}4,3}-\binom{9}{5{,}1,3}-\binom{10}{5{,}4,1}+ \binom{5}{1{,}1,3}+\binom{6}{1{,}4,1}+\binom{7}{5{,}1,1}-\binom{3}{1{,}1,1}=\\ =27{,}720-280-504-1{,}260+20+30+42-6=25{,}762.\)

• Answer

  There are 25,762 possible arrangements.

• Variant

  In how many ways can we arrange 5 Czechs, 4 Slovaks a 3 Poles in a single line such that all the members of a single nationality never form a contiguous block?

  Unlike in the previous variant, all the people are mutually distinguishable.

• Solution

  There are a total of \(12!=479{,}001,600\) arrangements.

  The number of arrangements in which all Czechs are adjacent is \(5!8!=4{,}838,400\) (we can imagine the figure from the first group as a single quintuple of Czechs). Similarly there are \(4!9!=8{,}709,120\) arrangements in which all Slovaks are adjacent, and \(3!11!=21{,}772,800\) arrangements in which all Poles are adjacent.

  If all Czechs are adjacent and also all Slovaks, there are \(5!4!5!=345{,}600\) possible arrangements, similarly for Czechs and Poles \(5!3!6!=518{,}400\) and Slovaks and Poles \(4!3!7!=725{,}760\). If every nationality forms a contiguous block, there are \(5!4!3!3!=103{,}680\) possible arrangements.

  It remains to calculate \(12! - 5!8! - 4!9! - 3!11! + 5!4!5! + 5!3!6! + 4!3!7! - 5!4!3!3! \\ =479{,}001,600 - 4{,}838,400 - 8{,}709,120 - 21{,}772,800 + 345{,}600 + 518{,}400 + 725{,}760 - 103{,}680\\ = 445{,}167,360\).

  Alternatively we may reach the same result from the solution to the previous variant if we consider that distinguishing individual people gives us \(5!4!3!\) possibilities for each arrangement, i.e. multiplies the number of arrangements by a factor of 17,280.

• Answer

  The number of possible arrangements is 445,167,360.