牛津劍橋如何面試？

這段時間是英國G5院校發面試offer的高峰期，有同學收到面試通知了嗎？收到的同學心情一定很激動吧，離正式offer只差一個面試了！

但G5面試不是走過場。需要精心準備。

到底在面試中，牛劍老師和面試者之間發生了哪些“對話”？牛劍到底想要什么樣的學生？為何有人成績很好，卻得不到面試老師的青睞？

在牛津大學的官網上，有一份該校計算機科學專業本科的面試過程實錄，雖然比較長，但是值得仔細閱讀。感受一下牛劍老師引導學生解題的思路，題目本身不難理解，只要學過數學應該都能看懂。在面試實錄的最后，我們總結了牛劍面試的一些關鍵點。

在這場面試中，牛津的面試老師首先向面試學生提出了下面這道題：

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

收納盒問題。
如果你有10個收納盒，每個盒子能裝10塊積木，總共有10種顏色的積木100塊。由于每種顏色的積木數目不一定相同，因此當你把積木全部裝進盒子里時，你可能沒法保證每個盒子只裝同一種顏色的積木。請證明我們能夠找到一種把積木全部裝進盒子里的方式，使得每個盒子最多只裝兩種不同顏色的積木。

隨后，面試老師和學生發生了如下對話：
A 代表面試老師
B 代表面試學生

A:? We asked you to think about the problem called tidy boxes. Have you made any progress with it?
A：剛才我們請你思考的這個收納盒問題，你有什么進展嗎？

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 dothat.
B：我目前沒有特別大的進展：也許你可以先把每種顏色的積木放進每個顏色相對應的盒子里。有些顏色可能有不到10塊積木，所以這些顏色中，所有同色的積木都能夠放進它們對應的盒子里。但是有些顏色有10個以上的積木，那樣我們就得想辦法讓多出來的那些積木填補到有空位的那些盒子里。我想不出來怎么做。

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?
A：好。我們先想一個簡單點的問題：如果我們只有一個盒子，10塊同色積木，我們能解答這道題嗎？

B:? Yes, of course: you just put allten 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.
B：當然可以：你只需要把這十塊積木都放進一個盒子里。這個盒子只裝一種顏色的積木，我們甚至都不需要把條件放寬到一個盒子裝兩種顏色。
A:? Good. Now suppose you have two boxes and 20 bricks in two different colours. Could you solve the problem then?
A：很好?，F在假設你有兩個盒子，2種顏色的積木20塊。你能解答這道題嗎？

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.
B：依然很簡單：你可以把這20塊積木隨便放進這兩個盒子里，這樣每個盒子里就可能會混合了兩種顏色的積木，但是每個盒子里也只有兩個顏色。

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?
A：所以這個問題的這幾個簡易版本很容易證明。那我們現在來思考一下原先的問題：十個盒子，十種顏色的積木。我在想，如果我們先試著裝第一個盒子，而不是把所有盒子都裝上積木，那么我們能否找到一種顏色，這種顏色的積木數目足夠少，使得它們都能夠被放進第一個盒子里呢？

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.
B：你是說找一個積木數目少于或者等于10塊的顏色。我們可以肯定這種顏色存在，因為每種顏色平均有10塊積木。如果所有顏色的積木數目都超過10塊，那么每種顏色的積木平均數就會大于10，這是不可能的。

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?
A：對。所以我們要選一種顏色，使得這種顏色的積木數目小于（或者等于）每種顏色的積木平均數，然后我們把所有這個顏色的積木都放進第一個盒子里。現在這個盒子里就可能會有空位，然后我想找另外一種顏色，使得這種顏色的積木數目足夠填滿第一個盒子里的空位。我能確定做到這點嗎？

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.
B：你可以找一個顏色，使得這種顏色的積木數目多于積木平均數。這個顏色的積木肯定滿足條件，因為如果想要第一個盒子里的空位，需要九塊或更少的積木，而每種顏色的積木的平均數是10塊。

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?
A：非常好。所以我們用了一種顏色的全部積木和另一種顏色的部分積木，裝滿了一個盒子。假設我們把這個盒子蓋上蓋子，推到一邊，那么現在我們還剩下什么？

B:? There are nine boxes left, andninety bricks of nine different colours.
B：現在剩下9個盒子，以及9種顏色的積木塊90個。

A:? So what should our next step be?
A：所以我們的下一步是什么？

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.
B：我們可以用和剛才相同的方法來裝第二個盒子：選一種少于平均數目的顏色，把所有積木裝進去，再選一種多于平均數目的顏色，用其中一部分把剩下的空位填滿。我們只要重復這一步驟，就可以每步消除一個顏色了。

A:? That's very good. How does the process end?
A：非常好。那么這個過程會怎么結束呢？

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.
B：當我們只剩下一個盒子時，我們也只剩下一種顏色的積木，然后我們就可以把這些積木全部裝進最后一個盒子里了，這就和之前的簡易版本問題是一樣的。

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?
A：所以我們已經證明了這個題目，我們可以找到方式把所有盒子裝滿，使得每個盒子里最多有兩種顏色?，F在我想思考一個再難點的問題：假設我們有10個盒子，11種顏色的積木。我們還能解決這個問題嗎？

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.
B：嗯，我覺得可以用剛才的方式來試一下：找一種積木數目足夠少的顏色，把他們都放進第一個盒子里。

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?
A：好。既然每種顏色的平均數現在變成100/11，然后這比10小，所以我們肯定能找到一種積木數目小于或等于10的顏色。不過我有點擔心下一步，就是我們要找一種顏色的積木，使其足夠填滿第一個盒子里的空位。你能算一下這一步嗎？

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.
B：第一個盒子里的空位最多能放下九個球，而每種顏色的積木平均數是100/11，也就是9 1/11，所以我們還是可以做到的：至少有一種顏色的積木數目是10或者以上，因為如果所有積木的數目都小于或等于9，那所有顏色的積木數目就都小于平均值了。

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 oneside. How does the process continue?
A：所以這還是可以做到的：我們可以用一種顏色的全部積木和另一種顏色的部分積木，裝滿第一個盒子。假設我們把這個盒子蓋上蓋子，推到一邊，那么現在我們要怎么做？

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 offthe problem.
B：我們繼續把每個盒子都填滿，一次消除一種顏色，直到我們只剩下最后一個盒子和最后兩種顏色的積木。然后我們把這兩種顏色的積木都裝進最后這個盒子里就可以了。

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.
A：我懂了。但我還是在擔心我們能不能找到一個顏色，其積木數目足夠填滿盒子里的空位。假設我們有3個盒子，4種顏色的積木，那么每種顏色的積木平均數就變成7?,對不對？那我們就不能確定有沒有哪種顏色可以有9個積木那么多了。

B:? Yes, that is a problem.
B：是，這確實是個問題。

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. Whatis the gap that we have to fill?
A：我們來看看我們能不能用一點代數來分析一下這個情況，假設我們現在剩下n個盒子，n+1種顏色的積木，然后假如說我們找一種顏色，這種顏色有x塊積木，而x ≤ 10?，這樣這種顏色的所有積木都能放進下一個盒子里。我們需要幾塊積木來填補下一個盒子的空位呢？

B:? That's obvious: it's 10 -?x.
B：顯而易見，需要（10 – x）塊。

A:? Right. And how many bricks do we have left, after putting the?x?bricks in the next box?
A：對。那么當我們把x塊積木放進下一個盒子里后，還剩下多少塊積木了呢？

B:? Well, we had 10n?bricks altogether, so now we have 10n?-?x.
B：嗯，我們原本一共有10n塊積木，所以現在我們有（10n– x）塊。

A:? So what is the average number of bricks of each colour that we have left?
A：所以現在我們手上每種顏色的積木平均數是多少？

B:? It's going to be(10n?-?x)/n, which is equal to 10 -?x/n.
B：是(10n - x)/n，也就是（10- x/n）塊。

A:? Is that smaller or larger than 10-?x?
A：這個數比10 – x大還是小呢？

B:? [Thinks for a moment]?Provided?n?≥ 1, we have that?x/n?≤?x, so 10-?x/n?≥ 10 -?x.
B：（想了一會）因為n ≥ 1，那么x/n ≤ x，所以 10- x/n ≥ 10 – x。

A:? So what does that mean?
A：這意味著什么呢？

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.
B：這意味著我們能找到一種顏色，使其有足夠數目的積木塊填滿空位，因為剩下每種顏色的積木數都至少剛好夠填滿盒子里的空位。

A:? Excellent: so we can solve the problem with ten colours, and we can still solve it with eleven colours. Whatdo you think I want to ask you next?
A：非常好。所以當我們有10種顏色時，這個問題可以有解，當我們有11種顏色的時候也可以有解。那么你覺得我接下來要問你什么問題？

B:? Can we do it with twelve colours?
B：當我們有12種顏色的時候，這個問題有解嗎？

A:? Well?
A：你怎么想？

B:? We could begin in the same way asbefore, eliminating colours one at a time. I'm not sure if the calculation wedid would still show that we can fill the gap, though.
B：我們可以跟剛才采取同樣的方法，一次消除一種顏色。不過我不太確定剛才的計算能夠證明我們可以填滿盒子里的空位。

A:? Even if we could always fill the gap, what would we be left with when we got down to one box?
A：即使我們每次都能夠填滿盒子里的空位，當我們只剩下最后一個盒子時，會出現什么問題？

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.
B：嗯，那樣的話你就已經消除了九種顏色，一次一個。所以你就會剩下一個盒子和3種顏色的積木。哦，我明白了，這樣做不行，因為你最后剩下了3種顏色的積木，但是你不能把它們都放進最后一個盒子里。所以這樣是不行的。

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?
A：所以你已經證明了，如果只用我們之前的方法，一次消除一種顏色，那么當我們有12種顏色時這個問題無解。但是這不代表這個問題就不能夠用其它方法解決。我們怎么能確定這個問題無論用什么方法都無解呢？

B:? We can't: sometimes it's possibleto 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.
B：我們做不到：因為有時候我們甚至可以解決20種顏色的問題：如果你有20種顏色的積木，而且這20種顏色可以被兩兩配對，使得每一對顏色的積木總數都是10，這個問題就有解。

A:? So what's the most we can hope tosay about twelve colours?
A：所以對于12種顏色的問題，我們最多能證明到什么程度？

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.
B：我們可以找一種情況，使得這12種顏色的積木一定無法按照題目要求裝進盒子里，然后我們可以說當我們有12種顏色時有時候無解，有時候有解。

A:? OK. Think about this: we have onebrick 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?
A：好，思考一下這個問題：這12種顏色的積木里，其中11種的積木我們每種顏色有1塊，然后剩下的所有積木都是第12種顏色的，假設說，白色。這個問題有解嗎？那11塊不同顏色的積木要怎么裝盒？

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.
B：這11種顏色的積木，你必須得在每個盒子里都只放1塊，那么盒子里剩下的空位就要全裝滿白色積木。如果你試圖在每個盒子里放2塊的話，那么你還得再找8塊白色積木來填滿盒子里的空位，這樣的話每個盒子里就有三種顏色的積木了，不滿足條件。

A:? But if you have eleven colouredbricks, you can't put them in ten boxes without having at least two in one ofthe boxes. What does that tell us?
A：但是你有11塊不同顏色的積木，如果你要把它們全都放進10個盒子里，就必須得有一個盒子里至少放有2塊。那么這說明什么？

B:? That you can't solve the problemfor this combination of twelve colours.
B：那么當我們有12種顏色的積木，并且它們是這種顏色組合時，這個問題是無解的。

A:? So what can we conclude?
A：那么我們可以得到什么結論？

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.
B：當我們有10種或11種顏色時，運用我們剛才討論過的方法，這個問題一定有解。但是當我們有12種顏色時，這個問題有時是無解的。

看完這份面試實錄，你有那些感受呢？先說說我的體會：

1. 雖然這是Computer Science專業的面試，題目卻沒有直接涉及編程，而是一道考察學生底層算法能力的數學題。
即使學生沒有編程經驗，也能作答。而事實上，在牛津大學計算機學院的官網上明確寫著，歡迎沒有編程經驗的學生報考。

2. 即使學生在剛開始沒有給出所謂的“完美答案”，面試老師還是會給予學生一些必要的引導，并根據學生的作答情況，不斷提出更深入的問題。
其實牛劍老師在剛開始就沒有期待學生能在短短幾分鐘的時間里給出“完美答案”。他們要看的，就是你的分析、解題過程。

3. 最重要的一點，通過這段實錄我們能真切的感受到，牛劍面試的目的：不是為了測試你已經知道了多少，而是要了解你如何思考。而這也正是傳統中式教育和歐美教育最大的不同。

面試是通往牛津offer的最后一站，然而很多小伙伴一路披荊斬棘卻最終敗給面試，實在是遺憾。