The Postage Stamp Problem: A Solution Combining Graph Theory, Number Theory, Algebra, Geometry, and Computer Science
April 28, 2008
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.
|Union College Math Department Home Page|
Comments to: firstname.lastname@example.org
Created automatically on: Thu Jul 19 22:47:06 EDT 2018