Подсказка к задаче 110

Попробуйте решить эту задачу рекуррентно, то есть, если мы знаем ответ для n человек, то какой ответ будет для n+1 человека?