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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .