Linear Algebra (Abstract impossible combination question)

[xdanizzlex]

Homework Statement

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.

Homework 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)
ex:
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.

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?

 

[HallsofIvy]

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?

 

[xdanizzlex]

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.

 

[soandos]

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.
also,
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.

 

[HallsofIvy]

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.

Well, didn't it occur to you that if the difference 22A/77- 21A/77\ge 1 then there MUST be an integer between them? Multiplying by 77, 22A- 21A= A\ge 77. 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.