Mathematical Proof Problem! Oxbridge interview,

Yes that makes perfect sense. It's just why the number of subsets = 2^n.

The induction proof makes perfect sense, namely that assume k elements {1,2...k} has 2^k subsets, so if we introduce another element, giving us k+1 elements, we have all the subsets from before and each subset with the k+1th element as well, hence 2 * 2^k = 2^k+1.

The proof which I am struggling to get my head around is that for every element we can either put it in the subset or not, hence 2^n different ways of choosing subsets.

But the way it is worded is that x_1 can either be in the subset or not, but all elements end up in a subset, hence I don't see where this comes from? As if we applied this rule to every subset we make, then it seems to me the total would be greater than 2^n; I am obviously overlooking a small, trivial detail.

I'll use spoilers to let you consider the question before looking at the solution. You should also get given some guidance with questions, after all, they don't expect you to know everything already, they want you to have to think.

So, in a practice interview I was asked something along the lines of "How many trailing, non-decimal, zeros are there are on 100!?"



After going through this it was followed up by "How many trailing, non-decimal, zeroes in 1000! ?"

Thank you for the insight, however, I had already came across a question like this the other day, hence I didn't have to 'think' much.

May I ask whether you applied to Oxford/Cambridge and which questions they asked you in your real interview?

Thanks.

Thank you for the insight, however, I had already came across a question like this the other day, hence I didn't have to 'think' much.

May I ask whether you applied to Oxford/Cambridge and which questions they asked you in your real interview?

Thanks.