On the Frobenius Coin-Exchange Problem

Authors

Lenny Fukshansky, Claremont McKenna CollegeFollow

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₁, a₂, … a_N. It is not difficult to show that there exists the maximum amount of change F = F(a₁, a₂, … a_N) 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, a₁, a₂, … a_N, and on the output return 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.

Comments

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

Rights Information

© 2009 Lenny Fukshansky

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Recommended Citation

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