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.

A set of values (S1, S2, S3, S4, S5, S6) is "intuitive" if its medium terms (S2, S3, S4, S5) adequate to "intuitivity". Verifying the set means verify the "intuitivity" of all single medium terms.

My thesis is that a term (Sj) adequate to intuitivity when the sum with itself, or with other inferior term of the set (Sj-i), that make the addition higher to the superior term of the set (Sj+1), can be expressed as the sum of this superior term (Sj+1) and (eventually) other term of the set (Sk).

In other words: Sj + Sj-i = Sj+1 + Sk

Ex: 1,3,4,7,11,18 is intuitive if 11, 7, 4, and 3 are.

11 adequate to intuitivity because: S5+S5 = 11+11 = 22 = 18+4 = S6+S3. Also  S5+S4 = 18 = S6

7 adequate to intuitivity because: 7+7 = 14 = 11+3. Also 7+4 = 11 (= S5)

4 adequate to intuitivity because: 4+4 = 8 = 7+1. Also 4+3 = 7

3 doesn't adequate because 3+3>4+1

So the set is not intuitive because term 3 isn't. But if I add another term with value 2 the set become intuitive.

The generalization of this requires some arrangements (for ex. if S6>2S5, verifying S5 means verifying 2S5, but in this case you can add another term Sk; if S5>3S4 the rule applies to 3S4 an so on and is possible to add two other terms Sk of the set). The principium is always the same: express the identity of the sum of two different groups of terms in the set.

 

Posted by armando on 2005-04-02 09:32:01