Oxford, Imperial and Warwick challenge prospective mathematics and computer science students with a rendition of the following problem to test their mathematical understanding rather than how much they know about mathematics. The following does really get the cogs working even though the concept is quite simple.
(Note the problem was rephrased slightly to make it more suitable for a The Guardian News to publish. Thanks to James Munro at Oxford’s Mathematical Institute.)
You need to pack several items into your shopping bag without squashing anything. The items are to be placed one on top of the other. Each item has a weight and a strength, defined as the maximum weight that can be placed above that item without it being squashed. A packing order is safe if no item in the bag is squashed, that is, if, for each item, that item’s strength is at least the combined weight of what’s placed above that item. For example, here are three items and a packing order:
This packing is not safe. The bread is squashed because the weight above it, 5, is greater than its strength, 4. Swapping the apples and the bread, however, gives a safe packing.
i) Which of the other four orderings of apples, bread and carrots are safe or unsafe?
(ii) Consider packing items in weight order, with the heaviest at the bottom. Show by giving an example – that is, invent some items and give them weights and strengths of your choosing – that this strategy might not produce a safe packing order, even if one exists.
(iii) Consider packing items in strength order, with the strongest at the bottom. Show by giving an example – that is, invent some items and give them weights and strengths of your choosing – that this strategy might not produce a safe packing order, even if one exists.
(iv) Consider we have a safe packing order in our bag. Assume that item j sits directly on item i. Suppose also that:
(weight of j) – (strength of i) ≥ (weight of i) – (strength of 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. (Listing all possible orderings is not possible.)
The majority of Oxford candidates have been known to score full marks on parts i-iii, however, successful applicants, on average, did not score full marks on parts -iv & v so do not be disheartened if you lacked a full answer. Nevertheless, I can assure all candidates will never pack their weekly shop the same after, who knew there was a deep science to bringing the groceries home.