Hey there! Sign in to join this conversationNew here? Join for free

Mathematical Proof Problem! Oxbridge interview, Watch

    • PS Helper
    • Study Helper
    Offline

    13
    ReputationRep:
    (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.
    • Thread Starter
    Offline

    2
    ReputationRep:
    (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.
    Offline

    16
    ReputationRep:
    (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
    • Political Ambassador
    Online

    21
    ReputationRep:
    (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.
 
 
 
  • 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
    What newspaper do you read/prefer?
    Useful resources

    Make your revision easier

    Maths

    Maths Forum posting guidelines

    Not sure where to post? Read the updated guidelines here

    Equations

    How to use LaTex

    Writing equations the easy way

    Student revising

    Study habits of A* students

    Top tips from students who have already aced their exams

    Study Planner

    Create your own Study Planner

    Never miss a deadline again

    Polling station sign

    Thinking about a maths degree?

    Chat with other maths applicants

    Can you help? Study help unanswered threads

    Groups associated with this forum:

    View associated groups
  • 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

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