0
$\begingroup$

Inspired by this question.

How many nine digit number can be formed by using the digits 1,2,3,4,5,6,7,8,9 so that each number has 7 consecutive descending digits?

Found the solution myself (see below), have fun trying it yourself :-)

$\endgroup$

1 Answer 1

0
$\begingroup$

You only have 3 sequences of 7-times decreasing digits, that are a=(9,8,7,6,5,4,3), b=(8,7,6,5,4,3,2) and c=(7,6,5,4,3,2,1) (3 possibilities). There are only 2 places left in your 9-digit number that could have any digit. Also they could be both left to our 7-digit-sequence (7ds) or right of it or embrace it. Since their content doesn't depend on the 7ds or one another, it should be $3\cdot 9^2\cdot 3=729$ possibilities, right?

Wrong.

Exactly 7 digits

We also counted numbers with more than 7 consecutive digits. With

$$X\in\{1,\ldots,9\}, \hat{1} \in\{2,\ldots,9\}, \hat{2}\in\{1,3,4,5,\ldots,9\}, \hat{8}\in\{1,\ldots,6,7,9\}, \hat{9}\in\{1,\ldots,8\}$$

we have $N[a]=\{a\hat{2}X,Xa\hat{2},XXa\}$, $N[b]=\{b\hat{1}X,\hat{9}b\hat{1},X\hat{9}b\}$, $N[c]=\{cXX,\hat{8}cX,X\hat{8}c\}$. All these sets are mutually exclusive, also note that $N[a]=N[c]$, so

$$N[a\cup b\cup c] = (N[a] + N[c]) + N[b] = 2(8\cdot 9 + 9\cdot 8 + 9\cdot 9) + (8\cdot 9 + 8\cdot 8 + 9\cdot 8) = 658$$

At least 7 digits

We forgot the inclusion/exclusion principle, i.e. we counted some sequences multiple times, like a21, 9b1 and 98c. inclusion/exclusion principle tells us the number we seek is

$$N[a\cup b\cup c] = N[a] + N[b] + N[c] - N[a\cap b] - N[a\cap c] - N[b \cap c] + N[a\cap b\cap c]$$

As stated above for all three $(a,b,c)$ there are only 2 free places for 1 of 9 digits and 3 possible placements, so $N[a] =N[b]=N[c]=9^2\cdot 3 =243$.

$$\{a\cap b\} = \{a2x,xa2\}, \{a\cap c\} = \{a21\}, \{b\cap c\} = \{b1x,xb1\}$$

where $x$ denotes any digit. Therefore we have $N[a\cap b]=N[b\cap c]=18$ and $N[a\cap c] = N[a\cap b\cap c] = 1$, hence

$$N[a\cup b\cup c] = 3\cdot 243 - 2\cdot 18 + 2 = 695$$

$\endgroup$
1
  • $\begingroup$ @KanwaljitSingh Just your intuition or anything more? $\endgroup$
    – Ayutac
    Jan 3, 2017 at 7:08

You must log in to answer this question.

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