Urgent Help: To solve a problem

静雯

Smart man,

Could you use a smart way to solve the problem below? I'm really crazy for it.

How many 5-digit multiples of 3 have at least one of its digits equal to 3?

davidbin

Let me have a try

Total 5 digits number from 10000~99999: 99999-10000+1 = 90000
multipled by 3, the result without single digit of 3 could be
4a1a2a3a4
5a1a2a3a4
.....
9a1a2a3a4
and
1a1a2a3a4a5
2a1a2a3a4a5
a1,a2,a3,a4,a5 belong (0,1,2,4,5,6,7,8,9)
0,1,2,4,5,6,7,8,9 mod 3 , the result can be grouped into 3
R0(0,6,9), R1(1,4,7), R2(2,5,8),each group has 3 numbers
4a1a2a3a4 total possiblity is 9X9X9X3= 2187
get a1,a2,a3 from (0,1,2,4,5,6,7,8,9), 9 choices for each number. For any a1,a2,a3 combination, you always have 3 choices to ensure the number can be devided by 3
(4~9)a1a2a3a4 total possibility = 6x2187=13122
(1~2)a1a2a3a4a5 totol possibility = 2x9x9x9x9x3 = 39366
Result = 90000- 13122-39366 = 37512


  

wd369

答案是不是这个有关: 从1000 到 9999 中 可以被3 整除的数字个数.

frekiwang

My solution:

Let
a(n) denote the number of n-digit numbers which are mutiples of 3 and include at least a '3';
b(n) ................................................................. are not mutiples of 3 and include at least a '3';
c(n) ................................................................. are mutiples of 3 and include no '3';
d(n) ................................................................. are not mutiples of 3 and include no '3';
By considering adding an addtional number at the end of n-digit number to form a (n+1)-digit number,
we can conclude:
a(n+1)=4a(n)+3b(n)+c(n) (numbers in a(n), you can add 0,3,6,9 at the end; numbers in b(n), you can add either 1,4,7 or 2,5,8 at the end; numbers in c(n), you can add a 3)
b(n+1)=6a(n)+7b(n)+d(n) (similar reasoning)
c(n+1)=3c(n)+3d(n) (similar reasoning)
d(n+1)=6c(n)+6d(n) (similar reasoning)

We know a(1)=1, b(1)=0, c(1)=2, d(1)=6
work recursively, we have
a(2)=6, b(2)=12, c(2)=24, d(2)=48
a(3)=84, b(3)=168, c(3)=216, d(3)=432
a(4)=1056, b(4)=2112, c(4)=1944, d(4)=3888
a(5)=12504, b(5)=25008, c(5)=17496, d(5)=34992

So the answer is 12504. The method above works for b(n),c(n),d(n) groups very well, so it is a more 'general' approach.

There is a 'simpler' way, which is by considering the number of 5-digit numbers which include 3 (90000-9*8*8*8*8=37512), and approximately 1/3 of them are divisibly by 3, so the answer is 37512/3=12504 as well, but you need a paragraph to explain why it is exactly 1/3 but not approximately.

davidbin

Misunderstood the question, correction is below
Total 5 digits number from 10000~99999: 99999-10000+1 = 90000,
90000/3 = 30000
So in total there are 30000 number multiples of 3 among 5 digits number
Without single digit of 3 could be
1a1a2a3a4
2a1a2a3a4
4a1a2a3a4
5a1a2a3a4
.....
9a1a2a3a4
a1,a2,a3,a4 belong (0,1,2,4,5,6,7,8,9)
0,1,2,4,5,6,7,8,9 mod 3 , the result can be grouped into 3
R0(0,6,9), R1(1,4,7), R2(2,5,8),each group has 3 numbers
1a1a2a3a4 total possiblity is 9X9X9X3= 2187
get a1,a2,a3 from (0,1,2,4,5,6,7,8,9), 9 choices for each number. For every 1, a1,a2,a3 combination, you always have 3 choices for a4 to ensure the number 1a1a2a3a4 can be devided by 3
(1,2,4~9)a1a2a3a4 total possibility = 8x2187=17496
Result = 30000- 17496 = 12504
Below formula valid for 3 & 9
(90000- 8x9x9x9x9)/X x=3 or 9

静雯

davidbin 发表于 22-3-2012 05:31
Misunderstood the question, correction is below
Total 5 digits number from 10000~99999: 99999-10000+ ...

昨天半夜想起这种方法, 与你的类似。
30000 multipies of 3 from 10000 to 99999.
5-digit:   abcde without single 3.
There are 8 choices for a, 9 choices for b, 9 choices for c, 9 choices for d and 3 choices for e.
8*9*9*9*3=17496
30000-17496=12504