Solving basic combinatorics

89 Views Asked by At

I started course in combinatorics and, as I'm still not much into it, I'm solving some basic problems to start with. So here is one of them: How many 5-digit positive integers are there such that 9 divides them? It's simple problem to solve probably but I want to see the way of thinking when solving this. I know that for the number in order to be divisible by 9, its sum of digits must be divisible by 9. I also know how to solve this problem: how many solutions does the following equation have (x1+x2+x3+x4+x5 = k). It is reduced to multisets. But the problem with the first task is that i should limit x1...x5 not to be greater than 9, as they represent digits of an integer. Thanks in advance!

1

There are 1 best solutions below

3
On BEST ANSWER

Number of integers less than or equal to $n$, exactly divisible by $k$ is $\lfloor \dfrac nk \rfloor$.

$$\begin{align}\text{Number of $5$ digit numbers divisible by} 9 &= \text{Number of integers divisible by 9, which are} \le 99999\\&\text{- Number of integers divisible by 9, which are} \le 9999 \\&= \lfloor \dfrac{99999}{9} \rfloor - \lfloor \dfrac{9999}{9} \rfloor\end{align}$$