Saturday, September 29, 2012


How many ordered triples of pairwise distinct, positive integers (a,b,c) are there such that abc=106?
Clarification: Ordered triples - (1,10,105) and (105,10,1) count as different solutions.
Clarification: Pairwise distinct - a set of integers are pairwise distinct if no two of them are the same. For example, the set (1,1,106) is NOT pairwise distinct, hence does not count as a solution.

Set a=2a15a2,b=2b15b2,c=2c15c2. We first count the number of triples without restriction. We seek the number of non-negative integer solutions to a1+b1+c1=6,a2+b2+c2=6. This is equivalent to arranging 6 1's with 2 0's (dividing blocks), thus there are (6+22) ways to solve either of the two equations. By the rule of product, there are (82)(82)=784 solutions in total.
If a=b, we seek the number of non-negative integer solutions to 2a1+c1=6,2a2+c2=6. For each equation, there are 4 solutions, corresponding to ai=0,1,2,3. By the product rule, there are 44=16 solutions in all. The cases b=c and c=a are exactly the same. If a=b=c, there is exactly 1 solution.
Let A,B, and C be the set of triples where b=c,c=a, and a=b, respectively. By the Principle of Inclusion and Exclusion, |ABC|=|A|+|B|+|C|−|AB|−|BC|−|CA|+|ABC|=16+16+16111+1=46. Hence, the number of triples with pairwise distinct values is 78446=738.

No comments:

Post a Comment