The Frobenius Problem and Its Generalizations

摘要

Let x_1, x_2, ... ,x_n be positive integers. It is well-known that every sufficiently large integer can be represented as a non-negative integer linear combination of the x_i if and only if gcd (x_1, x_2, ... ,x_n) = 1. The Frobenius problem is the following: given positive integers x_1, x_2, ... ,x_n with gcd(x_1, x_2, ... ,x_n) = 1, compute the largest integer not representable as a non-negative integer linear combination of the x_i. This largest integer is sometimes denoted g(x_1, ... ,x_n). As an example, consider the following problem that appears frequently in books of puzzles (e.g., [24]): The Chicken McNuggets Problem: At McDonald's, Chicken McNuggets are available in packs of either 6, 9, or 20 nuggets. What is the largest number of McNuggets that one cannot purchase?