If you must pay an amount in coins, the "intuitive" algorithm is: pay as much as possible with the largest denomination coin, and then go on to pay the rest with the other coins. For example, if there are 25, 5 and 1 cent coins, to pay someone 32 cents, you'd first give him a 25 cents coin, then one 5 cent coin, and finally two 1 cent coins.)

However, this doesn't always end paying with as few coins as possible: if we had 25, 10 and 1 cent coins, paying 32 cents with the "intuitive" algorithm would use 8 coins, while three 10 cent coins and two 1 cent coins would be better.

We can call a set "intuitive", if the "intuitive algorithm" always pays out any amount with as few coins as possible.

The problem: give an algorithm that allows you to decide that {25,5,1} is an "intuitive" set, while {25,10,1} isn't.

There's more to it than simple divisibility by the preceding value.  As has already been pointed out, {1, 2, 3} is intuitive, and it appears as if {1, 2, 5} is also intuitive.

I suspect that the intuitiveness is related to divisibility by the preceding number, but you also have to consider the numbers preceding the preceding number as well.

Perhaps each number needs to be checked against the number preceding it and the number following it.  For instance, with {1, 10, 25} you find the smallest number that is divisible by 10 which is larger than 25 and take the number of 10's it would take to get there (in this case 30 requires 3 dimes).  Then find the number of 25's and 1's to get to the same value.  If you can get to the number using fewer middle values then the set is NOT intuitive.


Using this criterion, {1, 5, 25} is intuitive, because it takes 6 5's to get to 30, but it also takes a total of 6 (5x1 + 1x25) to get to the same number.

The set {1, 7, 22} is NOT intuitive because it takes 4 7's to get to 28, but it requires 7 coins (1x22 + 6x1) to get to the same number.

The set {1, 2, 3} is intuitive because it takes 2 2's to get to 4, but it also takes 2 coins (1x3 + 1x1) to get to the same number.

The set {1, 2, 5} is intuitive because it takes 3 2's to get to 6, but it only takes 2 coins (1x5 + 1x1) to get to the same number.

The set {1, 5, 7} is NOT intuitive because it only takes 2 5's to get to 10, but it takes 4 coins (1x7 + 3x1) to get to the same number.


I'll leave it as an exercie to the reader to solve larger sets using the same criterion.

Posted by Erik O. on 2005-03-30 15:47:52