Combinatorics – Counting 4-Digit Numbers with Digit Sum of 9

combinatoricselementary-number-theory

How many $4$-digits number are a multiple of $3$ but not of $11$ and their digits sum is a perfect square?

My solution
Observe that the only acceptable perfect squares are $9$ and $36$ (if the sum of the digits is $25$ then the number is not a multiple of $3$). Furthermore, $9999$ is the only number having a digits sum of $36$, and it's also a multiple of $11$.

Proceed to count all the permutations of all the numbers in the interval $[1000, 10000)$ having a digits sum of $9$. This is the result.

The last step is rather boring and time-consuming. Since another student solved the problem in no time, I was wondering, is there a faster way?

Best Answer

Counting the number of 4-digit numbers and sum 9 can be done using stars and bars really fast (this works because $9$ is less than $10$).

There are $9-1=8$ stars (the first number is at least $1$) and $3$ bars. Hence there are $\binom{8+3}{3}=\frac{11\cdot10\cdot9}{3\cdot2}=11\cdot5\cdot3=165$ such numbers.

Now we have to substract the ones that are multiples of $11$. There are none as you have already realized, that is because $(a+c)-(b+d)\neq 0$ as $a+c$ has a different parity as $b+d$ (they add $9$).

I checked with my computer just to make sure it is correct.

Here is the c++ code, it gives $165$.

#include <cstdio>
#include <cstdlib>
int sumd(int x){
  int a=0;
  while(x!=0){
    a+=x%10;
    x/=10;
  }
  return(a);
}
int main(){
  int a,b=0;
  for(a=1000;a<10000;a++){
    if(sumd(a)==9){
      b++;
    }
  }
  printf("%d\n",b);
}
Related Question