DescriptionThe Frobenius coin/postage problem is a very classical in combinatorial and additive number theory. Given (an infinite amount) of coins (or stamps) of specified denominations what is the largest number/amount you cannot obtain using these coins? For example, given coins with values 3 and 5 you can only not obtain the values1,2,4,7
but then all! For coins of two denominations there exists an easy closed formula for the Frobenius number and the number of amounts which cannot not be obtained but that's it! For more denominations we only have bounds and asymptotic formulas. There are of course many variations for this problem, for example the postage stamp problem which limits the number of coins/stamps to be used. Another variation is to move the problem into higher dimensions, that is, given a number of vectors in n-space with non-negative integer coefficients which vectors and to consider the structure of all vectors obtained as non-negative integral linear combinations of the original ones. ResourcesThere are many sources, but for initial reading the wikipedia entriesPrerequisites
|