Pages

Thursday, November 4, 2010

Integral Solutions of Ax + By = C

This topic appears much later in my grand scheme of things but I promised '

Have you come across a question which is similar to the following:

A boy goes to a supermarket and buys some pencils and erasers . The cost of each pencil is $0.3 and cost of each eraser is $0.5. In how many ways could he have bought the pencils and erasers if he paid a total sum of $4.20 and bought at least one pencil and at least one eraser?

I am sure, most of you will be able to come up with the following equation: 0.3p + 0.5e = 4.2 and then, by multiplying both sides by 10, you will get:
3p + 5e = 42
(p - the number of pencils, e - the number of erasers
)

What next? This is the equation of a line and has infinite solutions i.e. for every value of p, exists a value of e.

e.g. When p = 0, e = 42/5; when p = 0.1, e = (41.7)/5; when p = 1, e = 39/5 and so on…
Then, should I say he can buy the pencils and erasers in infinite ways e.g. 0 pencils and 42/5 erasers or 0.1 pencils and 41.7/5 erasers or 1 pencil and 39/5 erasers etc?

No! There is a catch! (but of course!)
Can I buy 42/5 = 8.4 erasers? I can buy 8 erasers or 9 erasers but how can I buy 8.4 erasers? So what we are looking for is integral values of p and e. This is one of the constraints on our solution and will narrow down the acceptable values.

Let us write the equation again: 3p + 5e = 42
One set of integral solution to this equation is p = 14, e = 0 (I will discuss later how I got to this.)
When you put p = 14 and e = 0 above, you get 3*14 + 5*0 = 42. Here, 3p = 42 and 5e = 0 and they add up to give 42. What if I want to get 42 in another way? I can decrease 3p by some amount and will have to increase 5e by the same amount to get the same sum of 42. E.g. I decrease 3p by 1 and increase 5e by 1 to get 41 + 1 = 42. So p was 14 and 3p was 42, but now I want 3p to be 41. What should p be? p = 41/3 - but this is not an integral value! We are looking for only integral solutions. Then let’s try to decrease p instead of 3p to ensure that we get integral values of p. If p = 13 instead of 14, I get 3p = 39. I decreased 3p by 3 .
Now, I must increase 5e by 3 to get the same sum of 42. 5e was 0, and needs to be 3 now. What will e be now? e = 3/5. Unfortunately, the problem is still the same. We need integral values of p and e. I can increase 5e is blocks of 5 only i.e. if e = 0, 5e = 0; e = 1, 5e = 5; e = 2, 5e = 10 etc.
Now the problem is that 3p can be decreased only in blocks of 3 and 5e can be increased only in blocks of 5. But the decrease in 3p has to be offset by the increase in 5e! Therefore, we should decrease/increase them in blocks of 15 (lowest common multiple of 3 and 5). So when I try to decrease 3p by 15, p decreases by 5 (the second term, 5e, has 5 as the co-efficient) and when I try to increase 5e by 15, e increases by 3 (the co-efficient of the first term)
. The table given below will make it clearer.

and so on…

Note that in second, third and fourth rows, we have been decreasing 3p and increasing 5e. We could do the opposite as done in the last two rows of the table above. We could increase p by 5 and decrease e by 3 to get more solutions. Once we have one solution, we can figure out infinite solutions. Then is our answer still infinite? Why the hell did we do all this work then!

Actually, there is another constraint. Can the number of pencils or erasers be negative? Also, since he buys at least one pencil and at least one eraser, p and e cannot be 0 .(First solution discarded) Then, a solution is one where values of p and e are positive integers.

Go back to the table. After the third row of solutions, if you keep decreasing 3p, p will be negative every time. Look at the last row - if you keep decreasing 5e, e will remain negative. Therefore, there are only two solutions (p = 9, e = 3) and (p = 4, e = 6). He could have bought pencils and erasers in only two ways.

Now we come back to ‘How do you get the first solution’. Simple – by brute force. Here it is easy since 42 is a multiple of 3. Then we know that p can be 14 to give 42 and 5e can be 0.

An equation such as 3p + 5e = 49 is trickier.

First, I check for e = 1. Reduce 49 by 5 to get 44 and then check – is 44 divisible by 3? – No.

Then check for e = 2. Reduce 44 by 5 again to get 39 – is 39 divisible by 3? – Yes!

This means 3p can be 39 and 5e can be 10 giving us p = 13 and e = 2. This would be our first solution and would lead us to more, possibly. How many positive integral solutions will this equation have?

Things to ponder upon:

- What can you say if your equation is of the form 3x + 6y = 40?

- Should coefficients of x and y be co-prime?

- And, a trickier thing to think about - how many integral solutions would 3x - 5y = 42 have?

(If you like, I would be happy to confirm your answers!)

9 comments:

  1. No problem! I intend to discuss many more little topics in the days to come... Requests are welcome!

    ReplyDelete
  2. 3x + 6y = 40 has no integral solutions since no combination of x and y would equal 40.

    I'm confused by the question of "should" coefficients be coprime. Would it not depend entirely on what the two coefficients are set equal to? 8x + 12y = 40 has an integral solution and they are not coprime.

    3x - 5y = 42 would have infinite solutions at any point where x>=14, with intervals of every five units of x causing an increase of three units of y.

    ReplyDelete
  3. Hey Logan,
    Great Thinking!
    Let me explain.

    - You are right about 3x + 6y = 40. I can say it is equal to 3(x + 2y) = 40 or
    x + 2y = 40/3. You cannot add integers and get a fraction 40/3 so no solution.

    - When I see 8x + 12y = 40, I bring it down to 2x + 3y = 10 and then solve since 4 is a common factor of all coefficients. So what I need to think is that is it possible that coefficients of x and y are not co-prime but the equation is in the lowest form e.g. in the question above. It is not possible because of the explanation given for the question above.

    - Great! That is what I wanted to ask. You get solutions when x increases by 5 and y also increases, but by 3. Since there is a negative in between, they both will either increase or both will decrease. Which brings me to my next question, why cant x be less than 14? What about x = 9 and y = -3? (still integers, right!) and so on...

    ReplyDelete
  4. This comment has been removed by the author.

    ReplyDelete
  5. As for the Pen and eraser question - my first take is to use brute force: list down factors of 5 in a column(upto 40) and then calc what you need to add to them to get 42. There are only two solutions :
    4p,6e : 12+30
    9p,3e : 27+15

    ReplyDelete
  6. 3x + 6y = 40
    x+2y=40/3
    No Integral solution

    3x-5y=42
    x=(42+5y)/3
    x=14 + 5y/3
    5y/3 or y/3 will be an integer at only specific values such that y=3k (k = all Ints) and for each such value of y , there will be a corresponding value of x.

    ReplyDelete
  7. Awesome dear, thanks a lot.
    You can add one more thing that solns to equation values are in AP and the value of d is equal to the coefficient of other term...

    ReplyDelete
  8. hey karishma,
    in your explanantion above for equation 3p+5e=49, you say decrease 49 by 5.
    what is the reason behind all of a sudden decreasing it by 5 and why not any other number?

    ReplyDelete