Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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? –  Michael Ulm Jun 10 '11 at 10:38
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. –  Gerry Myerson Jun 10 '11 at 12:21
add comment

1 Answer 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}. $$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.