Results 1 to 14 of 14

Math Help - Too much money!!!!!!! Please help!

  1. #1
    Newbie
    Joined
    Apr 2006
    Posts
    3

    Too much money!!!!!!! Please help!

    In a country whose currency consists of $6 bills and $11 bills, the price of every item sold is a whole number of dollars that can be be paid (exactly) using these two types of bills. What is the largest whole number of dollars which could not be the price of an item sold in this country?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,903
    Thanks
    329
    Awards
    1
    Quote Originally Posted by Slipknotfanatic89
    In a country whose currency consists of $6 bills and $11 bills, the price of every item sold is a whole number of dollars that can be be paid (exactly) using these two types of bills. What is the largest whole number of dollars which could not be the price of an item sold in this country?
    There is no upper limit on the price. Any possible price in whole dollars will be of the form: $6*n + $11*m where n and m are non-negative integers. There are an infinite number of prices that don't fit this requirement.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by topsquark
    There is no upper limit on the price. Any possible price in whole dollars will be of the form: $6*n + $11*m where n and m are non-negative integers. There are an infinite number of prices that don't fit this requirement.

    -Dan
    Not so, when I get the chance I will post the proof that there is always
    a maximum price which cannot be made with bills of denominations $b1 and
    $b2 where b1 and b2 are co-prime.

    RonL
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Slipknotfanatic89
    In a country whose currency consists of $6 bills and $11 bills, the price of every item sold is a whole number of dollars that can be be paid (exactly) using these two types of bills. What is the largest whole number of dollars which could not be the price of an item sold in this country?
    This is not as clear as I would like and there is probably a more elegant way
    to do this, but here it is anyway:

    Consider a whole number of dollars \$N.

    Now consider

    <br />
R(k)=N-k.6,\ k \in \{0,\ \dots,\ 11 \}<br />

    Now as 11 and 6 are co-prime, for each
    r \in \{0,\ \dots,\ 11 \}:

    <br />
R(k) \equiv r \mod 11,\ \mbox{for some }k \in \{0,\ \dots,\ 11 \}<br />

    So there exists \rho and \kappa \ge 0 such that:

    <br />
N=\rho.11+\kappa.6<br />
,

    moreover if N \ge 11 \times 6, \rho \ge 0.

    Hence if N \ge \$ 66 it can be made up by a combination of
    \$ 11 and \$ 6 bills.

    Now trail and error show that \$65=1\times \$11+9\times \$6, but that there is no such representation for N = \$64.

    So \$64 is the largest whole number of dollars which could not be the price of an item sold in this country

    RonL
    Last edited by CaptainBlack; April 21st 2006 at 05:04 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,903
    Thanks
    329
    Awards
    1
    Huh! Well, I guess you DO learn something new every day! Sorry about that, Slipknotfanatic89!

    -Dan
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Dec 2005
    Posts
    117
    wow, CaptainBlack, you're good , i thought it was infinite too
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by SlipKnotfanatic89
    In a country whose currency consists of $6 bills and $11 bills, the price of every item sold is a whole number of dollars that can be be paid (exactly) using these two types of bills. What is the largest whole number of dollars which could not be the price of an item sold in this country?
    Mathematically what you are trying to find the smallest n such as you cannot find non-negative integers x,y such as,
    6x+11y=n.
    -----
    This problem is from number theory. It uses something called linear diophantine equation (Bezout's Identity):
    If ax+by=c and d|c where d=\gcd(a,b) then this diophantine equation has solutions.
    If x_0,y_0 is a solution pair, then all solutions and every solution (if and only if) are:
    \left\{ \begin{array}{c}x=x_0+\frac{b}{d}t\\y=y_0-\frac{a}{d}t \end{array} \right.
    -----
    Notice that,
    6(2)+11(-1)=1 multiply by n to get,
    6(2n)+11(-n)=n, by the theory of linear diophantine equations you have that all and every solution is,
    \left\{ \begin{array}{c}x=2n+11t\\ y=-n-6t \end{array} \right for an integer t.
    But you want whole numbers for x,y thus,
    x\geq 0 \mbox{ and }y\geq 0
    Thus,
    2n+11t\geq 0\mbox{ and }-n-6t\geq 0
    Solving these inequalites we find that t must satisfy,
    -\frac{2n}{11}\leq t\leq -\frac{n}{6}
    Placing a common denominator (and removing the negative),
    \frac{11n}{66}\leq -t\leq \frac{12n}{66}
    Thus,
    11n\leq k\leq 12n where k=-66t is also an integer.
    The only requirements that k must have is to be a multiple of 66.
    All the integers that satisfy this inequality are,
    S=\{11n,11n+1,11n+2,...,11n+(n-1),12n\}
    Thus, given this set we need to find the largest n such as there is no multiple of 66.
    In total we have n distinct integers in increasing order. Thus, if n\geq 66 then by the Pigeonhole Principle we have that there must be a multiple of 66.
    Instead of approaching this problem theoretically simply do trail and error beginning with n=65, soon we will see that n=49 contains no mutiples of 66.
    -----
    Wow two mistakes in a row first topsquark, CaptainBlack. Hope I am not the next one,
    64=6(7)+11(2).
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by ThePerfectHacker
    Wow two mistakes in a row first topsquark, CaptainBlack. Hope I am not the next one,
    64=6(7)+11(2).
    Must have been something wrong with my caluclator yesterday.
    It probably needs an oil change

    RonL
    Last edited by CaptainBlack; April 23rd 2006 at 12:34 AM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    My calculator is a turing machine.

    I use my computers calculator:
    C:\WINDOWS\system32\calc.exe
    it hs 34 digits.

    I was thinking of downloading a super advanced calculator with more than 100 digits.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by ThePerfectHacker
    My calculator is a turing machine.

    I use my computers calculator:
    C:\WINDOWS\system32\calc.exe
    it hs 34 digits.

    I was thinking of downloading a super advanced calculator with more than 100 digits.
    For arbitrary precision work I use a CAS, though I have been thinking
    about using UBASIC for some number theory calculations recently (it
    works with 2000+ digits).

    RonL
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Jun 2005
    Posts
    295
    Awards
    1
    This is Sylvester's Coin Problem, also known as the Frobenius Coin Problem. Sylvester showed that the largest sum that cannot be made using coins of values a and b (where a and b are coprime) is (a-1)(b-1)-1 = ab - a -b.

    There are articles in Wikipedia and MathWorld.

    In the specific case of coins of value 6 and 11, note that 50 can be made up as 4.11 + 1.6 and then 51=3.11+3.6, 52=2.11+5.6, 53 = 1.11 + 7.6, 54 = 0.11 + 9.6, 55=5.11 + 0.6, 56 = 4.11 + 2.6 and the pattern repeats with an interval of 6.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by rgep
    This is Sylvester's Coin Problem, also known as the Frobenius Coin Problem. Sylvester showed that the largest sum that cannot be made using coins of values a and b (where a and b are coprime) is (a-1)(b-1)-1 = ab - a -b.

    There are articles in Wikipedia and MathWorld.

    In the specific case of coins of value 6 and 11, note that 50 can be made up as 4.11 + 1.6 and then 51=3.11+3.6, 52=2.11+5.6, 53 = 1.11 + 7.6, 54 = 0.11 + 9.6, 55=5.11 + 0.6, 56 = 4.11 + 2.6 and the pattern repeats with an interval of 6.
    It looks interesting. I was able to demonstrate that n\geq ab (where a and b are co-prime) can always be expressed. But I was not able to demonstrate the second propstition, I just used trail and error.
    -----
    Does it generalize as if,
    \gcd(a_1,a_2,....a_n)=1
    Then, \prod^n_{k=1}a_k-\sum^n_{k=1}a_k
    Is the largest non expressable number?
    Last edited by ThePerfectHacker; April 23rd 2006 at 10:43 AM.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Apr 2006
    Posts
    3
    The largest number I have found thus far is 49 by 11(-1) + 6(10). I can't remember whose formula this follows, but it is the lagest number I have found that cannot be solved using 6 and 11
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Slipknotfanatic89
    The largest number I have found thus far is 49 by 11(-1) + 6(10). I can't remember whose formula this follows, but it is the lagest number I have found that cannot be solved using 6 and 11
    In the previous posts CaptainBlack and I give two different solutions to this problem (CaptainBlack was wrong because
    my calculator needs an oil change
    ). Then, rgep made another interesting post that this is a theorem. Anyways yes, the largest non-expressable number is 49. Notice that important fact that \gcd(6,11)=1 otherwise it is impossible.

    Let me explain let, \gcd(a,b)=d>1
    Then there are no integral solutions to the equation,
    ax+by=c where d\not |c because than the left hand side is divisible by d while the right hand side is not. But when the d=1 then it is possible because all numbers are divisible by one.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: January 5th 2011, 09:16 PM
  2. Money...
    Posted in the Math Puzzles Forum
    Replies: 3
    Last Post: August 12th 2009, 08:24 PM
  3. money
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 9th 2009, 04:31 PM
  4. money
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 11th 2007, 10:30 AM
  5. [SOLVED] money,money,money...
    Posted in the Statistics Forum
    Replies: 2
    Last Post: May 17th 2006, 04:44 AM

Search Tags


/mathhelpforum @mathhelpforum