Completely greedy coin sets

2024/07/27 by Andrew J. Young, Young, Andrew J.
Mathematics · #Mathematical Dynamics and Fractals #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2407.19137

Abstract

We show that the binary coin set minimizes the number of coins needed to guarantee the ability to make change in any one transaction and its asymptotic uniform average cost is no worse than that of any completely greedy coin set.

Related

• The Greedy Coin Change Problem
• Canonical Coin Systems for Change-Making Problems
• The change-making problem for six coin values and beyond
• Characterization of canonical systems with six types of coins for the change-making problem
• Totally Greedy Sequences Defined by Second-Order Linear Recurrences With Constant Coefficients