Coin Problem - Statement

Statement

In mathematical terms the problem can be stated:

Given positive integers a₁, a₂, ..., a_n such that gcd(a₁, a₂, ..., a_n) = 1, find the largest integer that cannot be expressed as an integer conical combination of these numbers, i.e., as a sum

k₁a₁ + k₂a₂ + ··· + k_na_n,

where k₁, k₂, ..., k_n are non-negative integers.

This largest integer is called the Frobenius number of the set { a₁, a₂, ..., a_n }, and is usually denoted by g(a₁, a₂, ..., a_n).

The requirement that the greatest common divisor (GCD) equal 1 is necessary in order for the Frobenius number to exist. If the GCD were not 1, every integer that is not a multiple of the GCD would be inexpressible as a linear, let alone conical, combination of the set, and therefore there would not be a largest such number. For example, if you had two types of coins valued at 4 cents and 6 cents, the GCD would equal 2, and there would be no way to combine any number of such coins to produce a sum which was an odd number. On the other hand, whenever the GCD equals 1, the set of integers that cannot be expressed as a conical combination of { a₁, a₂, ..., a_n } is bounded according to Schur's theorem, and therefore the Frobenius number exists.