What is s?

The Problem

The Otehaihai Post Office has two denominations of stamps. It has 3c stamps and stamps of some other value. It can make up any amount of postage from 24c onwards. It can’t make up 23c. What is the value of the other denomination?

 Teaching sequence

1. Pose the problem to the class. Discuss how they might solve the problem. Make sure that they understand that there are two key ideas here. The value of s has to be such that it produces 24, 25 and 26 but that it doesn’t produce 23.
2. Let the students work on the problem with a partner.
3. Then if the students are stuck you might suggest that they experiment with various values of s (and keep a record of their work as it will be useful later).
4. Share students’ solutions. Note any different methods of solution.
5. In the Extension, the students will probably need the following hints: (i) experiment with different values of s to get some ideas; and (ii) in the proof, use s = 3k + 1 and 3k + 2 (why?). But help them to see the need for (ii) by using several values of s in (i).
6. Get the students to write up what they have discovered.

Extension to the problem

If the Post Office had 3c and sc stamps, and every amount of postage could be made from a given point on, what is the smallest value of that given point?

Solution

Let s be the value of the unknown denomination. The simplest way to do this problem is to guess and check. So you might guess s = 10. But 23 = 3 + 2 x 10. Guess s = 11. But experiments will show that that guess is incorrect too. By gradually increasing the value of s you could discover that s is probably 13. Then, you need to justify that 13 does not give 23 but that it does give everything from 24 onwards. (It’s necessary to do this otherwise we can’t be sure that s = 13 fits all the data of the original problem.)

A nicer method than the one above, is to know that in general the lowest ‘point’ is 2(s – 1). This can then be equated to 24 and the linear equation solved to give s = 13. (However, we don’t justify this lowest point until the Extension.)

Solution to the extension

With 3 and s we can make 2(s – 1) and everything from then on but we can’t make 2(s – 1) – 1. The value of 2(s – 1) has to be guessed by experimenting with various values of s. But we have to be careful to remember that 3 and s have no factors in common (see 3c and 5c Stamps, Number, Level 3).

Proof: Using the proof method of 3c and 5c Stamps, we will need to show that we can get 2(s – 1), 2(s – 1) + 1, 2(s – 1) + 2. Then we need to show that we can’t get 2(s – 1) – 1.

2(s – 1). Now we have to get this as a linear combination of 3 and s. But with 2(s – 1) = 2s – 2, this isn’t obvious. Check with s = 5, 7, and a few other values to see if this gives us any insight. It does because it suggests that we should write s as either 3k + 1 or 3k + 2. (It can’t be 3k as 3 and s have no factors in common.)

If s = 3k + 1, then 2s – 2 = 6k + 2 – 2 = 6k = 3(2k). We can do this with only 3c stamps.

If s = 3k + 2, then 2s – 2 = 6k + 4 – 2 = 6k + 2 = 3k + 3k + 2 = 3k + s. We can do this with 3c and sc stamps.

2(s – 1) + 1
To do this we need to follow in the footsteps of 2(s – 1).

If s = 3k + 1, then 2(s – 1) + 1 = 2s – 1 = 6k + 2 – 1 = 6k + 1 = 3k + (3k + 1) = 3k + s.

If s = 3k + 2, then 2(s – 1) + 1 = 2s – 1 = 6k + 4 – 1 = 6k + 3 = 3(2k + 1).

2(s – 1) + 2
= 2s – 2 + 2 = 2s. So this is easy, we just use two sc stamps here.

But then there is the problem of why we can’t do 2(s – 1) – 1. How do we prove that something can’t happen? One way is to assume that it does and show that this leads to something that is clearly false. This implies that the original assumption had to be wrong. So let us assume that there exist numbers of stamps a and b such that 2(s – 1) – 1 = 3a + bs.

Rearranging we get 2s – bs = 3a + 3. So s(2 – b) = 3(a + 1). Now we know that s has no factors in common with 3. But 3 divides the right hand side of the equation, so 3 divides the left hand side. So 3 divides 2 – b. Since 2 – b has to be positive (because the right hand side is), 2 – b has to be 1. But 3 doesn’t divide 1 so we have our contradiction.