Coin Total Puzzles: Largest Unpayable Total and Fewest Tokens

To solve a coin total puzzle with two token values, sort the totals into columns by their remainder when you divide by the smaller value, then find the first total you can pay in each column. Every total further down a column is payable too, so the largest total you cannot pay is one smaller-token step below the latest of those first payable totals, and the fewest tokens come from using as many of the larger token as the remainder allows.

That is the whole method. This guide explains it in plain steps, works through a full example with tokens of value 4 and 7, compares several token pairs in a table, and ends with a practice puzzle and its answer.

What is a coin total puzzle?

You have as many tokens as you like of two fixed values, such as 3 and 5. You may use any number of each, including none at all. A total is payable when some mix of tokens adds up to it exactly, with nothing left over.

Three questions come up again and again:

• Which totals can you pay?
• What is the largest total you cannot pay?
• What is the fewest number of tokens that pays a given total?

Mathematicians have a name for the first question. A paper published on 6 June 2012 calls a whole number representable by a list of values when it equals a sum of those values, each used some whole number of times, zero included ^[1]. The same paper explains that this amounts to asking whether a sum can be paid exactly with coins of those values, which is why the question is often called the coin exchange problem ^[1].

Which totals can tokens of 3 and 5 pay?

Start small and simply list. With tokens of value 3 and 5, the first totals look like this:

Only four totals fail: 1, 2, 4 and 7. From 8 onwards everything works, and the reason is simple. Once 8, 9 and 10 are payable, add one more 3 token to each and you reach 11, 12 and 13. Add another and you reach 14, 15 and 16, and so on with no end.

That gives a handy stopping rule. When you meet a run of payable totals as long as the smaller token value, you can stop listing, because every later total is covered.

How does the ladder method work?

Listing is fine for small tokens, but it gets slow. The ladder method does the same job in a tidy table. Here are the steps:

1. Draw the columns. Make one column for each possible remainder when you divide by the smaller token. For a smaller token of 4, the remainders are 0, 1, 2 and 3, so you draw four columns.
2. Fill the columns. Write the totals in order down each column, so each column climbs by the smaller token value.
3. Find the first payable total in each column. In the column for remainder 0, it is the smaller token itself. In every other column, it is a multiple of the larger token, because only the larger token can move a total into a new column.
4. Shade everything below it. Each total under a payable one is just one more small token, so it is payable too.
5. Read the gaps. Every total above the first payable one in its column is a gap. The largest gap of all is the latest first payable total minus the smaller token.

The method turns a long hunt into a short one. You only ever look for one number per column.

How do you find the largest total you cannot pay?

Here is an original puzzle. You have tokens of value 4 and 7. What is the largest total you cannot pay, and how many totals can you not pay in all? Try it before reading on.

Step 1: draw four columns. The smaller token is 4, so the columns hold the remainders 0, 1, 2 and 3.

Step 2: find the first payable total in each column. The column for remainder 0 starts at 4. For the other columns, list multiples of 7. The total 7 has remainder 3, the total 14 has remainder 2, and the total 21 has remainder 1. Each of these lands in a new column, so they are the first payable totals there.

Step 3: fill in the ladder. Write yes for payable and no for a gap.

Step 4: read the answer. The latest first payable total is 21, in the column for remainder 1. One step of 4 below it, 17, is the largest gap. So the largest total you cannot pay is 17.

Step 5: count the gaps. The column for remainder 1 has five: 1, 5, 9, 13 and 17. The column for remainder 2 has three: 2, 6 and 10. The column for remainder 3 has one: 3. That makes nine totals you cannot pay.

Check the answer. For 17, take away 7 to leave 10, or take away 14 to leave 3. Neither 17, 10 nor 3 is a multiple of 4, so 17 really cannot be paid. Then check the four totals after it: 18 is 4 + 7 + 7, 19 is 4 + 4 + 4 + 7, 20 is five 4 tokens, and 21 is three 7 tokens. Four payable totals in a row, with 4 as the smaller token, means nothing after 17 is a gap.

How do different token pairs compare?

The same ladder works for any pair of values with no common factor. Here are some results, each one checked by a computer search through every total:

Look at the first five rows. In each of them, the largest gap equals the product of the two values minus both values. For 4 and 7, that is 28 minus 4 minus 7, which leaves 17. Use it as a quick cross-check on your ladder, not as a replacement for it.

The last row is different. Tokens of 4 and 6 are both even, so no mix of them can ever reach an odd total. When the two values share a common factor, the gaps never stop, and the puzzle has no largest unpayable total.

How do you pay a total with the fewest tokens?

The natural plan is to grab as many large tokens as you can. That plan can fail. Try paying 31 with tokens of 3 and 5.

• Six 5 tokens make 30, which leaves 1. No 3 token fits, so this is a dead end.
• Five 5 tokens make 25, which leaves 6. Two 3 tokens pay that exactly.

So 31 is five 5 tokens and two 3 tokens, seven tokens in all. The only other way to pay 31 is two 5 tokens and seven 3 tokens, which needs nine.

Here is the method in steps:

1. Take as many large tokens as fit under the total.
2. If what is left is a multiple of the small token, you are done.
3. If not, give back one large token and test the remainder again.
4. Stop at the first mix that works.

Why is the first mix that works also the smallest? Each large token you give back must be replaced by more value in small tokens, and since a small token is worth less, you always need more than one of them to fill the hole. So every step back adds tokens, and the first success uses the fewest. With two token values, this also means the fewest-token answer is always unique.

How many different ways can you pay a total?

Sometimes a puzzle asks how many mixes pay a total. Order does not matter here: 3 + 5 and 5 + 3 are the same payment.

Take 30 with tokens of 3 and 5. The 5 tokens must leave a multiple of 3, so you can use none, three or six of them. That gives three ways: ten 3 tokens, five 3 tokens with three 5 tokens, or six 5 tokens. Fixing the count of the larger token first, and letting the rest follow, stops you from counting the same mix twice.

This is a close cousin of splitting a number into parts. A paper published on 23 August 2024 describes a partition of a number as a way of writing it as a sum of positive whole numbers, where parts may repeat and the order of the parts is ignored ^[2]. A token payment is a partition in which every part is one of the token values, and the fewest-token question asks for the partition with the fewest parts.

The same paper records a rule for counting splits of a number into an exact number of parts: the count for n into m parts equals the count for n minus 1 into m minus 1 parts, plus the count for n minus m into m parts ^[2]. In plain words, sort the splits into two groups. The first group has a part equal to 1, and removing it leaves a split with one part fewer. The second group has every part at least 2, and taking 1 from each part leaves a smaller split with the same number of parts.

Try it on 6 split into three parts. The splits are 1 + 1 + 4, 1 + 2 + 3 and 2 + 2 + 2. The first two contain a 1, and removing it leaves 1 + 4 and 2 + 3, the two ways to split 5 into two parts. The last one has no 1, and taking 1 from each part leaves 1 + 1 + 1, the only way to split 3 into three parts. Two plus one gives three, with nothing counted twice.

Where do coin totals turn up outside puzzles?

They appear in some surprising mathematics. The paper published on 6 June 2012 used coin totals to describe how unit cubes can fill space with no gaps and no overlaps ^[1]. It focused on the cubes that sit on the same unit grid as one chosen cube in such a filling ^[1].

For a box measuring m cubes along every edge, the paper established that the number of those grid cubes inside it is always a multiple of m ^[1]. For a box whose edges have different lengths, the count is always a total you could pay with tokens whose values are the edge lengths ^[1].

What mistakes trip people up?

• Stopping the list too early. You need a run of payable totals as long as the smaller token before you can stop.
• Trusting the greedy grab. The most large tokens can leave a remainder that nothing pays, as with 31 and tokens of 3 and 5.
• Counting the same mix twice. Swapping the order of tokens does not make a new payment.
• Missing a shared factor. If both values are even, odd totals are out of reach for good.
• Forgetting zero. A mix may use none of one token, so 9 is paid by three 3 tokens alone.

Can you solve this practice puzzle?

You have tokens of value 5 and 8. Answer two questions.

1. What is the largest total you cannot pay?
2. What is the fewest number of tokens that pays 50, and which tokens are they?

Draw a ladder with five columns before reading the answer.

Answer 1: The largest total you cannot pay is 27. The first payable totals in the five columns are 5 for remainder 0, 16 for remainder 1, 32 for remainder 2, 8 for remainder 3 and 24 for remainder 4. The latest is 32, and 32 minus 5 is 27. To check, take 8 away from 27 again and again: 27, 19, 11 and 3 are not multiples of 5, so 27 cannot be paid. The next five totals, 28 to 32, can all be paid, so nothing larger is a gap.

Answer 2: Seven tokens, five 8 tokens and two 5 tokens. Six 8 tokens make 48 and leave 2, which no 5 token pays. Five 8 tokens make 40 and leave 10, which is two 5 tokens. The only other way to pay 50 is ten 5 tokens, which needs more.

Ready for a live token puzzle?

Now try a riddle from the catalogue that asks for the fewest tokens. Take as many large tokens as fit, check the remainder, and step back one large token at a time until the mix works.