My Mathematical Journey: The Stamp Problem
By: David Bressoud @dbressoud
David Bressoud is DeWitt Wallace Professor Emeritus at Macalester College and former Director of the Conference Board of the Mathematical Sciences
For the second in this series of reminiscences about my mathematical journey, I have chosen to write about a rich problem that I have used for years in Macalester’s course in discrete mathematics.
Problem: Given an unlimited supply of a cent stamps and b cent stamps, what is the largest amount that cannot be made?
Until the very end of my time at Macalester, Discrete Mathematics was a first-year course. Potential majors were encouraged to take it in their first semester, especially if they were not certain where they should start in the calculus sequence. Discrete Mathematics was an introduction to ideas in mathematics these students may not have seen before, and it was structured to begin building their ability to engage with proofs.
This has always been a challenging course for many students. In my last year of teaching, it was reclassified as a sophomore level course and, unfortunately, it has ceased to be required for mathematics majors.
Albert (Tommy) Wilansky (1921–2017)
When I taught this course, I built it around three projects, each with a low bar to entry, but with great opportunities to pursue more challenging questions. The first project involved the stamp problem: Given an unlimited supply of a cent stamps and b cent stamps, what is the largest amount that cannot be made and how many amounts cannot be made? It is a question that is personally meaningful.
I was introduced to this problem in the summer of 1967, between my junior and senior years of high school. I was fortunate enough to be accepted to a summer enrichment program at Lehigh University run by Albert (Tommy) Wilansky. As an aside, in his later years Tommy lived in the same retirement community as my father, so I had opportunities to get to know him personally. He was a Newfoundlander who was surprised to find himself accepted to Brown for graduate school, then spent his career at Lehigh. He told me he did not know why he was called Tommy. That was just was just the name his family always used.
The two-week Lehigh program introduced us to a variety of problems in number theory and combinatorics. In the second week, we were each given our own problem to work on. I was assigned the stamp problem. It did not take me long to determine that the answer is ab – a – b, provided a and b are relatively prime. But then I was challenged to prove this, and that completely stymied me.
As an undergraduate at Swarthmore College, I never took a course in number theory or combinatorics, but when I entered graduate school at Temple University, my undergraduate advisor, Dave Rosen, recommended that I work with Emil Grosswald, probably the most important advice I have ever received. Grosswald’s research was in analytic number theory, so when I asked to work with him, my first task was to learn some basic number theory.
I started with Niven and Zuckerman, where I ran across the stamp problem and realized that modular arithmetic provided the right tool for proving the result I had discovered some seven years earlier. When I got to Macalester and began teaching our discrete mathematics course, the stamp problem provided a wonderful way of providing “intellectual need” for studying modular arithmetic.
The term intellectual need was introduced by Guershon Harel. It refers to a problematic situation that necessitates the development of a particular piece of mathematics. Harel illustrates this with reference to A Radical Approach to Real Analysis in which I draw on Fourier’s solution of Laplace’s equation and the problems it created for the then current understandings of infinite series. The intellectual need for a better comprehension of infinite series would give rise to the real analysis of the 19th century. The emphasis is on the necessity of the piece of mathematics. If you really want students to be engaged, you have to pique their natural curiosity.
I have never been satisfied with the introduction of modular arithmetic as “clock arithmetic”: what happens when you add nine hours to 7:00 pm? The problem is just not sufficiently engaging. In contrast, students find the stamp problem intriguing and challenging. By the time they are done they comprehend how modular arithmetic works
If you are interested in the actual worksheet I give to my students, you can CLICK HERE for a pdf. CLICK HERE for the LaTeX code.
I give the students a lot of scaffolding for this problem. I start by asking about the largest amount that cannot be made with 5 and 8 cent stamps. To help them get going, I present them with the non-negative integers arranged into five columns. The eventual goal is for students to identify these with the five congruence classes modulo 5. After working with several other pairs of stamp values, the students are asked when there will be a largest amount that cannot be made. Having just worked with 4 and 6 cent stamps, there are always one or two groups who think that the necessary condition is that one value is odd and the other even. When I then ask them to look at 6 and 9 cent stamps, they quickly recognize that the values must be relatively prime.
Part (6) on the back page gets to the heart of the project, where they are asked to prove their result. Again, I include a lot of scaffolding that I have found is needed since this is often the first real proof these students have done.
Part (7) entered fairly late in my use of this project. It started as an extra credit problem, simply asking for the number of amounts that cannot be made, together with a proof. When I first posed this, only one student in the class was successful. There are various possible approaches—including a bijective argument—that explain why exactly half the integers from 1 through (a–1)(b–1) cannot be made. I decided to scaffold a direct proof that I rather like because it makes use of the floor function, requires an understanding that each column corresponds to exactly one of the remainders modulo a, and makes use of the formula for the sum of the first a–1 integers.
I have included my instructions for the teams and for scoring the reports. CLICK HERE for the rubric that I use. I like to work with teams of four. For this first assignment, I put each team into two writing pairs. While each pair is graded on their report, I encourage the pairs within a given team to share their reports. After the reports are handed in, I spend a good deal of time marking up problems in the argument or exposition. There is no grade on the first submission. Students then have a week to rewrite the report and get it back to me. Grading the first draft is time-consuming, but with the class capped at 32 students, this is do-able, and the final reports usually go pretty quickly.
There are three projects over the course of the semester. I choose the teams and the writing pairs, trying to make sure that no one person is likely to dominate their team, and I change the make-up each time. I have learned not to worry if some teams have to struggle more than others. All eventually make it, and productive struggle can be very beneficial. After this first project, each person is responsible for his or her own project report, though again I encourage them to share their drafts with the other members of their team. By the second report, enough students understand how to write a good report that scoring the first draft is not nearly as painful as on the first project.
The Stamp Problem also includes an appendix where I address one of the issues about which I care: student misuse of the terms modulus, modular, and modulo. It is like fingernails on a black board when I hear a student use “modulo” as a noun or adjective. I point out that we are learning a new preposition, and how often does that happen?
I have yet to meet a student who is not intrigued by the stamp problem. It builds an understanding that any integer in a given column can stand in for the entire column and that when we speak of, say, 3 modulo 5, we are not talking about a number but an entire column of numbers. Part (7) drives home the point that if a is relatively prime to b, then the first a multiples of b lie in distinct residue classes.
Finally, extending these columns into the negative integers and allowing negative numbers of stamps, students see that they have a proof that if a and b are relatively prime, then every integer is a linear combination of a and b. We are well into elementary number theory.
Download the list of all past Launchings columns, dating back to 2005, with links to each column.