\section*{6. For APPLICANTS IN $\left\{ \begin{array} { l } \text { COMPUTER SCIENCE } \\ \text { MATHEMATICS \& COMPUTER SCIENCE } \\ \text { COMPUTER SCIENCE \& PHILOSOPHY } \end{array} \right\}$ ONLY.}
You need to pack several items into your shopping bag, without squashing any item. Suppose each item $i$ has a (positive) weight $w _ { i }$, and a strength $s _ { i }$ which is the maximum weight that can be placed above it without it being squashed. For the purposes of this question, suppose that the items will be arranged one on top of the other within your bag. We will say that a particular packing order is safe if no item is squashed, that is, for each item $i , s _ { i }$ is at least the sum of the $w _ { j }$ corresponding to items $j$ placed above item $i$. For example, suppose we have the following items, packed in the order given

\begin{center}
\begin{tabular}{ c | l | c c }
Ordering & Item & $w _ { i }$ & $s _ { i }$ \\
\hline
Top & Apples & 5 & 6 \\
Middle & Bread & 4 & 4 \\
Bottom & Carrots & 12 & 9 \\
\end{tabular}
\end{center}

This packing is not safe: the bread is squashed, since the weight above it (5) is greater than its strength (4). However, swapping the apples and the bread gives a safe packing.\\
(i) Which of the other four orderings of apples, bread, and carrots are safe or unsafe?\\
(ii) Consider the tactic of packing the items in weight order, with the heaviest at the bottom. Show by giving an example that this might not produce a safe packing order, even if a safe packing order exists.\\
(iii) Now consider the tactic of packing the items in strength order, with the strongest at the bottom. Again show by giving an example that this might not produce a safe packing order, even if one exists.\\
(iv) Suppose we have a safe packing order, with item $j$ directly on top of item $i$. Suppose further that

$$w _ { j } - s _ { i } \geqslant w _ { i } - s _ { j }$$

Show that if we swap items $i$ and $j$, we still have a safe packing order.\\
(v) Hence suggest a practical method of producing a safe packing order if one exists. Explain why your method works. (Listing all possible orderings is not practical.)