#### Title

On the Frobenius Coin-Exchange Problem

#### Document Type

Lecture

#### Department

Mathematics (CMC)

#### Publication Date

9-30-2009

#### Abstract

Suppose you have an infinite supply of coins of N different relatively prime denominations, *a*_{1}, *a*_{2}, … *a _{N}*. It is not difficult to show that there exists the maximum amount of change

*F*=

*F*(

*a*

_{1},

*a*

_{2}, …

*a*) which CANNOT be given with these coins, and any amount larger than F can be given. The Frobenius problem (FP) asks for an algorithm that on the input would take

_{N}*N*,

*a*

_{1},

*a*

_{2}, …

*a*and on the output return

_{N,}*F*. FP is known to be NP-complete, which in particular means that there can be no general formula for F, although a very simple such formula exists for

*N*= 2 (this goes back to J. Sylvester, 1884). On the other hand, for each fixed

*N*, FP is known to be in the P complexity class. There is a variety of upper and lower bounds for

*F*in the literature, and recently some work has been done on trying to understand the behavior of

*F*“on the average.” I will present an introduction to this exciting problem, which is extensively studied in number theory, complexity theory, combinatorics, and probability, and explores the interplay between these areas.

#### Rights Information

© 2009 Lenny Fukshansky

#### Terms of Use & License Information

#### Recommended Citation

Fukshansky, Lenny. "On the Frobenius Coin-Exchange Problem." Graduate Seminar, California State University Channel Islands, Camarillo, California. 30 September 2009.

## Comments

This lecture was given during the Graduate Seminar at California State University Channel Islands in Camarillo, CA on 30 September 2009.