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.
Well, I have some time to devote to this, and have solved the 3 denomination case.
Consider the set {B, A, 1} where B > A > 1.
Divide B by A, giving a whole quotient Q with a remainder R.
B = A*Q + R, where R between 0 and A -1.
If R = 0, then the set is intuitive. (See many previous posts)
Otherwise, test A*(Q+1), the first whole multiple of A which is greater than or equal to B.
Using the greedy algorithm A*(Q+1) can be formed using 1 B coin and (A-R) singles, for a total of 1 + A - R coins.
Using an "ungreedy" algorithm, A*(Q+1) can be formed using Q+1 coins of denomination A.
The set is non-intuitive if 1 + A - R > Q + 1.
In other words, if Q + R < A.
In other words, if the Quotient and the Remainder, when dividing B by A, is less than A, as long as R is not zero.
I am interested in the n-denomination case, so I will not write down a proof that the converse is true, but I am 100% confident.
The set is intuitive if the Quotient and the Remainder, when dividing B
by A, is greater than or equal to A, (or if the Remainder is 0).
Two applications:
a) {25,5,1} is intuitive because 25/5 = 5 has a remainder of 0.
{25,10,1} is not intuitive because 25/10 = 2
with a remainder of 5, and 2 + 5 < 10.
b) {B,5,1} is not intuitive if B = 6,7,8,11,12, or 16
and is intuitive if B = 9,10,13,14,15 or B >= 17
On the right track
