Results 1 to 3 of 3

Thread: Linear Algebra

  1. #1
    Junior Member
    Joined
    Nov 2005
    Posts
    31

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    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.
    Last edited by CaptainBlack; Jan 31st 2006 at 07:10 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    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.
    Last edited by ThePerfectHacker; Jan 31st 2006 at 01:06 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: Aug 1st 2011, 10:00 PM
  2. Basic Linear Algebra - Linear Transformations Help
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: Dec 7th 2010, 03:59 PM
  3. Replies: 2
    Last Post: Dec 6th 2010, 03:03 PM
  4. Replies: 7
    Last Post: Aug 30th 2009, 10:03 AM
  5. Replies: 3
    Last Post: Jun 2nd 2007, 10:08 AM

Search Tags


/mathhelpforum @mathhelpforum