Collection of Maths Problems

Sprites and witches

Task number: 3454

• Variant

  Let \(m=5, n=7\).

  Assume that the sprites are indistinguishable, as are the witches.

• Solution

  First put the witches into place. Now we have 8 positions for sprites, of which we will choose 5, i.e. \(\binom{8}{5}=56\).

  Alternatively, but a bit more complicated: First put the 5 sprites into place, with 4 witches between them. Now 3 witches remain; we have 6 positions for them, and at each position we need not add any witches but may add more than one witch. This is \(\binom{3+5}{3}=56\).

• Answer

  There are 56 possible arrangements of sprites and witches.

• Variant

  \( m = 5, n = 7 \), we arrange characters on a line, but they are all recognizable from each other.

• Solution

  Each of the 56 options of unrecognizable characters can be expanded in \( 5! \) ways by distinguishing water sprites. Next, we expand each of these possibilities in \( 7! \) ways by distinguishing witches.

• Answer

  There are \( 56 {\cdot} 5! \cdot 7! = 33{,}868,800 \) possible layouts.

• Variant

  \( m = 5, n = 7 \), water sprites, resp. witches are indistinguishable from each other, but we arrange them on a circle under the same condition that no two sprites are adjacent.

• Solution

  First we place the witches in a circle and we fill the sprites into the gaps. There are thus \(\binom{7}{5}=21\) possibilities.

  However in this counting some (in fact all) arrangements are counted more than once. The circle of witches doesn‘t have a unique ‘first‘ gap. We can choose this ‘first‘ gap in seven ways and so every arrangement is counted seven times.

  The number of distinct arrangements \(\frac{21}{7}=3\). That may seem to be too few, but in reality they are the three in the following diagram. Here, V (‘vodník‘) is a sprite and Č (‘čarodějnice‘) is a witch:

  

• Answer

  There are only three distinct arrangements.

• Variant

  \( m = 5, n = 10 \), sprites as well as witches are indistinguishable from each other, and we put them on a circle.

• Solution

  As in the previous example, we first compute the total number of arrangements, of which there are \(\binom{10}{5}=252\), and then we will count how many times each distinct arrangement was repeated in the total.

  But evidently we cannot divide by 10 representing the choice of the ‘first‘ gap, since the result would not be an integer. That‘s because one of the possible arrangements is repeated only twice. Specifically that is the arrangement containing alternately one sprite, two witches, one sprite, two witches and so on.

• Answer

  The resulting number of arrangements is \(\frac{2}{2}+\frac{250}{10}=26\).

• Variant

  \( m = 6, n = 12 \), sprites as well as witches are indistinguishable from each other, and we put them on a circle.

• Solution

  The total number of arrangements is \(\binom{12}{6}=924\).

  The following sequences are counted more than once:

  • [2x] S,W,W…
  • [4x] S,W,S,W,W,W…
  • [6x] S,W,S,W,S,W,W,W,W…
  • [6x] S,W,S,W,W,S,W,W,W…
  • [6x] S,W,S,W,W,W,S,W,W…
  • [12x] all others

  (For completness: the sequences S,W,W…, W,S,W… a W,W,S…, give the same cyclic arrangement. Similarly S,W,S,W,W,W,W,S,W… is identical to S,W,S,W,S,W,W,W,W…)

• Answer

  The resulting number of arrangements is \(\frac{2}{2}+\frac{4}{4}+\frac{6+6+6}{6}+\frac{900}{12}=80\).