You are responsible for creating new types of coins for the court.
King respects the forgetful: he wants you to create 8 coins of different value, no more.
King respects the feeble: he wants that any (integer) sum of money (price) could be paid with no more than 8 coins, since they can be heavy. This sum should be paid without giving change.
- But my king, no matter how big is the largest coin, you can't pay more than 8 of them! How would you pay any sum?
- The king respects the poor: he wants you to set N such that no price in the kingdom is allowed to be greater than N. Thus, the contradiction with the rule (2) can be satisfied.
However, you, as a wealthy customer, are very troubled with this last rule. You want to maximize N so you can continue buying ludicrously overpriced things.
What is the maximum N you can reach by creating the coin standard?
Answer
The optimal solution is
1, 8, 13, 58, 169, 295, 831, 1036
This set of coins allows N =
3485
This set of coins is given in this paper: Some Extremal Postage Stamp Bases, by Michael F. Challis and John P. Robinson.
This paper was found by @alephalpha.
No comments:
Post a Comment