Fall 2013 MTCA Workshop #2

Post date: Oct 24, 2013 3:20:05 AM

Postage Stamp Problems

Presented by

Zachary Miner

The University of Texas at Austin

October 23, 2012

Our challenge in this session was to see how many interesting problems we could pose starting with something as simple as postage stamps. Here are some of the questions we thought about:

1. If you only have 5 cent and 7 cent stamps and want to use exact postage, what are all the possible postage amounts you can make? What is the largest amount you can't make? What if you limit the number of 5 cent stamps? How will the answers to these questions change? What if you limit the number of 7 cent stamps? What are the postage amounts you can make in more than one way? Is there a largest postage amount that you can make in only one way?

2. Consider other denominations of stamps. If you have an n cent stamp and an m cent stamp, where n and m have no common factors, can you always make all possible postage amounts above some value? If so, what is this value? A conjecture was offered suggesting that the largest postage value that cannot be made from two such stamps is mn-m-n. For example, when n=5 and m=7, the largest postage that cannot be made up from 5 and 7 cent stamps is 23= (5)(7)-5-7. Can an argument be made that will explain why this always works, or can an example be found that shows that the conjecture is not true in general?