Thread: 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?

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:


,

Rearranging to solve these for and setting the results equal:


,

gives:

.

Rearranging again gives:

.

Then:

,

but the LHS is divisible by , so is divisible by (as is prime).

But , so must be , then: , and .

QED.

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:


Thus,

Where 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
To do that use the Euclidean Algorithm,




Now work backward to get, (detailed steps omitted)

Multiply by 300,

Is one integral solution.

By the theory of linear diophantine equations,
all solutions of where
must have the form , where are particular solutions.

Thus, in your problem all solutions must have form,
and
You need because you want positive integral solutions,
thus, these two inequalities need to be satisfied,
and
From which we have that
That occurs when are the only positive integral solution thus,
and and
Q.E.D.