Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2303.00078 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913654998302720 |
|---|---|
| author | Van Cott, Cornelia A. Zhang, Qiyu |
| author_facet | Van Cott, Cornelia A. Zhang, Qiyu |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_00078 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The change-making problem for six coin values and beyond Van Cott, Cornelia A. Zhang, Qiyu Combinatorics 05A17 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. |
| title | The change-making problem for six coin values and beyond |
| topic | Combinatorics 05A17 |
| url | https://arxiv.org/abs/2303.00078 |