Problem Solving

hey_thr67 wrote:The number of positive integral solutions of the equation xyz=30 is,

The prime factors of 30 are 2, 3, and 5.

Now let us assume the situation as 2, 3, and 5 are going to 3 places labeled as x, y, and z. All of them have to go to some of the places and more than one can go to the same place. Hence, there may be a place that does not receive any of them which is equivalent to an integer value of 1.

Hence, all of the values can go to any of the three places.
Hence, total number of integral solutions = 3*3*3 = 27

The correct answer is D.

Note : The above method is straightforward only for numbers with prime factors without repetition. For example, if we were asked to find the number of positive integral solutions of 12, the method would slightly change. To understand why we have to go into the details of the origin of the method.

In this case, 30 = 2*3*5 --> All single primes
We can group them as any of the following

• 1. {1, 1, 30} --> 3 possible combinations
  2. {1, 2, 15} --> 6 possible combinations
  3. {1, 3, 10} --> 6 possible combinations
  4. {1, 5, 6} --> 6 possible combinations
  5. {2, 3, 5} --> 6 possible combinations
  
  A total of (3 + 4*6) = 27 combinations

But let's say for 12 = (2²)*3 --> We have two 2s
Let us write 12 as 2*2*3
We will now treat this red 2 different from black 2 and proceed as we did with 30.
We can group them as any of the following

• 1. {1, 1, 12} --> 3 possible combinations
  2. {1, 2, 6} --> 6 possible combinations
  3. {1, 2, 6} --> 6 possible combinations
  4. {1, 3, 4} --> 6 possible combinations
  5. {2, 2, 3} --> 6 possible combinations
  
  Now, note that groups 2 and 3 are same and we must discard one of them. Also group 5 will actually result in 3 combinations not 6.
  
  Hence, a total of (3 + 6 + 6 + 3) = 18 combinations

GMAT Kolaveri wrote:there was a typo in 5th. Request you to correct it.
5. {2, 2, 3}

Thanks for pointing it out.
Edited the reply.

hey_thr67 wrote:abcd= 100

how many integral solution are there then.

Okay. I take back the formula.
It's not that simple.

Let me explain it for a general case.
But before that I have to explain the concept of calculating the number of integral solutions for linear equations like (x + y + z = 3) etc. Please try to follow carefully.

Let's say we have to calculate the number of non-negative integral solutions for x, y, and z such that (x + y + z = 2)

For such simple equation we can easily found the solution triplets {x, y, z} as follows

• {0, 0, 2}, {2, 0, 0}, {0, 2, 0}, {1, 1, 0}, {1, 0, 1}, and {0, 1, 1}
  i.e. 6 such solutions

But how to calculate them in general?

In this case we can transform the problem as "In how many ways two 1s can be distributed in three buckets without any restrictions?". This means one bucket can receive more than one 1s.

Now visualize this : We have two 1s lying on the ground. And to distribute them in three buckets we are going to put two separators anywhere to separate the two 1s. Let's represent the separators by '|'.

Hence,

• |1|1 ---> Corresponds to {0, 1, 1}
  ||1 ---> Corresponds to {0, 0, 2}
  1||1 ---> Corresponds to {1, 0, 1} etc

Now the problem is reduced to "In how many ways we can arrange two 1s and two separators?" And the answer to the question will be 4!/[(2!)*(2!)] = 6

Similarly if we are asked to find the number of non-negative integral solutions for x, y, z, and w such that (x + y + z + w = 2), the answer will be 5!/[(3!)*(2!)] = 10



Now coming to our problem, we need to find the number of positive integral solutions of abcd = 100 = (2²)*(5²)
It is obvious that a, b, c, and d will be made of 1, 2, and 5 only. Hence, we can assume that they will be of the form,

• a = (2^x1)*(5^y1)
  b = (2^x2)*(5^y2)
  c = (2^x3)*(5^y3)
  d = (2^x4)*(5^y4)

As we have only two 2s and two 5s, we must satisfy the following

• x1 + x2 +x3 +x4 = 2
  y1 + y2 + y3 + y4 = 2

We need to find the number of non-negative integral solutions of x1, x2, .., y1, y2... etc for the above equations.

As we have shown earlier number non-negative integral solutions to both of these two equations will be 10.

Hence, number of positive integral solution for abcd = 100 will be 10*10 = 100


Let's cross-check it.
We can group the factor of 100 as any of the following

• 1. {1, 1, 1, 100} --> 4 possible combinations
  2. {1, 1, 2, 50} --> 12 possible combinations
  3. {1, 1, 4, 25} --> 12 possible combinations
  4. {1, 1, 5, 20} --> 12 possible combinations
  5. {1, 1, 10, 10} --> 6 possible combinations
  6. {1, 2, 2, 25} --> 12 possible combinations
  7. {1, 2, 5, 10} --> 24 possible combinations
  8. {1, 4, 5, 5} --> 12 possible combinations
  9. {2, 2, 5, 5} --> 6 possible combinations
  
  A total of (4 + 5*12 + 2*6 + 24) = 100 combinations

Now reconsider my example of xyz = 12 = (2²)*3

Each of x, y, and z will be made of 1, 2, and 3 only.
Hence, we can assume that they will be of the form,

• x = (2^p1)*(3^q1)
  y = (2^p2)*(3^q2)
  z = (2^p4)*(3^q3)

As we have only two 2s and one 3, we must satisfy the following

• p1 + p2 + p3 = 2
  q1 + q2 + q3 = 1

Now, number non-negative integral solutions to (p1 + p2 + p3 = 2) will be 4!/[(2!)*(2!)] = 6
And, number non-negative integral solutions to (q1 + q2 + q3 = 1) will be 3!/(2!) = 3

Hence, number of positive integral solution for xyz = 12 will be 6*3 = 18

1947 wrote:Anurag, Are we expected to know all this in GMAT quant ?

It's unlikely that GMAT would ask for any of this concepts. Even if it asks to solve this kind of problems, they will be like xyz = 12 or 30, which can easily solved by manual counting of factors.