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:

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!).