# Solving a system of equations with natural numbers?

first of all I am sorry if the level of this question is nowhere near the usual level of questions on this site because my math knowledge is still very basic. I hope you won't mind.

I found this problem on some site:

"A basket of oranges costs 20 dollars, a basket of pears costs 30 dollars and a basket of kiwi fruits costs 40 dollars. Eight baskets of these fruits were bought for 230 dollars. What is the largest possible number of baskets of kiwi fruits that were bought?"

The answer on the site is explained by just putting values in and see if they work. However I would like to know if there is a mathematical method of solving this.

So let me make a system of equations:

$20o+30p+40k=230$

$o+p+k=8$

extra restrictions:

$o, p, k$ are natural numbers

$k$ has to be as large as possible.

Is something like this solvable mathematically without putting in values and see if they work? If yes, how?

-

It is, but these are more complicated. If we bought $O$ orange baskets, $P$ pear baskets, and $K$ kiwi baskets, we have that

$$20O+30P+40K=230$$ $$O+P+K=8$$

So now we combine the equations:

$$20(O+P+K)+10P+20K=230$$ $$160+10P+20K=230$$ $$10P+20K=70$$ $$P+2K=7$$

now the $2K$ number is clearly even. But the right side is $odd$, meaning that we must have bought an odd number of pear baskets. So we know that $0\leq P \leq 8$, and that $P$ is odd. So our options for $P$ are in $1,3,5,7$. Looking at $P+2K=7$, we see that $K$ can be at most $3$ (if $P=1$).

More generally, $K$ can be $3,2,1,0$. So we have four different options:

$$O=4, P=1, K=3$$ $$O=3, P=3, K=2$$ $$O=2, P=5, K=1$$ $$O=1, P=7, K=0$$

-
Do I have to check all possible values each time (until the greatest K value works)? since it's not because K is a natural number, it automatically implies the other variables are natural numbers, right? Well maybe in this case it is, but I guess not in all cases with natural numbers? Is there no other way than checking for it? – xcrypt Sep 11 '12 at 22:05
Because if the problem at hand, even if you reduced it to the minimal amount of checks necessary, would have to be checked for 500 values, we'd have a lot of work to do :p – xcrypt Sep 11 '12 at 22:14
In general there are multiple solutions. So you may have one with 500 different solutions. However you wouldn't have to check for them, you could use logic like the above (especially the odd/even part) to figure out exactly what the solutions are before writing them all out (e.g. here there's one for each odd number from 1 to 8). I just wrote them out to see the results. There was no checking, since I knew from my equations that I had already figured out all restrictions, so that everything left would work. In general we're looking at Linear Diophantine Equations, if you want to learn more. – Robert Mastragostino Sep 11 '12 at 22:26
But how did you know O was going to be a natural number (if this problem would be more generalized)? – xcrypt Sep 12 '12 at 11:06
@xcrypt Because you can only buy an integer number of baskets. By phrasing the problem in terms of buying baskets, I know to see it as a problem involving integers only. I'm assuming that you can't buy half a basket. If you let yourself buy fractional baskets then there are infinitely many solutions. It'll either be implied by the setup (buying things that come in discrete pieces) or explicitly stated. – Robert Mastragostino Sep 12 '12 at 18:39

Since $20o+30p+40a=230$, we have $2o+3p+4a=23$ and from the second equation $o=8-p-a$ (Hence $p+a\leq8$). Substituting into the first equation, you get $16-2p-2a+3p+4a=23$, i.e. $p+2a=7$. So $p=7-2a$. This implies that $2a\leq7$, and since we deal with natural numbers, we have $a\leq3$. It's left to check that it is possible to have $a=3$: then $b=7-6=1$ and $o=8-3-1=4$. So we have that the maximal value of $a$ is $3$.

-

Starting with your equations $$20o+30p+40k=230$$ $$o+p+k=8$$ it is clear (if the solutions are all to be positive) that $k$ can be at most $5$, otherwise $40k\geq 240$. Now, work through the values one-by-one - try $k=5$, then $k=4$, and so on. For each of these substitutions, you can try solving the two resulting equations for $o$ and $p$.

But $k=5$ and $k=4$ don't lead to solutions with positive integers for $o$ and $p$, so these cases can be rejected. You'll find the correct solution when you get to $k=3$.

-