Question

In a futuristic dystopian Chicago, society is divided into five factions: Abnegation, Amity, Candor, Dauntless and Erudite. At the age of 16, each person is allowed to choose any faction as their permanent social group at the Choosing Ceremony.

This year, there are 25 candidates at the ceremony, including Tris, Caleb, Christina, and Peter. All 25 candidates get called up one at a time to pledge themselves to the faction that they want to join.

a)How many ways are there to select 6 candidates to join Dauntless?

b)How many ways are there to distribute all 25 candidates into factions such that Tris and Caleb belong to different factions?

c)How many ways are there to distribute all 25 candidates into factions if there is at least one candidate in Dauntless and at least one candidate in Erudite?

d)For every fixed call order, how many ways are there to distribute all 25 candidates into factions such that nobody joins the same faction as the person called up just before them?

Answer 1

a) Total number of ways to select 6 candidates out of 25 to join Dauntless is

C 177100

b) There are 5 ways to pick a faction for Tris and 4 ways to pick a faction for Caleb from the remaining four. Then we can distribute the rest into any of the five factions.

hence the total number of ways is

F24

c)

We will be using inclusion-exclusion.

Let A be the collection of the distributions of 25 candidates into factions such that none is in Dauntless.Then

A42

Let B be the collection of the distributions of 25 candidates into factions such that none is in Erudite.Then

B 는 425

$A\cap B$ is the set of distributions of 25 candidates into factions such that no one is in Dauntless and none is in Erudite. Here,$\mid A\cap B\mid =3^{25}$

hence the total number of ways there are to distribute all 25 candidates into factions if there is at least one candidate in Dauntless and at least one candidate in Erudite =

5* -2* 425 325

d) There are 5 ways to pick a faction for the first person.

For each of the remaining candidates, there are 4 ways to pick a faction that is not the same as the one chosen by the person beforethem.

Hence there is a total of

5 424