3
$\begingroup$

We have a 6 digit number $a_1a_2a_3a_4a_5a_6$ and $a_1 \neq 0$

also $a_1 \neq a_2, a_2 \neq a_3, a_3 \neq a_4, a_4 \neq a_5, a_5 \neq a_6, a_6 \neq a_1$

All of numbers where $a_1 \neq a_2, a_2 \neq a_3, a_3 \neq a_4, a_4 \neq a_5, a_5 \neq a_6$ are $9^6$
I'm having troubles with the last case.
I know that this is generalization of $a_1a_2a_3$ for which there are $8*9^2$ numbers but cannot figure out how they are related

and this is the source file which counts all those digits.

bool foo(int num)
{
    char str[15] = {};
    int i=0;
    while(num)
    {
        str[i]=num%10;
        num/=10;
        i++;
    }
    str[i]=str[0];
     for(int j=0;j<i;j++)
            if(str[j]==str[j+1])
                return false;
    return true;
}

int main()
{
    int sum=0;
    for(int i=100000;i<=999999;i++)
        if(foo(i))
            sum++;
    cout<<sum;
    return 0;
}

Please note that this program produces answer: 478305, which is correct
Also note that the answer 8*9^5 misses some cases

$\endgroup$
3
  • $\begingroup$ Can you please identify the cases that the 8*9^5 misses? I can't understand that. And please indicate how you know that 478305 is the correct answer. $\endgroup$
    – Mark
    Feb 1, 2015 at 21:44
  • $\begingroup$ consider similar problem $a1a2a3a4$, your solution would be 8*9^3 in this case, but this is also wrong. it only works for $a1a2a3$, but I dont know why. And I know the answer is correct, because I double checked the program in debugger, to see if it's bug free $\endgroup$
    – shcolf
    Feb 1, 2015 at 21:49
  • $\begingroup$ I agree with you. If a1 = a5, then a6 can be any one of 9 numbers. Those are the additional cases that I had overlooked. I independently wrote a Perl program and got the same answer as your program. $\endgroup$
    – Mark
    Feb 1, 2015 at 22:40

4 Answers 4

3
$\begingroup$

Let $f(n)$ denote the number of strings $a_1\cdots a_n$, where no consecutive digits are equal, and $a_1\ne a_n$. Let $g(n)$ be the number of strings where no consecutive digits are equal, but $a_1 = a_n$. The OP notes that $f(n)+g(n)=9^n$.

We'll write down a recurrence involving both $f$ and $g$, and solve for $f$. It's easy to see that $f(1)=9$, $f(2)=9^2$, $f(3)=8\cdot 9^2$. So suppose $n\ge 4$; to compute $g(n)$, we assume $a_n=a_1$. We have $9$ choices for each of $a_1,\ldots, a_{n-2}$. The number of choices for $a_{n-1}$ depends on whether $a_{n-2} = a_n$ or not. If so, there are $9$ choices, and there are $g(n-2)$ ways for this to happen. If not, there are only $8$ choices for $a_{n-1}$, and there are $f(n-2)$ ways for this to happen.

This gives the recurrence $g(n)=9 g(n-2) + 8 f(n-2)$. Substituting $g(n)=9^n-f(n)$ we see $$ f(n) = 8\cdot 9^{n-1} + f(n-2),\,n\ge 4.$$

We conclude $f(6)= 8\cdot 9^5 + 8\cdot 9^3 + 9^2 = 478305.$

$\endgroup$
1
  • $\begingroup$ Thank you, now everything seems to be clear :) $\endgroup$
    – shcolf
    Feb 1, 2015 at 21:58
2
$\begingroup$

WRONG ANSWER (for reason noted below)

a1 can be any one of 9 numbers, (1,2,...,9)
a2 can be any one of 9 numbers, (0,1,...,9 not a1)
.
.
.
a6 can be any one of 8 numbers, (0,1,...,9 not a5 and not a1)

These choices are all unique and exhaustive. So I get 9^5 * 8.

CORRECTION: Saying that a6 can be any one of 8 numbers, (0,1,...,9 not a5 and not a1) IS WRONG if a5=a1. In that case, a6 can be any one of 9 numbers.

$\endgroup$
0
$\begingroup$

Here's another approach. We will do cases based on the digits in positions $1$, $3$, and $5$.

Case 1:

$a$, ___ , $a$, ____, $a$, ____.

There are $9$ ways to select the digit $a$, and $9$ ways to fill each blank. So $9^4$ numbers of interest in this case.

Case 2.1, 2.2, 2.3:

$a$, ___ , $a$, ____, $b$, ____

and $a$, ___ , $b$, ____, $b$, ____

and $b$, ___ , $a$, ____, $a$, ____

For each of three subcases, there are $9\cdot 9$ ways to choose $a$ and $b$, and $9\cdot 8\cdot 8$ ways to fill the blanks. So there are a total of $3\cdot 9^3\cdot 8^2$ numbers of interest in these three subcases combined.

Case 3:

$a$, ___ , $b$, ____, $c$, ____.

There are $9\cdot 9\cdot 8$ ways to choose $a, b,c$, and $8$ ways to fill each blank. So there are a total of $9^2\cdot 8^4$ numbers of interest in this case.

Grand total: $9^4+3\cdot 9^3\cdot 8^2+9^2\cdot8^4=478305$ numbers of interest.

$\endgroup$
0
$\begingroup$

You need to examine each position - whether it is the same as $a_1$, or not. Although this is slow in general, it's OK with a few cases, like here for n=6. So here we go, I denote different choices with different letters:

1. $a_1 = A$ - 9 choices. | A | _ | _ | _ | _ | _ |

2. $a_2 = B$ - 9 choices. | A | B | _ | _ | _ | _ |

3.A. $a_3 = a_1 = A$ - 1 choice. Then $a_4 = D$ - 9 choices. | A | B | A | D | _ | _ |

  • 3.A.4.A. $a_5 = a_1 = A$ - 1 choice, then $a_6$ - 9 choices
    - in total $\fbox{$9^4$}$ | A | B | A | D | A | F |

  • 3.A.4.B $a_5 = E \ne a_1$ - 8 choices, then $a_6$ has 8 choices

    - in total $\fbox{$9^3.8^2$}$ | A | B | A | D | E | F |


3.B. $a_3 = C \ne a_1$ - 8 choices | A | B | C | _ | _ | _ |

  • 3.B.4.A. $a_4 = A$ - 1 choice => $a_5 = E\ne A$ - 9 choices => $a_6 = F$ - 8 choices

    - in total $\fbox{$9^3.8^2$}$ | A | B | C | A | E | F |


  • 3.B.4.B. $a_4 = D\ne a_1$ - 8 choices | A | B | C | D | _ | _ |

    • 3.B.4.B.5.A. $a_5 = a_1 = A$ - 1 choice => $a_6 = F$ - 9 choices
      - in total $\fbox{$9^3.8^2$}$ | A | B | C | D | A | F |

    • 3.B.4.B.5.B $a_5 = E\ne a_1$ - 8 choices => $a_6 = F$ - 8 choices
      - in total $\fbox{$9^2.8^4$}$ | A | B | C | D | E | F |


And now, just sum up the results: $3.9^3.8^2+9^4+9^2.8^4 = $478305, exactly what we needed.

Tad's response is also great and timely!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.