Solutions for Permutation Assignment questions


Lots of people were looking for solutions for three of the questions on the Permutations assignment, and I promised I’d post them here.

It’s possible I’ve made some kind of mechanical error here, but the solutions are otherwise correct. Please let me know if there are mistakes you notice. Thanks!

Question 5

“The school is trying to buy combination locks for each student. There are 1200 students in the school. If each combination is made up of 3 numbers, and no two consecutive numbers can be the same, what is the minimum number of positions the lock should have?”

Considering each of the numbers in the combination in order, there are

n \times (n-1) \times (n-1)

combinations that satisfy the restriction for a lock with n positions. This can be solved for its roots (there is one real number and two imaginary numbers), but this isn’t necessary. Instead, since the number of positions is a natural number, we try some and find by trial-and-error that 11 positions yields 1100 combinations (too few) and 12 positions yields 1452 combinations (enough).

Question 7

“School Council has 24 members. There are 6 students per grade: 3 male and 3 female. The school has the following numbers of students in each grade:

Grade Male students Female student
9 91 85
10 102 115
11 75 74
12 147 133

How many different ways can School Council be selected?”

Now that we know about combinations this can be solved more easily, but we can still use permutations to solve it.

Consider a grade and gender, say Grade 9 Male. There are 91 candidates and 3 positions to fill. Dividing by 3! to account for duplicate arrangements, there are

\frac {91 \times 90 \times 89}{3!} = 242970

possible ways to select the three Grade 9 male students.

Applying the same reasoning to the other categories of students we see the following:

Grade 9 Male: 242970

Grade 9 Female: 98770

Grade 10 Male: 171700

Grade 10 Female: 246905

Grade 11 Male: 67525

Grade 11 Female: 64824

Grade 12 Male: 518665

Grade 12 Female: 383306

To find the total number of possible committees, we multiply all of these values together (Fundamental Counting Principle) to get approximately

8.85 \times 10^{41} .

Question 8

“At a wedding, the 10 members of the Jones family is seated at a round table. Jesse Jones and Kurt Jones can’t sit next to each other, and neither can Monica Jones and Nellie Jones. How many different seating arrangements are possible? The tables are round, so rotating positions does NOT count as another arrangement.”

Rotating positions not counting as another arrangement is very important here.

First, there are

\frac{10!}{10} = 362 880

possible, unique arrangements (dividing by 10 takes into account the rotations).

From this we’ll remove the arrangements with Jesse (J) and Kurt (K) together, and the arrangements with Monica (M) and Nellie (N) together. Last we’ll add back in the arrangements with J and K together AND M and N together (as these have been subtracted twice).

J and K

There are two ways to approach this case.

First, consider J and K as a single item to be placed. Then there are 8! ways to arrange the remaining guests. Since there are two ways to arrange J and K (JK and KJ), there are

2 \times 8! = 80 640

arrangements with J and K together.

The second approach is to place J and then notice there are two possible seats for K (either side of J). There are then 8! ways to arrange the remaining guests, giving once again

2 \times 8! = 80 640

arrangements with J and K together.

Note that both of these approaches take the roundness of the table into account, since we don’t count “initial” seats for J and/or K.

M and N

The very same logic yields 80640 arrangements with M and N together.

JK with MN

Let’s use the first approach to calculate this. Place JK together, then place MN in the adjacent two seats. There are 4 orders that their four seats can be filled:

JKMN

KJMN

JKNM

KJNM

There are 6! ways to arrange the remaining guests, giving

4 \times 6! = 2880

arrangements with J&K and M&N.

The total

So there are

362 880 - 80 640 - 80 640 + 2880 = 204 480

arrangements in which everyone is happy.

Whoa, sir – that’s long!

That is a little long, but it’s an assignment – I’m allowed to do that, since you had five days to complete it. Also, this is a very complete solution, with lots of words. I don’t expect quite this level of detail from you (although I would be overjoyed to see it!).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s