Sample interview dialogue
The sample interview below is intended to show something of the kind of mathematical dialogue we hope to have with candidates who apply to read Computer Science. Some tutors hand out a sheet of problems in advance, and others introduce a problem at the start of the interview. In this case, our candidate B has spent a few minutes thinking about the following problem before the interview:
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 blocks of only one colour. Show that it is possible to do it so that each box contains at most two different colours.
Although this dialogue shows what happens in a Computer Science interview, you will notice that there is apparently no computing content at all in it. This is quite usual: we accept and encourage applications to read Computer Science from candidates who have little or no experience of programming computers.
A: We asked you to think about the problem called tidy boxes. Have you made any progress with it?
B: I haven't got very far: perhaps you could begin by putting each colour in its own box. Some colours would have less than ten bricks, so all of that colour would go in one box. But some colours would have more than ten bricks, and we'd have to find a way to use the extra bricks to fill up the gaps in the other boxes. I can't see a way to do that.
A: OK. Let's think about an easier problem to start with: if we had only one box and ten bricks, all of the same colour, could we solve the problem?
B: Yes, of course: you just put all ten bricks in the one box, and it then contains only one colour, so you don't even need the freedom to have two colours in a box.
A: Good. Now suppose you have two boxes and 20 bricks in two different colours. Could you solve the problem then?
B: It's still easy: you can just put the 20 bricks into the two boxes any way you like. Then each box might have a mixture of the two colours, but there are still only two of them.
A: So these small versions of the problem are easy. Let's go back to thinking about the original problem, with ten boxes and ten colours of brick. I wonder if, instead of starting to fill all the boxes as you suggested, we could begin by filling just the first box. Can we find a colour with few enough bricks that we can put all of them in the first box?
B: You mean a colour with ten bricks or less. We can be sure such a colour exists, because the average number of bricks of each colour is ten. If all colours had more than ten bricks, then they would all be above average, and that can't happen.
A: Right. So we choose a colour that's below average (or equal to the average) and we put all of those bricks into the first box. Now there may be a gap to fill, and I'd like to find another colour with enough bricks to fill the gap. Can I be sure of doing that?
B: What you could do is to choose a colour with more than the average number of bricks. That colour ought to be enough: the gap to fill must be nine bricks or fewer, and the average is ten.
A: Excellent. So we've filled up a box by using all of one colour and some of another colour. Let's suppose we put a lid on that box and push it to one side. What do we have left?
B: There are nine boxes left, and ninety bricks of nine different colours.
A: So what should our next step be?
B: We can use the same approach as before, filling a second box by using all of a below-average colour and some of an above-average colour. By carrying on like this, we can eliminate the colours one at a time.
A: That's very good. How does the process end?
B: When we get down to one box, we will have only one colour left, and that can all be put in the last box, as we said before.
A: So we've shown that the problem can always be solved, and you can put the bricks in the boxes with at most two colours in each box. Now I want to think about a slightly harder problem: suppose we have ten boxes but there are 11 different colours of brick. Can we still solve the problem with only two colours in each box?
B: Well, I suppose we could start the same way as before: find a small colour and put all of it in the first box.
A: OK: since the average number of each colour is now 100/11 and that's smaller than 10, we can still be sure of finding a colour with 10 bricks or less. But I'm worried about the next part, where we need to find a colour with enough bricks to fill up the gap. Can you work out what will happen?
B: The biggest gap we might have is nine, and the average number of each colour is 100/11 = 9 1/11, so we're still all right: at least one colour must have 10 bricks or more, since if they all had nine or less, then they'd all be less than average.
A: So that still works: we can fill up the first box with all of one colour and some of another, then put it to one side. How does the process continue?
B: We carry on filling boxes and eliminating one colour at a time, until we get down to one box and two colours. And we can fill the last box with the two colours that are left to finish off the problem.
A: I see. I'm still a bit worried about finding a colour with enough to fill up the gap. Say we had three boxes and four colours: then the average of each colour would be 7½, wouldn't it? And we couldn't be sure that any colour had as many as nine bricks.
B: Yes, that is a problem.
A: Let's see if we can use a bit of algebra to analyse the situation. Let's suppose we have n boxes and n+1 colours left, and say we find a colour that has x bricks, with x ≤ 10 so that that colour all fits in the next box. What is the gap that we have to fill?
B: That's obvious: it's 10 - x.
A: Right. And how many bricks do we have left, after putting the x bricks in the next box?
B: Well, we had 10n bricks altogether, so now we have 10n - x.
A: So what is the average number of bricks of each colour that we have left?
B: It's going to be (10n - x)/n, which is equal to 10 - x/n.
A: Is that smaller or larger than 10 - x?
B: [Thinks for a moment] Provided n ≥ 1, we have that x/n ≤ x, so 10 - x/n ≥ 10 - x.
A: So what does that mean?
B: It means we can find a colour with enough bricks to fill the gap, because the average number of each colour remaining is at least as large as the gap.
A: Excellent: so we can solve the problem with ten colours, and we can still solve it with eleven colours. What do you think I want to ask you next?
B: Can we do it with twelve colours?
A: Well?
B: We could begin in the same way as before, eliminating colours one at a time. I'm not sure if the calculation we did would still show that we can fill the gap, though.
A: Even if we could always fill the gap, what would we be left with when we got down to one box?
B: Well, you'd have eliminated nine of the colours, one at a time, so you'd be left with one box and three colours. Oh, I see, you can't do it, because you're going to have three colours left at the end, and you can't put them all into the last box. So it can't be done.
A: So what you've shown is that we can't solve the problem for twelve colours by using the method we've been talking about, eliminating the colours one at a time. That doesn't mean, though, that there isn't some other method we could use to find a solution. How can we be sure that the problem can't be solved?
B: We can't: sometimes it's possible to fit up to twenty colours in: if you had twenty colours, but they could be arranged in pairs that added up to ten, then that would work.
A: So what's the most we can hope to say about twelve colours?
B: We could look for an example with twelve colours that definitely couldn't be solved. Then we could say that sometimes you can do it with twelve colours and sometimes you can't.
A: OK. Think about this: we have one brick of each of eleven colours, and the rest of the bricks are another colour, say white. Can that problem be solved? Where would the eleven coloured bricks have to go?
B: You could only have one of them in each box, and the rest of the box would have to be filled up with white. If you tried to have two in the same box, then there'd be a gap of eight spaces to fill up, and you'd have to use another colour for that, violating the rules.
A: But if you have eleven coloured bricks, you can't put them in ten boxes without having at least two in one of the boxes. What does that tell us?
B: That you can't solve the problem for this combination of twelve colours.
A: So what can we conclude?
B: With ten or eleven colours, you can always solve the problem, using the method we talked about. But for twelve colours, sometimes the problem can't be solved at all.