1. ## 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?

2. 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.

3. 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.