## The Postage Stamp Problem: A Solution Combining Graph Theory, Number Theory, Algebra, Geometry, and Computer Science |

**Stan Wagon**

Macalester College

April 28, 2008

4:15 pm

Bailey Hall 207

Refreshments will be served in Bailey 204 at 4:00

A classic real-world problem is: How to make up a certain amount of postage using a given set of stamps. A modern variation is the Chicken McNugget problem: They are sold in packets of 6, 9, and 20. One can buy 46 of them, but one cannot buy 13. Which numbers are attainable? There is a largest non-attainable number. What is it? In the talk I will discuss this problem and variations, showing how many areas of mathematics come together to lead to a good algorithmic solution. Graph theory methods are the traditional way to solve it, but a new approach based on combining algebra and geometry is much more efficient.

For additional information, send e-mail to math@union.edu or call (518) 388-6246.

Union College Math Department Home PageComments to: math@union.edu Created automatically on: Tue Oct 23 08:20:10 EDT 2018 |