筹码的面值怎样设计最好

看到科学松鼠会上有一篇类似文章，转发一下，顺便景仰下老陈强大的编程思路和探求真理的决心：

——————————————————————————————————————————————

本文作者：Albert_JIAO

两个造假币的不小心造出了 33 元的钞票却又不想浪费，他们决定拿到偏远山区花掉。用 33 元的假币买了一串 1 元的糖葫芦后，他们哭了：农民伯伯找给他们两张 16 元！

当然，这只是一个段子。加拿大滑铁卢大学计算机系研究员 Jeffrey Shallit 也很喜欢这个段子，并且他认为，从理论上讲钞票就应该有 16 元和 33 元的。

16元的纸币最方便

以人民币为例，纸币面值在 100 元以下的一共有 1 元、5 元、 10 元、 20 元、 50 元五种。 Jeffrey 认为这 5 种纸币面额数值的组合并不是最科学的，而应该是 1 元、 5 元、 16 元、 23 元、 33 元这五种。

平时我们去超市买东西，每次使用 100 元以下数额的钱（ 1 元到 99 元），需要用 1 元、 5 元、 10 元、 20 元、 50 元五种面额的钱币组合而成，有的时候需要一张，有的时候需要两张或者更多。比如你需要 31 元的零钱，可以用三张 10 元的和一张 1 元，也可以用一张 10 元、一张 20 元和一张 1 元，前一种需要四张纸币，后一种需要三张。在组成 31 元的所有可能方案中， 10+20+1 是最佳的，它最节省钞票张数，也就是说，凑成 31 元最少也需要三张纸币。

我们可以对从 1 到 99 之间的每个数额分别算出来它最少需要的纸币张数，这不难通过编程实现。这样一来就能知道使用这五种面额的人民币组成 99 个数额，在最“环保”的组合方式下，平均需要多少张钞票。

接下来， Jeffrey 在电脑上把参数修改了一下，五种纸币的面额更改为各种其他数值，让电脑程序运行，看一看哪一种货币面额体系在组成99个数额的时候平均最方便、需要的纸币张数最少。最终结果就是前面说过的， 1-5-16-23-33 方案击败了我们现实生活中使用的 1-5-10-20-50 方案，也击败了其他各种方案，组成 99 个数额平均只需要最少的3.29张。


【Jeffrey的货币最佳发行方案。】

值得一提的是，这个研究结果不仅适用于人民币。比如目前美国的流通的硬币主要有 1 美分、 5 美分、 10 美分和 25 美分四种，可是根据 Jeffery 的结果，要想最方便的凑齐 1 美分到 99 美分一共 99 个数额，美联储应该发行 18 美分而不是 10 美分的硬币。

在加拿大，实际流通中的硬币有 6 种： 1 分、 5 分、 10 分、 25 分、100 分和 200 分，而最小的纸币面额是 5 加元。这 6 种硬币的“艰巨任务”是组成 1 到499 的数字。 Jeffery 计算出平均每笔交易会用到 5.9 枚硬币，不过他建议在这个体系中加入一枚面值为 83 分的硬币，这个数值就会降为 4.578 枚。他和他的学生甚至还给 83 分的假想硬币设计了正面和背面图案。不过 Jeffery 的论文在 2003 年就发表了，但到现在 83 分的硬币还没问世。

二进制的面值也好用

当然，最佳货币面额的计算方法也并非完美无瑕，一个漏洞就是 Jeffery 计算平均需要的张数的时候假定 1 到 99 个数额我们平时使用的频率是一样的，可现实交易中往往小的数额出现的机会更大，如果考虑这个因素，恐怕“最佳面额”结果就会有所改变。

另一方面，不只 Jeffery 一个人琢磨过这个问题，有人模仿信息编码方式设计出一套很酷很潇洒的货币面额方案。若纸币面额是按照二进制设置的，1元、2元、4元、8元、16元、32元、64元，虽然未必保证每次付款的时候使用的张数最少，但是神奇之处在于，每次出门的时候只要带齐一套，每样一张，就可以组成1到127的任意数额。

不仅如此，如果考虑了找钱的情况之后，三进制，也就是面值分别为 1 元、 3 元 、9元、27元、 81 元……也可以实现“每样一张，找零无忧”的效果，不信你可以随便选个数字试一下。比如你想付款 20 元，需要做的是给收银员一张 27 元、一张 3 元的，收银员找给你一张 1 元的，一张 9 元的，整个交易过程中每张也只出现了一次，唯一的麻烦是三进制的钞票计算起来有点费脑筋。

实际使用不容易

计算机人士提出各种数学游戏式的货币发行方案尽管看起来很酷，真正被掌管货币发行的金融高富帅们采纳的却极少。事实上，银行在考虑发行哪些数额的纸币的时候主要考虑的就是两个实际因素。第一个是货币面额要考虑人们日常的十进制算术习惯，如果又是最优组合，又是二进制、三进制，数学不好的人士必将苦不堪言，街边买菜的大妈恐怕买次东西算钱也要算上几分钟， 5 元、 10 元、 20 元的面额在数学上未必是最佳的，但是起码算数的时候最方便。第二个因素是尽量少发行一些面额种类，如果面值种类很多，尽管组成任意数额都不会出现一大把钞票的情形，但是银行不便于管理，使用者可能自己都搞不清楚到底有哪些面额了。

要说世界上发行钞票面值种类最多的地方当属几年前的非洲国家津巴布韦了。当时津巴布韦国家经济出现了崩溃，恶性通货膨胀愈演愈烈，银行也在滥发纸币。哈佛大学举办的以“乍看之下令人发笑，之后发人深省”为宗旨的搞笑诺贝尔奖 2008 年的数学奖就授予了津巴布韦国家储备银行行长的戈诺，颁奖理由是他居然下令印刷了1分（0.01元）至100万亿面值的钞票，大幅提高了本国国民的数学能力。

现实中的货币面额大多是按照习惯和经验而已，背后并没有涉及到很多数学知识，世界上各国的货币不外乎都是1、2、5、10这类面额，本文有些异想天开的方案恐怕只能停留在数学爱好者自己想象的世界中了。

参考资料

[1] What This Country Needs is an 18 Piece; Jeffrey Shallit

[2] Optimal Denominations for Coins and Bank Notes: In Defense of the Principle of Least Effort; Leo Van Hove

Howard 发表于 2012-12-28 08:14
看到科学松鼠会上有一篇类似文章，转发一下，顺便景仰下老陈强大的编程思路和探求真理的决心：

————— ...

筹码面值与种类设计和钞票面值与种类设计在数学上是完全一回事，一点差别也没有！

牛人都进圈了
123456...

刚看见这题，还没仔细看回帖。先发个言。
如果“N”足够大，筹码应该是1，5，25，125...5^n.
以下是大概思路：
1）在最佳筹码下，下一个面值都应该是上一个面值的m倍。m是常数。换句话说，筹码面值是等比数列，1，m,m^2,...m^n... (数学可证,但是很繁琐，就不写了）
2）这其实是几进制是最佳进制的问题。大数“N"在m进制下共log(m,N)位 （log(m,N)个面值）。m进制下，每位的数字可以是0，1，2……m-1。表示一个[1,N]的数平均每个面值的筹码要用（m-1）/2个。所以
组成各种筹码量使用的筹码个数的总和×筹码的种类= N×（m-1）/2 ×log(m,N)×log(m,N)
3）上面表达式在m比5稍小一点时有极小值。当m为整数时，m=5，上式极小。具体计算就不写了。无非是log换底公式加上对m求导。

注：log(m,N)表示以m为底对N取对数。没法输入公式，只能凑合表示。

看了一下跟帖，大家把N取成小数时，问题反而复杂化了。直接把N想成无穷大更容易看到问题的本质。

我摘抄一段文字：
“
柯尼斯堡七桥问题：
1852年十月，咖色利正在为一副英国地图着色。他思考了要区别各个国家最少需要几种颜色，他得到的结果是四种颜色。1879年给出了这个数确实是4的一个证明。但后来发现这个证明是错误的。几乎一个世纪后，1976年，两个年轻的数学家海肯和爱普尔证明了这个已非常著名的四色地图问题。然而，这个证明认为是值得商榷的，因为他是用计算机得到的，而不是用纯粹的数学逻辑。
”
X^N+Y^N=Z^N,当N大于2时没有整数解。

引
“
后来发现欧拉对于N=3的费马大定理的证明有一个错误，这被高斯改正了。那时候大多数有名望的数学家都是法国人，但毫无疑问那个时代-也可能是所有时代-最伟大的数学家的高斯，却是地道的德国人。
”
“。。。”
《费马大定理》，非常非常好看的一本书，说数学史的，我看的是左平翻译的。原作者是（AMIR D.ACZEL）

数学的魅力在于最难部分的求解，最难部分往往看上去似乎又很简单。

X^N+Y^N=Z^N,当N大于2时没有整数解。

历经数百年（算源头的话可以说数千年），费马大定理到1993年才证明。