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.

(In reply to On the right track by Steve Herman)

It's a good idea to express it on terms of quotient and remainder.

By the moment I still thinking that to verify the set means verify each term of its terms. Two possibilities:

a) In the case of a term whose quotient with immediate superior term is 1, I worked the formula posted before (see i, k, j, j+1 are sub index):

Sj+Si = Sj+1 + Sk (con k<i and for all k verifying Sk<Rj and     i <= j for all i verifying Si>Rj). If Sj+1 = Sj + Rj (Rj = remainder of Sj relative to Sj+1), we have: Rj = Si - Sk (i>k)

Sk is eventual (can also be 0).

It means that if all the remainders in case a) can be express as the exact value of other term of the set or as difference of two terms of the set (Sj with other inferior, or two inferiors terms), the set is "intuitive" for these terms.

b) if the term has a quotient with immediate superior >1, the formula is:

Rj = Si - Sum (Skq) (Sum is from 1 to q; k and q are sub index and q is the quotient. All these terms are eventual: can be 0 or be present only some).

It means that if all the remainders in case b) can be express as the exact value of other term of the set or as difference of a term and the sum of a q number of other terms (Sj with inferiors, or a inferiors with the sum of others), the set is "intuitive" for that terms. But of this I'm not totally sure.

Example 1: (S1, S2, S3, S4, S5, S6) = (1, 4, 11, 18, 25, 50)  is intuitive because:

R5 = 0 (all multiplex are always intuitive but be applied considering the limit case that i = j, you can consider R25 = S5 = 25)

R4=7=S4-S3;  R3=7=S3-S2;  for R2 formula with quotient is need R2=3=S2-S1.

Example 2: The set 1,3,8,13,23,38 is intuitive. All the remainders can be expressed by differences of other terms. Remainders are 15, 10, 5, 2, 0 and correspond to 23-8, 13-3, 8-3, 3-1, 0.

 

 

Edited on April 12, 2005, 11:24 am

Edited on April 12, 2005, 11:26 am

Edited on April 12, 2005, 11:27 am

Posted by armando on 2005-04-02 22:25:23