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 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
    9
    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 01:06 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

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

Search Tags


/mathhelpforum @mathhelpforum