The Frobenius problem (or Chicken McNugget problem) is, given coins worth units, to find the largest such that no combination of the coins is worth exactly units. This value is called the Frobenius number of the .
The problem comes up in many real-world contexts, and despite being quite elementary, its general solution is not known. The solution is completely understood for , but even for , there is no general closed-form formula for the Frobenius number.
Suppose that a popular fast-food restaurant sells its chicken nuggets in sizes of 6, 9, and 20. Customers who want exactly 21 nuggets can buy two 6-packs and one 9-pack, but customers who want exactly 22 nuggets are out of luck. It may seem somewhat plausible that larger orders will be more likely to be fillable, since there are more potential combinations to try. The Frobenius problem in this case asks for the largest number of nuggets that cannot be ordered.
Let be positive integers. Define Note that the nonnegativity of the is what makes the problem interesting; if the are allowed to be arbitrary integers, then is just the set of multiples of the greatest common divisor of the by Bezout's identity.
If and , then does not contain . Of course but these are not nonnegative integer linear combinations of and . American football fans may recognize as a fairly rare team score, since the vast majority of points that are scored in a game come in denominations of and
Here are four potential questions, in increasing order of difficulty.
- Can any sufficiently large positive integer be represented as a nonnegative integer linear combination of the That is, does the Frobenius number exist?
- If 1 is true, how large is sufficiently large? (That is, what is the Frobenius number?)
- If 1 is true, how many integers cannot be represented?
- Given and is there a formula for the number of representations of as a nonnegative integer linear combination of the
The answers to these questions are all known for , but for only partial answers are known (for 2~4 above).
One necessary condition for question 1 above to hold is that the greatest common divisor of the should be , since if the are all divisible by then so is any integer linear combination of them. In fact, this condition turns out to be sufficient as well.
If , then every sufficiently large positive integer can be represented as a nonnegative integer linear combination of the .
If the result is true for , then the general case can be proved inductively. For instance, suppose exists, and suppose exists. Then every sufficiently large positive integer can be written as a nonnegative integer linear combination of and . But can be written as a nonnegative integer linear combination of and , and substituting that into the original linear combination gives an expression for every sufficiently large positive integer as a nonnegative integer linear combination of . This technique extends to any value of .
The case requires a key lemma that answers questions 1 and 2 simultaneously.
Lemma: Suppose are relatively prime. Then .
Proof: First, suppose the number can be written as
for nonnegative integers and . Then taking this equation modulo gives , implying since has a multiplicative inverse modulo Similarly, , implying Since and are nonnegative integers, this gives
a contradiction. So .
Now, consider any number By Bézout's Identity, there exist integers and such that Multiplying both sides by gives integers and such that A result from the wiki on linear Diophantine equations describes all solutions to the equation : for some integer .
By the division algorithm, we can choose such that . For this value of , implies Now, since and this implies , or This gives nonnegative integers and such that
This shows that . So .
A shop sells cookies in packages of two sizes, cookies and cookies. What is the maximum number of cookies that cannot be expressed as a nonnegative combination of these package sizes?
In this problem, and and . By the lemma above, the maximum number of cookies that cannot be expressed as a combination of these sizes is the Frobenius number
In general, there is no polynomial closed formula for for and, computationally, the Frobenius problem is NP-hard. However, there are polynomial-time algorithms for finding that are exponential in , and there are known upper and lower bounds on the Frobenius number for .
Three rectangles of dimensions and with and coprime integers are available as the bases on which to build cuboid towers of any heights. The tower on each base will be built with cubic blocks. For example, if we want to make cuboids of heights 1, 2, 3 for the first, second, and third bases, respectively, the total number of the unit blocks used will be But it is not required to use all three of the bases in building cuboid towers: you may use only one or two of the three bases.
You try all combinations of the bases and heights and find that, given 47 unit blocks, you can never build cuboid towers as described above, but that there is always a way to do the job if there are more than 47 blocks.
What is ?
Note that the key technique used in the solution to the problem above is this: if there is a run of consecutive representable numbers, then every larger number is also representable, by adding an appropriate multiple of to one of the representations.
I have an unlimited supply of 17-cent, 18-cent, and 19-cent stamps. I'd like to put exactly cents' worth of postage on an envelope, but no matter which combination of stamps I try, I am unable to accomplish this.
What is the largest possible value of ?
Bonus 1: Generalize to any three consecutive integers.
Bonus 2: Generalize to any three-term arithmetic progression.
Bonus 3: Generalize to any arithmetic progression.
If and are coprime, exactly half of the integers between and are representable. So there are non-representable positive integers.
The second sentence follows from the first (and the lemma above). To see the first, for any integer , consider the pair of nonnegative integers . The goal is to show that exactly one of the numbers in this pair is representable.
First, the sum of representable numbers is representable, but is not representable. So at most one of the numbers in the pair is representable.
Now, consider any number and suppose is not representable. Follow the same lines as the proof of the lemma above: by Bézout's Identity, there exist integers and such that and multiplying both sides by gives integers and such that As above, by linear Diophantine equations, all solutions to the equation can be written as for an integer. By the division algorithm, we can choose such that . Since is not representable, for this value of , . Then
where and . Therefore, is representable. This shows exactly one of the pair is representable, as desired.
This answers question 3 above (question of which integers cannot be represented) for .
For question 4 above (question of how many representations), there is a beautiful result due to Popoviciu that gives a formula for the number of representations of an integer. The proof uses generating functions and is omitted.
Let and be coprime positive integers, and find integers and such that mod and mod . Then the number of representations of a positive integer as a nonnegative linear combination of and is
Here denotes the fractional part of .
In how many ways can be represented as a nonnegative integer linear combination of and ?
The answer is a little less than . The exact formula requires us to find , and compute
In fact, it is not hard to find the representations: .