NTIC A First Problem

Section 1.1 A First Problem

Let's start! Suppose you have lots of left-over postage stamps² that are of just a few different denominations. It could be fun to see what amounts you could make from them.

Perhaps because you only use email or texting now; too bad for you!

🔗

To be concrete, let's assume first that all your stamps are numbered 2¢ and 3¢. Here are two questions we could ask. They are mathematically equivalent, but might take your exploration in two very different directions!

🔗

Question 1.1.1.

Suppose you only have stamps (or some other currency-like item) available in 2¢ and 3¢ amounts.

Which denominations of postage can you get by combining just these two kinds of stamps?
Which denominations can you not get with just these two kinds?

Once you've thought about that, try the same problem with 2¢ and 4¢ stamps. What is the same, what is different?

🔗

Now let's get to a nontrivial case; what about with 3¢ and 4¢ stamps? In this case, after some experimentation, it looks like only 1, 2, and 5 are not possible, so anything six or above is possible. We call this number (in this case, 6) the conductor of the set

{3, 4} .

🔗

What we are really asking, as might be clear by now, is which positive integers

n

are impossible (or possible) to write in the form

n = 3 x + 4 y,

for nonnegative integers

x

and

y .

This is also sometimes called the Frobenius³ or coin problem.

For a very full discussion, see [E.7.20], but not until after you have started the next chapter of this book!

🔗

Continue trying this with different small pairs of positive integers (see also Exercise 1.4.5–Exercise 1.4.7). For each pair, pay attention to two things:

What is the conductor of the pair? (You might want to ask whether there is a conductor!)
How many numbers lower than the conductor cannot be written in this way as a sum with this pair?