Problem Solving

How many 5-digit positive integers exist where no two consecutive digits are the same ?

9*9*8*7*6
9*9*8*8*8
10*9^^4
9^^5
9*8^^4

IMO D

ABCDE be the number

A can be selected in 9 ways [not 0 rest 1-9]
B can be selected in 9 ways [except the selceted digit for A rest all including 0]
C can be selected in 9 ways
D can be selected in 9 ways
E can be selected in 9 ways

Total 9*9*9*9*9 = 9^5

shovan85 wrote:IMO D

ABCDE be the number

A can be selected in 9 ways [not 0 rest 1-9]
B can be selected in 9 ways [except the selceted digit for A rest all including 0]
C can be selected in 9 ways
D can be selected in 9 ways
E can be selected in 9 ways

Total 9*9*9*9*9 = 9^5

I would definitely like to recommend you to write CAT(You have all the answers ) ,
I think you are 98+ percentile Guy.

Take it as a complement........

Good solution indeed, shovan. Clear and to-the-point.

Let us put some spice in the problem, shall we?

How many 5-digit positive integers exist in which there are exactly two consecutive digits that are the same ?

Regards,
Fabio.

Hint/Sugestion: [spoiler]there is the possibility of choosing the first two, then the second and third digits, etc... but there is a trick to "glue" two of the digits as if they were just one to apply shovan´s idea... think about it!)[/spoiler]

fskilnik wrote:Good solution indeed, shovan. Clear and to-the-point.

Hi FSKILNIK,

I have a concern about the actual problem. I could solve it by starting from A then B then C D E.
ABCDE be the number

A can be selected in 9 ways [not 0 rest 1-9]
B can be selected in 9 ways [except the selceted digit for A rest all including 0]
C can be selected in 9 ways
D can be selected in 9 ways
E can be selected in 9 ways

Total 9*9*9*9*9 = 9^5

But if I start from E (backwards) D C B A.... Its quite possible to solve but why the results do not match?
I mean now E can be selected in 10 ways right (0-9)

shovan85 wrote: Hi FSKILNIK,

I have a concern about the actual problem. I could solve it by starting from A then B then C D E.

But if I start from E (backwards) D C B A.... Its quite possible to solve but why the results do not match?
I mean now E can be selected in 10 ways right (0-9)

Good question, shovan85! Thank you for the opportunity you give me to try to clear that for you...

One of the "golden rules" of Combinatorics is "satisfy the restrictions first", perhaps because it is hard (sometimes impossible) to manage the difficulties if you let them "propagate"...

In this case, if you start with the first digit, the problem with 0 to be excluded from this (first) place is managed at first, what is according to the "golden rule", right?

If you start with the last digit, you see the problem: at the moment you have to choose how many possibilities you have for A given that you have already reasoned for E, D, C and B... you have a nightmare:

(1) If B was 0, then A will be not "naturally" (great) but...
(2) If B was not 0, then A CANNOT be equal to B NOR to zero...

You see, you would need to separate in 2 cases, because the Multiplicative Principle could not be applied as in the first way you chose to answer the problem!!

I hope I did clear it all for you. If not, please ask me about my explanation or about what you still didn´t get, ok?!

Best Regards and thank you for your trust!
Fabio.

fskilnik wrote: One of the "golden rules" of Combinatorics is "satisfy the restrictions first", perhaps because it is hard (sometimes impossible) to manage the difficulties if you let them "propagate"...

In this case, if you start with the first digit, the problem with 0 to be excluded from this (first) place is managed at first, what is according to the "golden rule", right?

So we have to restrict it first. I was thinking if I start from E to A

Will it be like 10*9*9*9*9 - 9*9*9*9? I was subtracting all possible 4 digit numbers when A becomes zero. If you see now we can have the answer equal to 9^5.

I know this discussion is out of context and in GMAT I ll not try to experiment. But what do you say for my above reasoning?
If its correct then I ll gain more confidence on this as I can understand the problem very well.

fskilnik wrote: How many 5-digit positive integers exist in which there are exactly two consecutive digits that are the same ?

ABCDE now AB has to be equal then BC then CD then DE.

AB can be selected in 9 ways (except zero) and C, D and E each can be selected in 9 ways = 9*9*9*9 = 9^4 ways
BC can be selected in 9 ways and A (except zero) D, and E each can be selected in 9 ways = 9*9*9*9 = 9^4 ways
CD can be selected in 9 ways and A (except zero) B, and E can be selected in 9 ways = 9*9*9*9 = 9^4 ways
DE can be selected in 9 ways and A (except zero) B, and C can be selected in 9 ways = 9*9*9*9 = 9^4 ways

So total = 4*9^4

shovan85 wrote: Will it be like 10*9*9*9*9 - 9*9*9*9? I was subtracting all possible 4 digit numbers when A becomes zero. If you see now we can have the answer equal to 9^5.

You are right to think about alternative options, that´s the proper way of gaining experience and also of understanding why "good paths/strategies/techniques are really good" (because they avoid headaches that bad ones don´t...)

About your calculations... they are right! Being more explicit:

10*9*9*9*9 is 10 options for E, 9 for D, 9 for C, 9 for B (till now perfect) but when it comes to 9 for A, we know that we are making some mistakes, that we are counting also when A is zero, and that is not allowed... your idea is to take out exactly what was "extra-counted" (correct), and then you forced A to be zero (1 option for A), then 9 options for B, 9 for C, 9 for D and 9 for E... and that is PERFECT. Do you see it clearer now?

Best Regards,
Fábio.

P.S.: you are right to check your reasoning even when the result is the same. I know same examples of wrong reasoning coming to right answer, LoL...

fskilnik wrote:

shovan85 wrote: Will it be like 10*9*9*9*9 - 9*9*9*9? I was subtracting all possible 4 digit numbers when A becomes zero. If you see now we can have the answer equal to 9^5.

You are right to think about alternative options, that´s the proper way of gaining experience and also of understanding why "good paths/strategies/techniques are really good" (because they avoid headaches that bad ones don´t...)

About your calculations... they are right! Being more explicit:

10*9*9*9*9 is 10 options for E, 9 for D, 9 for C, 9 for B (till now perfect) but when it comes to 9 for A, we know that we are making some mistakes, that we are counting also when A is zero, and that is not allowed... your idea is to take out exactly what was "extra-counted" (correct), and then you forced A to be zero (1 option for A), then 9 options for B, 9 for C, 9 for D and 9 for E... and that is PERFECT. Do you see it clearer now?

Best Regards,
Fábio.

P.S.: you are right to check your reasoning even when the result is the same. I know same examples of wrong reasoning coming to right answer, LoL...

Thanks this really helps. As per wrong reasoning to right answer I always do that in Verbal Section

shovan85 wrote:

fskilnik wrote: How many 5-digit positive integers exist in which there are exactly two consecutive digits that are the same ?

ABCDE now AB has to be equal then BC then CD then DE.

AB can be selected in 9 ways (except zero) and C, D and E each can be selected in 9 ways = 9*9*9*9 = 9^4 ways
BC can be selected in 9 ways and A (except zero) D, and E each can be selected in 9 ways = 9*9*9*9 = 9^4 ways
CD can be selected in 9 ways and A (except zero) B, and E can be selected in 9 ways = 9*9*9*9 = 9^4 ways
DE can be selected in 9 ways and A (except zero) B, and C can be selected in 9 ways = 9*9*9*9 = 9^4 ways

So total = 4*9^4

Nice! Just to emphasize the "restrictions first", I would write:

shovan85 wrote: BC can be selected in 9 ways and A (except zero) D, and E each can be selected in 9 ways = 9*9*9*9 = 9^4 ways

As

A selected in 9 ways (except zero), then BC, D, and E each can be selected in 9 ways = 9*9*9*9 = 9^4 ways

but of course it´s just a matter of preference!

What about my idea of gluing? If you consider (say) AB as a single block, you would have 4 blocks to be represented by different digits... try to finish the reasoning from now, shovan, but remember not to give the block "AB" special treatment!

shovan85 wrote: Thanks this really helps. As per wrong reasoning to right answer I always do that in Verbal Section

Great, so now add Math to it

P.S.: in teaching/learning Combinatorics, we have two types of mistakes:

(1) We missed someone in the counting
(2) We counted someone (at least) twice, what I like to call double-counting´s...

That understood, WHENEVER you are not sure about your (potential) solution, try to understand if your solution avoids the mistakes mentioned above. If you are not sure, that means you should probably try another (easier/clearer) approach, in which you (will be able to) see, clearly, that you are not making mistakes of these types.