PROBLEM LINK:
Author: Raj Ranjan
Editorialist: Raj Ranjan
DIFFICULTY:
MEDIUM.
PREREQUISITES:
Maths, Number Theory
PROBLEM:
The aim is to find the number of ways to such that everyone has a unique seat.
EXPLANATION:
The trick is to add an extra seat, and the plane is now circular. Now the number of ways such that n + 1-th seat becomes empty is our number of ways to satisfy the condition. For each seat there is ( (((2*(p+1))^q)*(p+1-q))/(p+1) ) ways such that this seat becomes empty.
(2*(p+1))^q - — The ways of assignment without restrictions.
(p+1-q) — As there are (n+1-m) seats remain empty at the end, and again, they have the equal chance of being empty, so the ways of assignment that leaves a particular seat empty is multiplied by (p+1-q).
1/(p+1) — Note that as the seats are in a ring, each of them have an equal chance of being empty.
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.