GMAT Question of the Day - Daily to your Mailbox; hard ones only

It is currently 16 Oct 2019, 12:40

Close

GMAT Club Daily Prep

Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track
Your Progress

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

Not interested in getting valuable practice questions and articles delivered to your email? No problem, unsubscribe here.

Close

Request Expert Reply

Confirm Cancel

CONCEPT- How to solve Integral solutions

  new topic post reply Question banks Downloads My Bookmarks Reviews Important topics  
Author Message
TAGS:

Hide Tags

Theory   
Find Similar Topics 
Retired Moderator
User avatar
V
Joined: 27 Oct 2017
Posts: 1256
Location: India
Concentration: International Business, General Management
GPA: 3.64
WE: Business Development (Energy and Utilities)
CONCEPT- How to solve Integral solutions  [#permalink]

Show Tags

New post 23 Jul 2018, 07:07

How to Solve Number of Integral Solutions Questions:



1. Equation type: Ax + By = C

Few rules to find integral solutions of this type of equations.

  • First, reduce the equation in lowest reducible form.
  • After reducing, if coefficients of x and y still have a common factor, the equation will have no solutions.
  • If x and y are co-prime in the lowest reducible form, find any one integral solution. The rest of the solutions can be derived from that integral solution.
  • For each successive integral solutions of the equation, the value x and y will change by a coefficient of the other variable .If the equation is of the type Ax – By=C (after getting the lowest reducible form) ,an increase in x will cause increase in y .If the equation is of the type Ax + By=C,an increase in x will cause a decrease in y.

Let us take an example.

2x + 3y = 39.

  • The equation is already in its reduced form and we can see that coefficients of x and y are co-prime.
  • For a given equation, you should start substituting values (by hit and trial) for the variable that has larger coefficient to find out first integral solution. In this case, it is y. Now, if we take y = 0, we will get x = 39/2(not an integer). Again, if we take y=1, we will get x = 18.So, (18,1) is our first solution.
  • If you understand the 4th point mentioned above, at one of any two consecutive integral values of y, the value of x will come out to be an integer OR at one of the 3 consecutive values of x, the value of ywill come out to be an integer. That means, if we add 2n (where n is an integer) to the first value for y, we will have to subtract 3n from the first value of x to get integral solutions.

That means,

If y =1 +2(1) = 3 , x= 18-3(1) = 15.

If y= 1 + 2(2) = 5, x= 18 – 3(2) = 12.

If y= 1 + 2(3) = 7, x = 18 – 3(3) = 9 and so on.

Step-4.This equation will have infinite number of integral solutions but finite number of non-negative integral solutions. Let’s see how we can find it.

We can keep increasing the value of y in the positive direction but x will be decreasing simultaneously and become less than 0 at one point. As lowest non negative integral value of y is 1,highest allowable positive value of x is 18 and it is decreasing by 3. So, x can take 7 non negative integral values and they are- 18, 15, 12, 9, 6, 3 and 0.Hence the given equation has 7 non negative integral values.

Note: In equation Ax + By = C, if C is divisible by any of A or B, then number of non-negative integral solutions = {C/LCM(A,B)} + 1

2. Equation type: x1+x2+⋯+xr=n

Case-1: Positive integral solutions.

Let us understand the concept from an example:

X1 + X2 + X3= 8

To solve this, imagine that there are 8 identical objects placed next to each other with gaps separating them.8 objects have 7 gaps between them. Now, I can select 2 gaps from among the 7 in \(7C2\)ways. These selected gaps will hold the plus signs of the given equation. Now, the number of objects to the left of the first plus sign, the number of objects between the two plus signs and the number of objects to the right of the second plus sign will be the values of X1, X2 and X3 respectively.

Attachment:
integral-solutions.jpg
integral-solutions.jpg [ 13.13 KiB | Viewed 896 times ]
Therefore, number of positive integral solutions of equation x1+x2+⋯+xr=n

= Number of ways in which n identical balls can be distributed into r distinct boxes where each box must contain at least one ball

= (n-1)C(r-1)

Case-2: Number of Non-negative integral solutions

We will continue with our previous equation. The number of non-negative integral solutions will be different from number of positive integral solutions as the value of variables can be 0 as well.

We will substitute the variables in the question such that this case would become similar to previous case. In previous case, (X1, X2, X3) >= 1. In this case, (X1, X2, X3) >= 0. Therefore, (X1+1, X2+1, X3+1) >= 1. Substitute X1+1=Y1, X2+1=Y2 and X3+1=Y3 in the given equation such that

(X1+1) + (X2+1) +(X3+1) = 11

=> Y1+Y2+Y3=11.

Now this case becomes similar to previous one and number of solutions is 10C2.

Therefore, Number of non-negative integral solutions of equation x1+x2+⋯+xr=n

= Number of ways in which n identical balls can be distributed into r distinct boxes where one or more boxes can be empty.

= (n+r-1)C(r-1)


Case-3.-Constraints on the variables.

Consider following equation- A+B+C = 13, where, 1=< (A,B,C) <=6.

To solve this, replace A,B,C with P,Q,R such that P= 6-A, Q=6-B and R=6-C. Then, (6-P)+(6-Q)+(6-R)=13 which implies P+Q+R=5. As A ranges from 1 to 6, P ranges from 0 to 5. Hence, the problem reduces to finding the non-negative solutions of P+Q+R = 5. The number of non-negative solutions is 7C2 = 21.

Another way is to use the following concept. If the linear equation is x1 + x2 +..+ xr= n and 0<= (x1, x2 .… xr ) <=p then the problem can be reduced to finding the exponent of\(x^n\) in the expression \(( 1 + x + x^2 + x^3..+ x^p )r.\)
_________________
GMAT Club Bot
CONCEPT- How to solve Integral solutions   [#permalink] 23 Jul 2018, 07:07
Display posts from previous: Sort by

CONCEPT- How to solve Integral solutions

  new topic post reply Question banks Downloads My Bookmarks Reviews Important topics  





Powered by phpBB © phpBB Group | Emoji artwork provided by EmojiOne