Permutations & Arrangements

6. \(\begin{array} { l l l l l l l l l l } 55 & 80 & 25 & 84 & 25 & 34 & 17 & 75 & 3 & 5 \end{array}\)

1. The list of numbers above is to be sorted into descending order. Perform a bubble sort to obtain the sorted list, giving the state of the list after each complete pass. The numbers in the list represent weights, in grams, of objects which are to be packed into bins that hold up to 100 g .
2. Determine the least number of bins needed.
3. Use the first-fit decreasing algorithm to fit the objects into bins which hold up to 100 g .

8. A company makes three sizes of lamps, small, medium and large. The company is trying to determine how many of each size to make in a day, in order to maximise its profit. As part of the process the lamps need to be sanded, painted, dried and polished. A single machine carries out these tasks and is available 24 hours per day. A small lamp requires one hour on this machine, a medium lamp 2 hours and a large lamp 4 hours. Let \(x =\) number of small lamps made per day, $$\begin{aligned} & y = \text { number of medium lamps made per day, }
& z = \text { number of large lamps made per day, } \end{aligned}$$ where \(x \geq 0 , y \geq 0\) and \(z \geq 0\).

1. Write the information about this machine as a constraint.
2. 1. Re-write your constraint from part (a) using a slack variable \(s\).
   2. Explain what \(s\) means in practical terms. Another constraint and the objective function give the following Simplex tableau. The profit \(P\) is stated in euros.

      Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	Value
      \(r\)	3	5	6	1	0	50
      \(s\)	1	2	4	0	1	24
      \(P\)	- 1	- 3	- 4	0	0	0

3. Write down the profit on each small lamp.
4. Use the Simplex algorithm to solve this linear programming problem.
5. Explain why the solution to part (d) is not practical.
6. Find a practical solution which gives a profit of 30 euros. Verify that it is feasible.

1. \begin{figure}[h] \end{figure} Figure 1 shows a directed, capacitated network where the number on each arc is its capacity. A possible flow is shown from \(S\) to \(T\) and the value in brackets on each arc is the flow in that arc.

1. Find the values of \(x , y\) and \(z\).
2. Find, by inspection, the maximal flow from \(S\) to \(T\) and verify that it is maximal.
   (2)

1. There are 16 competitors in a table-tennis competition, 5 of which come from Racknor Comprehensive School. Prizes are awarded to the competitors finishing in each of first, second and third place.

Assuming that all the competitors have an equal chance of success, find the probability that the students from Racknor Comprehensive

1. win no prizes,
2. win the \(1 ^ { \text {st } }\) and \(3 ^ { \text {rd } }\) place prizes but not the \(2 ^ { \text {nd } }\) place prize,
3. win exactly one of the prizes.

7. With respect to a fixed origin \(O\), the lines \(l _ { 1 }\) and \(l _ { 2 }\) are given by the equations $$\begin{array} { l l } l _ { 1 } : & \mathbf { r } = ( - 9 \mathbf { i } + 10 \mathbf { k } ) + \lambda ( 2 \mathbf { i } + \mathbf { j } - \mathbf { k } )
l _ { 2 } : & \mathbf { r } = ( 3 \mathbf { i } + \mathbf { j } + 17 \mathbf { k } ) + \mu ( 3 \mathbf { i } - \mathbf { j } + 5 \mathbf { k } ) \end{array}$$ where \(\lambda\) and \(\mu\) are scalar parameters.

1. Show that \(l _ { 1 }\) and \(l _ { 2 }\) meet and find the position vector of their point of intersection.
2. Show that \(l _ { 1 }\) and \(l _ { 2 }\) are perpendicular to each other. The point \(A\) has position vector \(5 \mathbf { i } + 7 \mathbf { j } + 3 \mathbf { k }\).
3. Show that \(A\) lies on \(l _ { 1 }\).
   [0pt] [BLANK PAGE]

9. The continuous random variable \(X\) has a uniform distribution on the interval \([ - \pi , \pi ]\).
The random variable \(Y\) is defined by \(Y = \sin X\). Determine the cumulative distribution function of \(Y\). END OF TEST

1

1. (a) Show that the number of arrangements of 25 distinct objects is an integer multiple of \(5 ^ { 6 }\).
   (b) Explain how this shows that the number of arrangements of 25 distinct objects is a whole number of millions.
2. (a) Calculate the values of
   • INT(720 \(\div 25\) )
   • INT(720 \(\div 125\) ).
     (b) Deduce the largest power of 10 that is a factor of 720!
   • Use the inclusion-exclusion principle to find the number of integers from 1 to 720 that are not divisible by either 2 or 5 .