4
$\begingroup$

I am trying to solve the puzzle below and am thinking that there ought to be some way of formulating it as a problem about counting matchings, but I can not make it work. I would appreciate a hint or a different strategy.

N premier league footballers, all with different birth dates, and a single female, Natasha, are to be seated at a round table. To avoid any footballers getting ignored, each footballer must either sit next to a younger footballer or to Natasha. In how many ways can the footballers and Natasha be seated?

  • 1
    I can't beat Michael's hint, but if it's a (directed) graph you want, set one up with a vertex for each person, an arc from each player to each younger player, and two-way arcs joining each player to Natasha; then you're asking for a Hamiltonian cycle.2011-06-10

1 Answers 1

1

Let's elaborate the hint of Michael Ulm:

  • We first seat Natasha, there are $N+1$ possibilities.
  • The youngest footballer cannot sit next to a younger footballer, so we must seat him next to Natasha. There are two possibilities.
  • The second youngest footballer can either sit next to Natasha or next to the youngest footballer. There are two possibilities.
  • The third youngest footballer must sit next to Natasha or to one the two youngest footballers. Since those three are already seated in a row, there are again two possibilities (the two empty seats next to them).

Going on like this, we have 2 possibilities for all footballers up to the second oldest one. The oldest footballer goes to the last empty seat.

So the total number of possibilities is $ (N+1)\cdot 2^{N-1}. $