COMAPR07 - Editorial

com2018
comapr07
editorial
maths
medium
number-theory

#1

PROBLEM LINK:

Practice

Contest

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.