Hey there! Sign in to join this conversationNew here? Join for free
    • Thread Starter
    Offline

    9
    ReputationRep:
    Find the number of k-digit numbers (k<=10) that contain no two consecutive 0's.

    Yet again I'm stuggling to make a start. All hints are welcome.

    Question edited.
    Offline

    16
    ReputationRep:
    See if you can find the number of 7-letter strings (of digits) with no two consecutive 0s, and then get rid of those starting with zero.
    Offline

    16
    ReputationRep:
    ok. so you know that the first digit of your number is 1-9

    so you have 9 options for the first digit. now consider cases where you have

    0-0-0-
    0-0---
    0-----
    ------
    separately.
    Offline

    15
    ReputationRep:
    i can only think of a long winded way of doing this

    consider all layouts of the integer which satisfy the question

    abcdefg <-7 digit integer

    abcdef0
    abdce0g
    abcd0fg
    ...
    a0cdefg

    abcd0f0
    abd0ef0
    ....

    hopefully its obvious enough where to go from here. just will take ages and is pretty inefficient. havnt had to do random problems like this in ages
    Offline

    6
    ReputationRep:
    If 7-digit no. in your solution set has 1 zero, this can be in 1 of 6 places (not at front I assume)

    if it has 2 zeros, then how many places can you have these zeros?

    3 zeros?

    4 zeros?

    Then consider if a number has n zeros, it has 7-n of the digits 1-9
    • Thread Starter
    Offline

    9
    ReputationRep:
    Sorry, I posted the question incorrectly. I'm trying to find the number of k-digit numbers (k<=10) that contain no two consecutive 0's and then use this to evaluate k=7.

    Does this change the method?
    Offline

    16
    ReputationRep:
    (Original post by 0-))
    Sorry, I posted the question incorrectly. I'm trying to find the number of k-digit numbers (k<=10) that contain no two consecutive 0's and then use this to evaluate k=7.

    Does this change the method?
    inclusion exclusion?
    • Thread Starter
    Offline

    9
    ReputationRep:
    (Original post by Totally Tom)
    inclusion exclusion?
    How would I use that?

    EDIT: I was given a hint which I've just remembered: Let f(k) be the number of k digit numbers with no two consecutive zeros. Express f(k) in terms of f(k-1) and f(k-2).
    Offline

    16
    ReputationRep:
    (Original post by 0-))
    How would I use that?

    EDIT: I was given a hint which I've just remembered: Let f(k) be the number of k digit numbers with no two consecutive zeros. Express f(k) in terms of f(k-1) and f(k-2).
    If you haven't covered it you're probably supposed to use the intuitive approach shown earlier in the thread.
    Offline

    17
    ReputationRep:
    What does the hint suggest to you?
    • Thread Starter
    Offline

    9
    ReputationRep:
    (Original post by DFranklin)
    What does the hint suggest to you?
    It suggests that I find out how adding an extra digit changes the number of possibilities.

    For k=4, the possible double 0's are a00b or ab00. Then you can add digits on either side of those strings to give the possible doubles for k=5. This doesn't include triples...

    I've been looking into things like the above but haven't got anywhere. Am I on the right track? I'm sure there's a nice way to see this problem but it hasn't come to me yet.
    Offline

    2
    ReputationRep:
    If you have A[k-digits], how many difference values A can always take. Is their a value it can't take always take and can you use something to do with AB[(k-1)-digits]?

    once you have exhausted all possibilities, you add the number of combinations for each of these possibilities, giving an equation of the form f(k+1)=mf(k)+nf(k-1)
    • Thread Starter
    Offline

    9
    ReputationRep:
    (Original post by jj193)
    If you have A[k-digits], how many difference values A can always take. Is their a value it can't take always take and can you use something to do with AB[(k-1)-digits]?

    once you have exhausted all possibilities, you add the number of combinations for each of these possibilities, giving an equation of the form f(k+1)=mf(k)+nf(k-1)
    I don't really follow your notation. Can you explain what A[k-digits] and AB[(k-1)-digits] mean?
    • Thread Starter
    Offline

    9
    ReputationRep:
    I wrote it out for k=3,4,5,6 (possibly wrongly)

    k=3: 900-(9)
    k=4: 9000-(9+2x9^2)
    k=5: 90000-(9+2x9^2)-(2x10x9^2+9^3)
    k=6: 900000-(9+2x9^2)-(2x10x9^2+9^3)-(2x10^2x9^2+2x10x9^3)

    I can't see a connection between the kth term and the two before it or develop an expression for the extra term added.
    Offline

    17
    ReputationRep:
    It's difficult to give hints which don't give the game away.

    You're looking to find f(k+1) in terms of f(k) and f(k-1).

    This should have you thinking about trying to form a sentence of the form:

    A k+1 digit number with no repeated zeros is formed by either doing ___ and following with a k digit number with no repeated zeroes, or by doing ___ and following with a k-1 digit number with no repeated zeroes.

    (You need to fill in the blanks).

    When you do this, you need to be able to show that

    (a) Count the number of ways of doing ___ or ___ (and following it with k-digit or k-1 digit number).
    (b) Every k+1 digit number (with no rep zeroes) can be formed in this way.
    (c) You can't get the same k+1 digit number in two different ways (so you're not double counting).
    • Thread Starter
    Offline

    9
    ReputationRep:
    The two blanks are 1-digit number and 2-digit number?

    This would give the recurrance f(k+1)=9f(k)+90f(k-1)

    But this doesn't work for k=2. I would've thought a more likely recurrance would be f(k+1)=9(f(k)+f(k-1)) but I don't know how to show this.
    Offline

    17
    ReputationRep:
    No, those aren't the blanks.

    A question you might want to answer: what k+1 digit numbers with no repeated zeroes *can't* be formed by writing a 1 digit number and following it with a k digit number with no repeated zeroes?
    • Thread Starter
    Offline

    9
    ReputationRep:
    (Original post by DFranklin)
    No, those aren't the blanks.

    A question you might want to answer: what k+1 digit numbers with no repeated zeroes *can't* be formed by writing a 1 digit number and following it with a k digit number with no repeated zeroes?
    Of course! I'm counting numbers twice.
    So the two blanks are '1 digit number' and 'two digit number ending in 0'. This gives the recursion which I mentioned in my last post.

    Now I'll have a go at showing (b) and (c).
 
 
 
  • 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
    Has a teacher ever helped you cheat?
    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

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