The currency of United Kingdom (UK) is called pounds (£), with 1 pound equivalent to 100 pennies (
). The denomination of the coins are:
. The minimum coins I needed to carry so that I could make any value from
to
is 8.
Now suppose the currency of a fictitous country next to the UK is called dounds , with 1 dound is equivalent to 100 antidisestablishmentarianism ( ). This country has a ridiculous denomination of coins, namely: . What is the minimum number of coins I needed to carry so that I could make any value from to ?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Here's my (somewhat tedious) solution:
Starting at 1 a , we know we'll need at least two 1 a coins, to make 1 a and 2 a . For 3 a , we can just use one 3 a coin.
So here's our coins so far:
From these we can make 4 a and 5 a , but we'll need another 3 a coin to make 6 a . After we do this, we can make 7 a and 8 a , but we'll need another 3 a coin for 9 a . Values of 1 0 a and 1 1 a will then be covered, but we'll need to add one more 3 a coin for 1 2 a .
Here's our coins so far:
But don't worry, the whole process isn't so laborious!
For 1 3 a , we can add a new 1 3 a coin. But notice something here: we went from 1 a to 1 2 a just with our 1 a and 3 a coins, so using these, we can go from 1 3 a all the way to 1 3 a + 1 2 a = 2 5 a and hit every integer along the way!
Coins so far:
For 2 6 a , we'll need another 1 3 a coin. As before, we can then easily go from 2 6 a to 2 6 a + 1 2 a = 3 8 a with all integers in between. Then another 1 3 a coin for 3 9 a and then we can go from 3 9 a to 3 9 a + 1 2 a = 5 1 a .
Coins so far:
Now at this point, we need a value of 5 2 a , but notice that we're not using all of our available small change. In 1 a s and 3 a s, we can technically increase 1 4 a . We only used 3 a coins to increase 1 2 a , so we can easily add another 1 a coin to get 5 2 a .
Coins so far:
Now we get to use a 5 3 a coin for 5 3 a . With small change, we can go from there to 6 5 a . Then, we could just use add a 1 3 a coin to our 5 3 a coin for 6 6 a . Then from there to 7 8 a . And with two 1 3 a coins, 7 9 a . Then from there to 9 1 a . (Hopefully the pattern is beginning to emerge!) Then with three 1 3 a coins, 9 2 a . And then from there we don't even need a 9 3 a coin. We just have to use our smaller change to get up to 9 9 a !
Whew!
But there you have it: we can get every integer from 1 a to 9 9 a using 2 + 4 + 3 + 1 = 1 0 coins!
Nice problem Pi Han Goh!