# 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 10*n* bricks altogether, so now we have 10*n*
- *x*.

**A:** So what is the average number of bricks of each colour that we have
left?

**B:** It's going to be (10*n* - *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.