Which Amounts Can You Never Pay with 3s and 5s?

The first twenty

Here is the answer the widget gives, with one way to pay each amount.

Amount	One way to pay		Amount	One way to pay
1	can’t		11	3 + 3 + 5
2	can’t		12	3 + 3 + 3 + 3
3	3		13	3 + 5 + 5
4	can’t		14	3 + 3 + 3 + 5
5	5		15	5 + 5 + 5
6	3 + 3		16	3 + 3 + 5 + 5
7	can’t		17	3 + 3 + 3 + 3 + 5
8	3 + 5		18	3 + 5 + 5 + 5
9	3 + 3 + 3		19	3 + 3 + 3 + 5 + 5
10	5 + 5		20	5 + 5 + 5 + 5

How can you be sure that Rs 7 is impossible, and not just hard? Count the Rs 5 stamps. A letter of Rs 7 can carry no Rs 5 stamp, or one; two would already be Rs 10. With none, the Rs 3 stamps must make 7, but 7 isn’t a multiple of 3. With one, they must make 7 − 5 = 2, and 2 isn’t either. Nothing else is possible, so Rs 7 can’t be paid. Checking every case like this, one by one, is a proof. It is how the widget knows.

Three in a row

Now look at Rs 8, 9 and 10, the first three amounts in a row that can all be paid. Put one more Rs 3 stamp on each letter: 8 + 3 = 11, 9 + 3 = 12 and 10 + 3 = 13 can all be paid. Add another: 14, 15 and 16. And another: 17, 18 and 19.

Every amount from 8 on is one of these, a step of 3 at a time below each column. So once three amounts in a row can be paid, every amount after them can too. You never need to test Rs 1,000 by trying stamps: it is in the column under 10, so it is Rs 10 plus a lot of Rs 3 stamps. (Or 200 Rs 5 stamps; there are often many ways.)

Amounts in rows

Here is a better way to look at all the amounts at once. Write them in three rows: 0, 3, 6, 9… in the first row (the multiples of 3), then 1, 4, 7, 10… (those that leave 1 when divided by 3), then 2, 5, 8, 11… (those that leave 2). A step to the right in any row is one more Rs 3 stamp.

Look at the rows for Rs 3 and Rs 5:

• the first row starts at 0 (no stamps at all);
• the third row starts at 5, one Rs 5 stamp;
• the second row starts at 10, two Rs 5 stamps.

Once a row has started, everything to its right can be paid: just keep adding Rs 3 stamps. So the only amounts that can’t be paid are the ones to the left of each ring: 1, 4 and 7 in the second row, and 2 in the third. The last row to start, starts at 10. The amount just before it in its row, 10 − 3 = 7, is the largest you can’t pay.

Why every ring is made of Rs 5 stamps

Why is the first amount in each row always paid with Rs 5 stamps only? Suppose it used a Rs 3 stamp. Peel that stamp off: what is left is still paid with stamps, and it is one step to the left, in the same row. Then the ringed amount wasn’t the first in its row after all. So the first amount in a row never uses a Rs 3 stamp, and it must be 0, 5, 10, 15, 20…

And 0, 5 and 10 already fall in the three different rows. They leave 0, 2 and 1 when divided by 3. So every row has started by 10, and 10 is where the last row starts.

The rule for any two stamps

Try more pairs in the widget, and fill in a table like this one. (Try the first rows yourself before you look.)

Small stamp	Other stamp	Largest you can’t pay	How many you can’t pay
2	3	1	1
2	5	3	2
3	4	5	3
3	5	7	4
3	7	11	6
4	5	11	6
4	7	17	9
5	7	23	12
5	8	27	14

This is the coin problem: given coins (or stamps, or packets) of fixed sizes, which amounts can be made exactly, and what is the largest that can’t? The largest amount that can’t be made is called the Frobenius number, after the German mathematician Ferdinand Georg Frobenius, and for two stamps there is a rule for it:

$$\text{largest you can’t pay} = \text{small} \times \text{other} - \text{small} - \text{other}.$$

The rows show why. With a small stamp of Rs a there are a rows, and the rings are 0, b, 2b, … for the other stamp of Rs b. The last ring is (a − 1) of the b-stamps, (a − 1) × b. One step to its left, (a − 1) × b − a, is the largest amount you can’t pay. And

$$(a - 1) \times b - a = ab - b - a.$$

For Rs 3 and Rs 5: (3 − 1) × 5 − 3 = 10 − 3 = 7, and 3 × 5 − 3 − 5 = 7.

Why the rings land in different rows

There is one gap left in the argument. Why do the rings 0, b, 2b, …, (a − 1)b always land in different rows? If they didn’t, two rings would share a row and some row would have no ring among them.

Suppose two of them did share a row, say 8 and 24 for Rs 5 and Rs 8 (they don’t, but suppose). Then their difference, 24 − 8 = 16, would be a whole number of steps in the row, a multiple of 5. It would also be a multiple of 8, since both rings are. So it would be a common multiple of 5 and 8, and smaller than 5 × 8 = 40. But the lowest common multiple of 5 and 8 is 40 (you find LCMs in Grade 7), because 5 and 8 share no factor except 1. So no two rings can share a row.

That is also where the rule needs its one condition: the two stamps must have no common factor except 1, as 3 and 5 do.

Stamps with a common factor

When the two stamps share a factor, say both are multiples of 2, or of 3, then every amount you can pay is a multiple of it too, and all the others are impossible for ever. The question “what is the largest?” only has an answer when the stamps share no factor except 1.

Three stamps

With three kinds of stamps, no simple rule like this one is known. But the idea of the rows still works.

In Britain, chicken nuggets were sold in boxes of 6, 9 and 20. Which numbers of nuggets can’t you buy? Here they are, all 22 of them:

1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37 and 43.

To see that every number above 43 can be bought, find six in a row, since the smallest box holds 6:

Nuggets	Boxes
44	6 + 9 + 9 + 20
45	9 + 9 + 9 + 9 + 9
46	6 + 20 + 20
47	9 + 9 + 9 + 20
48	6 + 6 + 9 + 9 + 9 + 9
49	9 + 20 + 20

Add a box of 6 to each, again and again, and every number from 44 on is covered. And 43 is impossible: with no box of 20 you need 43 from boxes of 6 and 9, but those always make a multiple of 3 and 43 isn’t; with one box of 20 you need 23, again not a multiple of 3; with two you need 3, a multiple of 3 but smaller than any box. Three boxes of 20 would be 60, too many.

The table had a second column: with Rs 3 and Rs 5 stamps, 4 amounts can’t be paid, and the amounts from 0 to 7 are 8 in all. Exactly half. With Rs 5 and Rs 8: 14 can’t be paid, out of the 28 amounts from 0 to 27. Half again. That is no accident.

Pair each amount from 0 to 7 with the amount that adds up with it to 7:

Amount	Can you pay it?	Its partner	Can you pay it?
0	yes (no stamps)	7	no
1	no	6	yes, 3 + 3
2	no	5	yes, 5
3	yes, 3	4	no

In every pair, exactly one can be paid. So half the amounts from 0 to 7 can be paid and half can’t.

Why can’t both in a pair be paid? Because the two add up to 7. If you could pay both, you could put both lots of stamps on one letter and pay 7, which is impossible.

Why can’t both be impossible? Here is a way to see it with change. Suppose your aunt also gives Rs 5 stamps back as change. Then every amount can be paid: Rs 1 is two Rs 3 stamps with one Rs 5 stamp given back (6 − 5 = 1), Rs 4 is three Rs 3 stamps with one Rs 5 back (9 − 5 = 4). Now 7 itself is four Rs 3 stamps with one Rs 5 back: 12 − 5 = 7.

You never need more than four Rs 3 stamps: five of them (Rs 15) can be swapped for three Rs 5 stamps. So write every amount with four Rs 3 stamps or fewer, and some Rs 5 stamps either stuck on or given back. An amount that can’t be paid without change must then get at least one Rs 5 stamp back.

Take one, like Rs 4: three Rs 3 stamps, one Rs 5 back. Its partner, 7 − 4, is “four 3s, one 5 back” take away “three 3s, one 5 back”: that is one Rs 3 stamp and no Rs 5 stamps. Rs 3, paid without change. Or Rs 2: four Rs 3 stamps and two Rs 5 back (12 − 10 = 2). Its partner, 7 − 2, is no Rs 3 stamps and one Rs 5 stamp: Rs 5. Every time, the partner gets the Rs 3 stamps the amount didn’t use (out of four), and one Rs 5 stamp fewer than the amount got back, now stuck on the letter instead of given back. Neither number is ever below zero, so the partner can always be paid without change.

The same pairing works for any two stamps with no common factor. That is why the number of amounts you can’t pay is half of (a − 1) × (b − 1): for Rs 3 and Rs 5, 2 × 4 ÷ 2 = 4.

• Can You Buy 100 Birds with 100 Coins? (Grades 9–12) Equations to be solved in whole numbers, Aryabhata’s kuttaka, and this topic’s rule proved with algebra.
• Why Do the Divisibility Tests Work? Remainders, the idea behind the rows of this topic.
• What Day of the Week Will Your 100th Birthday Be? More remainders, this time by 7, on the calendar.
• How Does a Magic Square Work? Another whole-number puzzle: rows, columns and diagonals that all add to the same number.
• How Many Eggs Were in the Basket? (Grades 9–12) Counting in twos, threes and fours, and an old puzzle about remainders.