You are Here: Home >< Maths

# Find the number of integers... watch

1. 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.
2. 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.
3. 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.
4. 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
5. 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
6. 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?
7. (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?
8. (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).
9. (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.
10. What does the hint suggest to you?
11. (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.
12. 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)
13. (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?
14. 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.
15. 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).
16. 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.
17. 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?
18. (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).

### Related university courses

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: February 14, 2010
Today on TSR

### Results day under a month away

How are you feeling?

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