Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Linear Algebra (Abstract impossible combination question)

  1. Jan 14, 2009 #1
    1. The problem statement, all variables and given/known data
    Chicken nuggets are only sold in baskets of either 7 or 11 nuggets. What is the largest
    number of nuggets that is impossible to order exactly? You must prove that your answer
    is correct.

    2. Relevant equations
    Not sure what equations could be used, but I guess 7(x1) + 11(x2) = (A) is what we're technically trying to solve and we're trying to get a number (A) that can't be achieved when you plug in any combinations of whole numbers for (x1) and (x2)
    if (A)=43, a solution could be (x1)=3 and (x2)=2
    if (A)= 23, there can be no combinations of (x1) and (x2) that will fulfill the equation

    What I need to find is the largest (A) where there will be no combinations, and i've been able to find some like 52, 59, 94, but I can't seem to find the largest one because I keep finding more and more.

    3. The attempt at a solution
    I'm not sure how to approach this... it's been the first week of my linear algebra course and we've learned some things on matrices but I'm not sure how I could apply it to this problem. I've written out so many combinations of the sums of multiples of 7's and 11's and I am just stumped. I can find values of (A) where there can't be any whole numbers for (x1) and (x2), but how can I be sure that it's the largest amount?
  2. jcsd
  3. Jan 15, 2009 #2


    User Avatar
    Science Advisor

    So you want to find A such that 7n+ 11m= A is impossible for any positive integers n and m. I notice that 2(11)- 3(7)= 1 or that 7(-3)+ 11(2)= 1 Multiplying by A, 7(-3A)+ 11(2A)= A. So n= -3A, m= 2A is a solution for all A.

    But, of course, that is not a valid solution for this problem- n and m must both be non-negative for this to make sense. But it is not to difficult to see that n= -3A+ 11k, m= 2A- 7k also satisfies that equation of any k: 7(-3A+ 11k)+ 11(2A- 7k)= -21A+ 77k+ 22A- 77k= A because the k terms cancel. Now we must have -3A+ 11k> 0, which gives k> 3A/11 and 2A- 7k> 0 which gives 2A/7> k: 3A/11< k< 2A/7. There will be a solution to this problem if and only if there is an integer between 3A/11 and 2A/7. What is the largest A such that there is NOT an integer between 3A/11 and 2A/7?
  4. Jan 15, 2009 #3
    The steps you laid out were just a tad bit confusing, but I do get what you're saying: What is the largest A such that there is NOT an integer between 3A/11 and 2A/7?

    The thing is I don't know how to solve that haha. To make it easier to see, you can put them in common denominators and you will want to find a number between 21A/77 and 22A/77, and the thing is, how will I ever know that it's the LARGEST one? It can't just be guess and check... ugh. But thanks for the help.
  5. Jan 15, 2009 #4
    i think this is simpler, but i am not sure it works.
    given that everything is given in terms of 7 and 11, all multiples of these numbers can be had.
    7+11==18, so everything that 18+7x can be had.
    so can 2*11+7x, 3*11+7x, ... till 7*11+7x, where they start to repeat.
    you have every multiple of 7 greater than 7
    you have four more than every multiple of seven greater than 18
    you have one more than every multiple of seven greater than 29
    you have five more than every multiple of seven greater than 40
    you have two more than every multiple of seven greater than 51
    you have six more than every multiple of seven greater than 62
    you have three more than every multiple of seven greater than 73

    (you could have seen that 0*11+7, 1*11+7, 2*11+7... would have the last different remainder when divided 7 at 6*11+7, or after the seventh term, one for every possible remainder 0->6)
    then, you look for the greatest number that is three more than a multiple 7 less than 73.

    I do not know any linear algebra, but this sounds more like number theory to me.
    I believe that the number that you are looking for is called the Frobenius Number for a given linear system.
    Last edited: Jan 15, 2009
  6. Jan 16, 2009 #5


    User Avatar
    Science Advisor

    Well, didn't it occur to you that if the difference [itex]22A/77- 21A/77\ge 1[/itex] then there MUST be an integer between them? Multiplying by 77, [itex]22A- 21A= A\ge 77[/itex]. That is, any A larger than or equal to 77 can be written as a combination of 7 and 11. The largest A that cannot must be less than 77. Now you can "check" but you certainly don't need to "guess"
    A 21A/77 22A/7
    76 20.7 21.7 so there is an integer between them.
    75 20.45 21.4 so there is an integer between them.
    etc. At least now you know there IS a largest A and you only have to check at most 76 numbers. Don't be afraid to do a little work.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook