Next Previous Contents

3. An easy case

L(2,m) = m(m+1) for all m, and the unique optimal set of coins is {m,m+1}.

Indeed, the polytope |m_1|+|m_2| <= m has 2m^2 + 2m + 1 integral points, so if we can get all values in -L, ..., L then L is at most m^2 + m. If we have equality then (assuming w_1 < w_2) we must have m.w_2 = L, so w_2 = m+1. Since we can also make L-1 we need w_1 = m. And the set {m,m+1} actually works, for if some value is missing, some other value must occur at least twice, but if am+b(m+1) = cm+d(m+1) then b=d (mod m) and a=c (mod m+1), so both sides differ by a multiple of m(m+1).


Next Previous Contents