All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
Delicate Divisibility (Posted on 2010-10-19) Difficulty: 3 of 5
For a positive base ten integer of the form ABCD drawn at random between 1111 and 9999 inclusively, determine the probability that ABCD is divisible by each of AB, AC, AD, BD and CD; but, not divisible by BC.

Note: Each of the letters in bold represents a digit from 1 to 9, whether same or different.

No Solution Yet Submitted by K Sengupta    
Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
partial analytical solution. Comment 7 of 7 |

I'm not certain this is complete/rigorous; It does however lead me to think that this problem could be solved analytically. by those of keener aptitude.

For convenience, let ABCD = N.

1. Divisibility by (10c+d) gives x(10c+d) = 100(10a+b). Let x = 100, so that a = c and b = d. 11b then divides 101(10a+b) and 11a divides 101(10a+b), so a = b, in which case (10b+c) divides N; this is prohibited by the problem.

2. It is given that (10a+b) divides N and hence (10a+b) divides (10c+d), but it has just been shown that (10a+b) cannot equal (10c+d). Hence (10c+d) = n(10a+b), where 1<n<=an<10. Accordingly all the prime factors of (10a+b) are also prime factors of (10c+d), and all the prime factors of (10c+d) are factors either of (10a+b) or n. It follows immediately that all the factors of x are held in common with 100 i.e. {2^k,5^k}

3.  (10c+d) is at least 2(10a+b). Since x(10c+d) = 100(10a+b), x cannot exceed 50. (10c+d) is at most 9(10a+b); multipliers that do not evenly divide 100 may be eliminated, giving {x, n} = {20,5:25,2^2:50,2}

4. Let (10a+b) be prime, P. The prime factors of (10c+d) are then, {2,5,P}.
(a) If 5 is a factor of (10c+d) then the problem requires d to be 5 also, compelling n=5, a=1. Since that factor is 'borrowed' from x, x=20, so 20(10c+5) = 1000+100b and c = k+5 b = 2k+1: 1155,1365,1575,1785,1995; Division by (10a+c) quickly rules out all except 1995, which is a valid solution.
(b) Let (10c+d) be even; by parity of reasoning, x= 25, n = 4, or x = 50, n=2.
a = 1;1122,1326,1734,1938,1188,1352,1768,1986 divided by {21,51} produces numerous candidates, but (10a+d) divides none of these.
a = 2; 2346,2958; no candidates
a = 3; 3162,3774; one candidate, 3774, which is a valid solution.
a = 4: 4182,4386,4794; but (10a+d) divides none of these.

5. Let (10a+b) be compound.

(a) Since 2*3*5*7 = 210, (10a+b) has at most 3 prime factors. Since no number less than 100 has two prime factors greater than 10, at least 2 of the factors must be less than 10 {2,3,5,7} of which only 3 and 7 are new.

(b) Further, each of those factors is also a factor of (10c+d), which is at least 2(10a+b), where n = 2 is 'borrowed' from x. But x(10c+d) = 100(10a+b), and every factor of 100 must still be accounted for somewhere. This combination of constraints is only possible if (10a+b) holds NO factors in common with 100.

(c) Next, assume (10a+b) to have some factor greater than 10, say 11. Now (10a+b) = 33, and n=2: 50(10c+d) = 200(33) and 10c+d = 132, which is already outside the permitted range. It follows that not only does (10a+b) have no factors in common with 100, but the sole factors that it can have are 3(singly) and 7 (singly).

(d) Then (10a+b) = 21 gives N = 2142, 2163, 2184. Division by (10b+d) leaves 2184 the sole survivor; it is also a solution.

The probability has already been computed in earlier posts.

Edited on October 21, 2010, 8:30 am
  Posted by broll on 2010-10-21 08:25:14

Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information