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?

  • 3
    Here is a hint: First seat Natasha. The youngest player must sit next to Natasha (why?). Once you seated Natasha and the youngest player, what can you say about the rest of the players?2011-06-10
  • 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