# simple word problem

There are two types of apples. One's 120 gr and the other one is 200gr. I need to buy 1000 gr of apples. How many apples I can buy at most?

I need the algebra on this one, I tried

120x + 200y = 1000 but don't know what to do from that point.

-
In how many ways you can express $25$ using form : $3x+5y$ ? –  pedja Apr 26 '12 at 10:21
I don't understand what you mean pedja –  alik Apr 26 '12 at 10:26
divide equation by $40$... –  pedja Apr 26 '12 at 10:33

Buy 5 of the first type and 2 of the second type for a total of 7. This is optimal since we can't buy any more than 5 of the first type and still end up with exactly a kilogram, and if we buy any fewer than 5 of the first type we will end up with fewer than 7 apples. I'm sorry but I don't know a general way to solve this type of problem without enumerating all of the partitions. The linear equation is correct but it needs to be solved in such a way that $x+y$ is maximized and also constrained to integers.

-

We have $$120 a + 200 b = 1000 \\ 3a + 5b = 25$$ Now by extended Euclidean algorithm $$\underline{5}=\underline{3}\cdot 1+\underline{2} \\ \underline{3}=\underline{2}\cdot 1+\underline{1}$$ Thus $$\underline{1}=\underline{3}-\underline{2}\cdot 1 = \underline{3}-\left(\underline{5}-\underline{3}\cdot 1\right) = \underline{3}-\underline{5}+\underline{3}=2\cdot\underline 3 - \underline 5$$ And $$\underline{3}\cdot 50 +\underline{5}\cdot \left(-25\right) = 25$$ Apparently adding $5t$ to the coefficient to $3$ and $-3t$ to the coefficient of $5$ preserves the right hand side $$\underline{3}\cdot \left(50+5t\right)+\underline{5}\cdot \left(-25+3t\right) = 25$$ Because $a,b>0$ we find that the least $t$ would be $-9$ $$\underline{3}\cdot\left(50-45\right) + \underline 5 \cdot \left(-25+27\right) = 25$$ A bigger $t$ does not yield $a,b>0$ and a smaller $t$ yields a less $a+b$ (because it adds 3 and removes 5 from $a+b$)

Thus solution is $a=5, b=2$

-
Thanks - but way too complicated for me to understand. –  alik Apr 26 '12 at 10:57

To go off what peja mentioned, I think this is a relatively simple and intuitive way to see what's happened.

We start with $120x+200y=1000$. Now divide the equation by 40 - this leaves us with $$3x + 5y = 25.$$

Some rearranging turns this into $$3x = 5(5-y).$$

Now, both $x$ and $y$ are meant to be nonnegative integers, which also means both sides of this equation are. This gives two possibilities: either both sides are zero, in which case $x=0$ and $y=5$ (i.e., you buy 5 apples weighing 200g). Or they're both nonzero, in which case they have to have the same prime factors - everything that divides the right hand side divides the left hand side and vice versa.

So because 3 is a factor of the left hand side and $5$ isn't divisible by $3$, $5-y$ has to be divisible by 3. The only way for that to be true without ending up needing to buy negative apples of one or the other kind is for $y=2$. Then $3x=15$ and so $x=5$. This gives you seven apples in total, more than the zero case, so that's your answer.

-

It is clear that we will not be buying many apples. For "large" problems, we would need general theory, or a suitable computer program. But this is a small problem, and algebra need not come into play.

You will be buying at most $5$ big apples.

Try buying $0$ big apples, and the rest small. It is easy to see that we can't get to exactly $1000$ using small apples, since $120$ does not divide $1000$ exactly.

Try buying $1$ big apple, and the rest small. Then we need to get to $800$ grams using only small apples. Can't be done, since $120$ is not a factor of $1000$.

Try buying $2$ big apples, and the rest small. That leaves $600$ grams to be made with small apples. This can be done, since $\frac{600}{120}=5$.

Try buying $3$ big apples, the rest small. Can't be done. Try buying $4$. Can't be done.

Try buying $5$ big apples. Works fine.

With $2$ big, we had a total of $7$ apples, with $5$ big we had a total of $5$ apples. So we get the largest number of apples by buying $2$ big, $5$ small, a total of $7$.

It might have been easier to see what's going on by knocking off a $0$, and using $12$, $20$, $100$. It might have been still easier to further divide by $4$, and using $3$, $5$, $25$.

Remark: Note that there are no $x$'s and/or $y$'s in the analysis.

For me, writing $120x+200y=1000$, and then perhaps $3x+4y=25$, would be automatic. But the rest would have been exactly like in the above solution: a scan of the possibilities, leading to a quick answer. The equation would only be used as an organizing device, easier (for me) than visualizing small yellow apples and big red apples. Remember that this is a concrete problem. Symbols can be very useful, but it is even more useful to experiment, in order to find out what's really going on.

-