Each of A, B, C and D is a positive integer with the proviso that A ≤ B ≤ C ≤ D ≤ 20.

Determine the total number of quadruplets (A, B, C, D) such that A*B*C*D is divisible by 50.

Without the proviso that A, B, C and D be in ascending order the sets would constitute all 160,000 permutations chosen with replacement from the integers 1 through 20.

Each has a probability 1/2 of being even and 1/5 of being divisible by 5. None is divisible by 5^2.

To be divisible by 50, the product must be even and a multiple of 5^2, with the latter condition being possible only if at least two of the chosen four integers are multiples of 5.

The probability of the product's being even is 1-(1/2)^4.
... that it is not a multiple of 5 is (4/5)^4.
... of being a multiple of 5 but not of 25 is 5*(1/5)*(4/5)^3

making the probability that it's even and a multiple of 25, 1-(1/2)^4 - (4/5)^4 - 5*(1/5)*(4/5)^3 = 147/2000.

When multiplied by 160,000, the result would be 11760.

But we're basically being asked for combinations rather than permutations, as the elements must be in order. For example 2,2,2,2 counts once, as does 1,2,3,4. But in the permutation case, 1,2,3,4 would count 4! = 24 times, thereby upsetting the probabilities, and therefore the final count, even assuming we computed the combinations, which is 8855.

In fact 8855*147/2000 comes out to 650.8425, plainly wrong, while the following program finds the number directly by computing them all, and comes out with a count of 1570:

DEFDBL A-Z
FOR a = 1 TO 20
FOR b = a TO 20
FOR c = b TO 20
FOR d = c TO 20
  prod = a * b * c * d
  PRINT a; b; c; d, prod;
  IF prod MOD 50 = 0 THEN
    ct = ct + 1: PRINT "*"
  ELSE
    PRINT
  END IF
  comb = comb + 1
NEXT
NEXT
NEXT
NEXT
PRINT ct, comb

Posted by Charlie on 2010-08-20 13:56:11