Pith. sign in

REVIEW

The change-making problem for six coin values and beyond

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2303.00078 v2 pith:UUW6CUJZ submitted 2023-02-28 math.CO

classification math.CO
keywords coinsystemsvaluesorderlychange-makingproblemalgorithmcoins
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
abstract

The change-making problem asks: given a positive integer $v$ and a collection $C$ of integer coin values $c_1=1<c_2< c_3< \cdots< c_n$, what is the minimum number of coins needed to represent $v$ with coin values from $C$? For some coin systems $C$, the greedy algorithm finds a representation with a minimum number of coins for all $v$. We call such coin systems orderly. However, there are coin systems where the greedy algorithm fails to always produce a minimal representation. Over the past fifty years, progress has been made on the change-making problem, including finding a characterization of all orderly coin systems with 3, 4, and 5 coin values. We characterize orderly coin systems with 6 coin values, and we make generalizations to orderly coin systems with $n$ coin values.

Discussion (0). Continue with ORCID to comment.

Pith tools