Linear Algebra

• Jan 31st 2006, 06: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, 06: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:

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

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

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

gives:

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

Rearranging again gives:

$300=19R+15H$.

Then:

$300-15H=19R$,

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

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

QED.
• Jan 31st 2006, 09: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:
$20R+16H+C=400$
$C=100-R-H$
Thus,
$19R+15H=300$
Where $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 $\gcd (19,15)=19x+15y$
To do that use the Euclidean Algorithm,
$19=1\times 15+4$
$15=3\times 4+3$
$4=1\times 3+1$
$3=3\times 1+0$
Now work backward to get, (detailed steps omitted)
$1=4\times 19-5\times 15$
Multiply by 300,
$19(1200)+15(-1500)=300$
Is one integral solution.

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

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