# Linear Algebra

• Jan 31st 2006, 05:05 AM
TexasGirl
Linear Algebra
You want to buy 100 birds for exactly 100 coins. How many roosters, hens and chicks can you buy if a rooster costs 5 coins, a hen costs 4 coins and the price for four chicks is 1 coin.

Do I set this up like this:

5R + 4H + (1/4)C = 100
R+C+H = 100

I seem to be going in a circle on this little problem. Any suggestions?
• Jan 31st 2006, 05:23 AM
CaptainBlack
Quote:

Originally Posted by TexasGirl
You want to buy 100 birds for exactly 100 coins. How many roosters, hens and chicks can you buy if a rooster costs 5 coins, a hen costs 4 coins and the price for four chicks is 1 coin.

Do I set this up like this:

5R + 4H + (1/4)C = 100
R+C+H = 100

I seem to be going in a circle on this little problem. Any suggestions?

So:

$\displaystyle 20R+16H+C=400$
$\displaystyle R+H+C=100$,

Rearranging to solve these for $\displaystyle C$ and setting the results equal:

$\displaystyle C=400-20R-16H$
$\displaystyle C=100-R-H$,

gives:

$\displaystyle 400-20R-16H=100-R-H$.

Rearranging again gives:

$\displaystyle 300=19R+15H$.

Then:

$\displaystyle 300-15H=19R$,

but the LHS is divisible by $\displaystyle 15$, so $\displaystyle R$ is divisible by $\displaystyle 15$ (as $\displaystyle 19$ is prime).

But $\displaystyle 300/19>=R>=0$, so $\displaystyle R$ must be $\displaystyle 15$, then: $\displaystyle H=1$, and $\displaystyle C=84$.

QED.
• Jan 31st 2006, 08:33 AM
ThePerfectHacker
Quote:

Originally Posted by TexasGirl
You want to buy 100 birds for exactly 100 coins. How many roosters, hens and chicks can you buy if a rooster costs 5 coins, a hen costs 4 coins and the price for four chicks is 1 coin.

Do I set this up like this:

5R + 4H + (1/4)C = 100
R+C+H = 100

I seem to be going in a circle on this little problem. Any suggestions?

This is a nice problem, I forgot the name of it some Chinese problem. This is not a basic Problem of linear algebra. This is a Diophantine Equation, an equation whose solution(s) are in terms of integers.
Thus, we have that:
$\displaystyle 20R+16H+C=400$
$\displaystyle C=100-R-H$
Thus,
$\displaystyle 19R+15H=300$
Where $\displaystyle R,H$ must be integers.

One way to solve this is with continued fractions. Another way is with the Euclidean Algorithm, which I am going to use.
Express $\displaystyle \gcd (19,15)=19x+15y$
To do that use the Euclidean Algorithm,
$\displaystyle 19=1\times 15+4$
$\displaystyle 15=3\times 4+3$
$\displaystyle 4=1\times 3+1$
$\displaystyle 3=3\times 1+0$
Now work backward to get, (detailed steps omitted)
$\displaystyle 1=4\times 19-5\times 15$
Multiply by 300,
$\displaystyle 19(1200)+15(-1500)=300$
Is one integral solution.

By the theory of linear diophantine equations,
all solutions of $\displaystyle ax+by=c$ where $\displaystyle \gcd (a,b)=1$
must have the form $\displaystyle x=x_0+bt$ , $\displaystyle y=y_0-at$ where $\displaystyle x_0,y_0$ are particular solutions.

Thus, in your problem all solutions must have form,
$\displaystyle R=1200+15t$ and $\displaystyle H=-1500-19t$
You need $\displaystyle R,H>0$ because you want positive integral solutions,
thus, these two inequalities need to be satisfied,
$\displaystyle 1200+15t>0$ and $\displaystyle -1500-19t>$
From which we have that $\displaystyle -80<t <-(1500/19)\approx -78.9$
That occurs when $\displaystyle t=-79$ are the only positive integral solution thus,
$\displaystyle R=15$ and $\displaystyle H=1$ and $\displaystyle C=84$
Q.E.D.