Some Triples

Probability Level 4

How many natural numbers (written in base 10) of 5 digits chosen from the set {1,3,4,5,7} are divisible by 3?

The answer is 1031.

2 solutions

Akshay Bodhare
Dec 26, 2014

The answer is the addition of coefficients of all powers divisible by 3 in

(x+x^3+x^4+x^5+x^7)^5

which is 1031

this is an application of multinomial theorem.Good question

but still, isn't this method too long as we have to check for all multiples of 3 from 9 to 33 ??

Vighnesh Raut - 6 years, 4 months ago

Not really, if you use powers of x in mod 3 by taking the generating function $\displaystyle (1 + 3x + x^2)^5$ .

Rajen Kapur - 6 years ago

I did a different method but made an error entering the solution.

I separated the digits into equivalence classes based on themselves modulo $3$ :

${3}_0 , {1,4,7}_1 , {5}_2$ .

For a 5-digit number to be a multiple of $3$ , the sum of the classes above must be $9,6,3,0$ :

$9$ : 2,2,2,2,1 in some order: $\binom{5}{1}$ orders, $3$ choices from set 1.

$15$ .

$6$ : 2,2,2,0,0 in some order: $\binom{5}{2}$ orders.

2,2,1,1,0 in some order: $\binom{5}{2, 2}$ orders, $3^2$ choices from set 1.

2,1,1,1,1 in some order: $\binom{5}{1}$ orders, $3^4$ choices from set 1.

$10 + 270 + 405 = 685$ .

$3$ : 2,1,0,0,0 in some order: $\binom{5}{1, 1}$ orders, $3$ choices from set 1.

1,1,1,0,0 in some order: $\binom{5}{2}$ orders, $3^3$ choices from set 1.

$60 + 270 = 330$ .

$0$ : 0,0,0,0,0 in some order: $\binom{5}{0}$ orders.

$1$ .

Hence $15 + 685 + 330 + 1 = 1031$ numbers.

Alex Burgess - 2 years, 2 months ago

Brock Brown
Dec 27, 2014

a = set(('1','3','4','5','7'))
def valid(x):
    for digit in str(x):
        if digit not in a:
            return False
    return True
i = 10002 #first 5 digit multiple of 3
count = 0
while i < 100000:
    if valid(i):
        count += 1
    i += 3
print count

Some Triples

The answer is 1031.

2 solutions

0 pending reports