Results 1 to 3 of 3

Math Help - 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
    4
    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.
    Last edited by CaptainBlack; January 31st 2006 at 08: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:
    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<t <-(1500/19)\approx -78.9
    That occurs when t=-79 are the only positive integral solution thus,
    R=15 and H=1 and C=84
    Q.E.D.
    Last edited by ThePerfectHacker; January 31st 2006 at 02:06 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

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

Search Tags


/mathhelpforum @mathhelpforum