You are Here: Home >< Maths

# Mathematical Proof Problem! Oxbridge interview, Watch

1. (Original post by DomStaff)
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.
All elements do end up in a subset, certainly - but you're overcounting here. You're adding {1, 2} twice, for instance - once for 1 and once for 2. (The Inclusion-Exclusion principle tells you how to do this exactly - it's closely related.)

The "reason" it's true is that I can specify any subset by the following method: "1 is in; 2 is not in; 3 is in; … n is in". This can be represented as a binary number (in this case, 101…1) with 1 for "in" and 0 for "not in". What's the number of binary numbers of length n? Obviously 2^n.

The inductive one is fine, though.
2. (Original post by Jammy Duel)
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!?"

Spoiler:
Show
With a bit of thinking, and some logic which was along the right lines but incorrect (mainly from not solving it generally enough) I gave an incorrect answer, and was prompted to consider where the trailing zeros come from. Of course, 10=2x5 so to get a trailing zero you require 2x5 of some form in there, there are more 2s than 5s so you can disregard those and just look at the multiples of 5.

So, there are 20 multiples of 5 between 1 and 100 inclusive, so there are 20 trailng zeroes there, 4 of these are also multiples of 25, so there are another 4 trailing zeroes from that, so the answer is 24. Upon giving this justified answer I was told it's correct, however I should, strictly, conclude this explanation by saying that there are no values in the range that are multiples of 125 (being 3​).

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

Spoiler:
Show
So, this is easy enough to solve, given the first part, but was mainly there to see if I had paid attention the first time. So, obviously there is 200 multiples of 5, 40 of 25, 8 of 125 and 1 of 625, so 149 trailing zeroes. However, I forgot to mention that there are no numbers in the range that are multiples of 55. The person doing it would count against me that I was told that I should include that final part, and so soon after failed to do so.
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.
3. (Original post by DomStaff)
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.
To be fair on everyone, typically recent interview questions aren't shared publicly. This is a controversial policy (because if you went to an elite private school, they'd give you plenty of questions from past students). However I agree it's the right thing to do, because it just further creates an imbalance of people who know specific questions and those who don't.

The good news is I can give you a massive source of questions at the appropriate difficulty; STEP I questions have been adapted for interview questions. It might be slightly overkill to prepare for interview with STEP I, but you'll have to take STEP to get in eventually, so might as well get used to the papers now
4. (Original post by DomStaff)
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.

Posted from TSR Mobile

Not everybody will have come across it before

In the end, I did not apply, didn't put enough effort into AS, however the practice started pretty early at my school, in the spring term of AS IIRC.

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: July 2, 2014
Today on TSR

### Cambridge interview invitations

Has yours come through yet?

### Official Oxford interview invite list

Discussions on TSR

• Latest
• ## See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams

## Groups associated with this forum:

View associated groups
Discussions on TSR

• Latest
• ## See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.