Cambridge Computer Science

Tidy boxes. You are given 10 boxes, each large enough to contain exactly 10 wooden building blocks, and a total of 100 blocks in 10 different colours. There may not be the same number in each colour, so you may not be able to pack the blocks into the boxes in such a way that each box contains only one colour of block. Show that it is possible to do it so that each box contains at most two different colours.

Searching for the maximum. The real-valued function f(x), defined for 0 ≤ x ≤ 1, has a single maximum at x = m. If 0 ≤ u < v ≤ m then f(u) < f(v), and if m ≤ u < v ≤ 1 then f(u) > f(v). You are told nothing else about f, but you may ask for the value of f(x) for any values of x you choose. How would you find the approximate value of m? How accurately could you find m if you could choose only 10 values of x for which to evaluate f(x)?

Death by chocolate. You are locked in a room with your worst enemy. On a table in the centre of the room is a bar of chocolate, divided into squares in the usual way. One square of the chocolate is painted with a bright green paint that contains a deadly poison. You and your enemy take it in turns to break off one or more squares from the remaining chocolate (along a straight line) and eat them. Whoever is left with the green square must eat it and die in agony. You may look at the bar of chocolate and then decide whether to go first or second. Describe your strategy.

Monkey beans. An urn contains 23 white beans and 34 black beans. A monkey takes out two beans; if they are the same, he puts a black bean into the urn, and if they are different, he puts in a white bean from a large heap he has next to him. The monkey repeats this procedure until there is only one bean left. What colour is it?

Lily-pad lunacy. Eleven lily pads are numbered from 0 to 10. A frog starts on pad 0 and wants to get to pad 10. At each jump, the frog can move forward by one or two pads, so there are many ways it can get to pad 10. For example, it can make 10 jumps of one pad, 1111111111, or five jumps of two pads, 22222, or go 221212 or 221122, and so on. We'll call each of these ways different, even if the frog takes the same jumps in a different order. How many different ways are there of getting from 0 to 10?