Coins (Jurgen van Dijk)Discuss about this problem
(from the "End-of-Year Contest 2000" by the department of Mathematics and Computer Science at Eindhoven University of Technology)

In the European currency there are coins of 1 and 2 euro and notes of 5, 10, 20, 50, 100, 200 and 500 euro. One can pay 46 euro by giving one 50-euro note and getting back two 2-euro coins. These denominations are not convenient when at most 3 coins (metal or paper) are allowed to change hands. This way for example 33 euro cannot be paid.

Consider K values W1 < ... < WK for the coins. These values are called (L,M)-perfect, when all integer amounts from 1 to L euro are payable with at most M coins. The euro-standard with K=9 is (32,3)-perfect.

Find a best choice for W1, ..., WK for a given M and K, that is an (L,M)-perfect combination with maximal L.

This problem is also discussed by Andries Brouwer at http://www.win.tue.nl/~aeb/contest2000/.

What is L(k,m), the largest integer L such that one can find k integers w1, ..., wk such that each integer 1, 2, ..., L can be written as a sum m1 w1 + ... + mk wk with |m1| + ... + |mk| at most m?
Please send us a simpler description.