Coins in Twoland

by Joshua Zucker, joshua.zucker at stanfordalumni dot org

In Twoland, the only coins are the toonies: 1, 2, 4, 8, 16, 32, 64, 128, and so on. The law says you must always pay with exact change; only the banks are allowed to make change.

In Twoville you must pay with zero, one, or two of each type of coin, never more than two. (If Twoville is too complicated for you, try Oneville where you can only pay with zero or one of each coin!)

For instance, to pay 6 toonies, you could pay with:

one 4 and one 2 (and zero 1s)
one 4, zero 2s, and two 1s
or two 2s and two 1s.

You could describe the three legal ways to pay by writing them in English, as I just did. You could write the list of legal ways to pay mathematically, too. For instance you might write

4 + 2
4 + 1 + 1
2 + 2 + 1 + 1.

Another, shorter way to write the list of legal ways to pay might be like this:

110
102
022 (or simply 22).

Create a table with the list of ways to legally pay for items that cost 1 toonie, 2 tonnies, ..., 16 toonies in Twoville, remembering that you cannot use more than two of each coin. Or print out the Coins in Twoland PDF and complete the table on the 2nd page. What patterns do you find?

Look at the table you created, describing possible payments of up to 16 toonies. Do you see any patterns in the number of ways to pay with exact change? How about in the list of all the different ways? Tell us about the patterns you find. How will the patterns work when you buy items that cost more than 16 toonies?

Look at the amounts that are one less than an exact single coin. Is there a pattern for the number of ways to pay 1, 3, 7, and 15? Why does that pattern work? How does that pattern continue?

What about the amounts that are exactly one single coin? Is there a pattern for the number of ways to pay 1, 2, 4, 8, and 16? Why does that pattern work? How does that pattern continue?

How about amounts that are one more than a single coin? Is there a pattern for the number of ways to pay 3, 5, 9, and 17? (Do you know how many ways there are to pay 17?) Why does that pattern work? How does that pattern continue?

Are there similar relationships for other lists of numbers? Why do they work?

Can you find a relationship between the number of ways to pay 11 toonies and the number of ways to pay 5? Do you see the same relationship between 13 and 6? By looking at the list of ways, can you find a reason for that relationship? Explain.

Can you find a relationship between the number of ways to pay 10 toonies and the number of ways to pay 4 or 5? Can you find a similar relationship between 12 and 5 or 6? By looking at the list of ways, can you find a reason for that relationship? Explain.

Can you find a relationship between the number of ways to pay 10 toonies and the number of ways to pay 12? Is there a similar relationship between 9 and 13? How about 8 and 14? Can you explain it by looking at the list of ways? As a hint, anything that costs at least 8 and less than 16 can be made using at most one 8, two 4s, two 2s, and two 1s.