RMO Combinatorics DPP 1

 

First of all, let's figure out whether we want ordered triplets or unordered ones.
In combinatorics, if the question says "number of ways" it usually means ordered.

If they wanted unordered triplets, they would have said:

"Find the number of sets of 3 integers..."
"Find the number of unordered combinations of 3 factors..."

“in non-decreasing order”,

“up to permutation”,

“as an unordered product”.

etc.

Once it has been established that we want ordered triplets, it calls for stars and bars.
10^6 = 2^6 * 5^6
Let
10^6 = N
then:
N = a * b * c
Here a,b,c are 3 distinct buckets in which 6 identical objects have to be distributed(for powers of 2), and similarly for powers of 5.
So number of ways to distribute powers of 2 = (6 + 3 - 1)C(3-1) = 8C2 = 28
Similarly for powers of 5 = 8C2 = 28
Total: 28*28 = 784

But this number includes the cases where 1 or more factors could be 1.
Let's count them:
Cases where at least one factor is 1:
A = set of triplets a,b,c when a = 1 => |A| = 49
similarly |B| = |C| = 49.

Why 49: because now powers of 2 and 5 will be distributed in 2 factors in 7*7 ways.
Notice that one of those 2 factors can still be 1.

Cases where 2 factors are 1:
|A intersection B| = 1 since a = b = 1 => c = N
similarly 
|C intersection B| = 1
|A intersection C| = 1

Cases where 3 factors are 1: 0 (not possible)

So we are left with case 1 and 2.

What we want = |A U B U C| = number of cases where at least one factor is 1.
From principal of Inclusion-Exclusion:

|A U B U C|  = |A| + |B| + |C| - |A intersection B| - |C intersection B| - |A intersection C|
 = 3*49 - 3 = 144 = number of cases where at least one factor is 1.

784 - 144 = 640 = number of ways to express N as a product of 3 integers when none of them is 1.

So fare we have considered only positive factors.
But the question asks for negative factors also.
For final number to be positive, we can make 2 of the factors as negative. 3C2 ways to do that.
So total solutions with negative factors = 640 * 3.
Final answer = 640*4 = 2560.

Total: 754 + 128 = 882 = Answer

A simpler solution for question 6 is here:

Also note that there is one more way to get the original ordered count here which is (6m+2)C(2)/3!.
If you recall number of garlands made with n distinct flowers are: (n-1)!/2.
But since the flowers here are identical, we will divide by those factorials:
(6m + 3 - 1)!/3!6m!.2 = (6m+2)(6m+1)/12 same as what we got using stars and bars above.

Another way to find the number of ways of forming the team:
First team can be made in 3C1 * 3C1 * 3C1 ways = 27.
Now second team has 2 * 2 * 2 = 8 ways
Third team has only 1 way left  = 1 * 1 * 1.
Total ways = 27 * 8 = 216.
But these are ordered ways so divide by 3! to get unordered count which is 36.
For e.g. the above method(216 ways) will count {1,2,3} {4,5,6} {7,8,9} as different from {4,5,6} {1,2,3} {7,8,9}.