筹码的面值怎样设计最好

我们玩扑克要用到多种筹码。
在Calgary 经常用到的有0,5$,1$,5$,25$,100$，有时也用500$,但很少使用。在拉斯维加斯，也见过2$、3$和20$的筹码。

下面我出一道题。
我们只考虑整数筹码，1，2，...N
这里N相当大
我们来设计一套筹码，使得
组成各种筹码量使用的筹码个数
的总和（这一行是后加的）
和
筹码的种类
乘积最小。
假设Dealer 都使数学家。

我摘抄一段文字：
“
柯尼斯堡七桥问题：
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年才证明。

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

刚看见这题，还没仔细看回帖。先发个言。
如果“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取对数。没法输入公式，只能凑合表示。

牛人都进圈了
123456...

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

————— ...

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

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

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

本文作者：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

我说一下这道题我的解题思路。
我是用计算机编程序解的，在出题时我高估计算机CPU的计算能力，也就是低估题目的计算复杂性。因此在原题目中写了N是一个很大的数。实际计算中当N＝2000时就很难计算出最优解了。

我是采用逼近的算法解的。
以N＝1000,4种筹码为例。
首先给4种筹码一个初始值：比如（1,5，25,125）
用符合逻辑的初始值就可以，结果与初始值无关，只是稍微影响找到最佳方案的更速度。
1是必须的。
然后在初始值“附近”搜索更好的方案。
“附近”的意思：
5附近为3－8
25附近为18－33
125附近为93－154
这个“附近”不能太大（会使计算复杂），也不能太小（会丢掉更好的方案）。

进行三重循环搜索更好的方案。当找到更好的方案后再在更好的方案“附近”搜索更好的方案。
一直到找不到更好的方案为止。
4种筹码策略用三重循环，5种筹码策略用四重循环，程序是用递归的方法写的，适用于多种筹码策略。

搜索方案也是用递归的方法写的。
Search(CHips,NC)
CHips是筹码数,NC是筹码种类
在使用了1个125的筹码后就
Search(875,3)
当搜索到Search(X,1)就结束了，用X个1$筹码就可以了。把筹码总和记住。所有可能的组合找出筹码最少的。
CHips从1到N搜索，把各个筹码总和加起来，与前一个方案比较，如果这个方案好就在这个方案搜索，否则计算其它方案。

我的计算结果是：
100(1,12,19)=1563
500(1,13,69)=14982
500(1,7,56,95)=13648
500(1,7,17,72,118)=13705
1000(1,18,97)=38955
1000(1,9,89,140)=33996
1000(1,7,52,137,218)=33335
2000(1,22,162)=100488
2000(1,12,138,236)=83884
5000(1,29,300)=349944
10000(1,38,469)=894672

第一个数字为N
括号里的数字个数为筹码种类，单个数字为筹码面值
最后一个数为所有表达1到N的筹码总和乘以筹码种类

N越大，筹码种类越多计算就越复杂。
N＝2000的5种筹码就很难算了，我编的程序只少需要12个小时。

dfu2012 发表于 2012-12-21 20:46
J兄，每个人的经历不同，谈不上谁差还是好，心境不同而已，相由心生，境由心转。

上贴中的那个朋友，曾 ...

德夫无论数学知识还是人生哲学都领会深刻
能在智游城认识真是件开心的事

能到处走?
穷的就只剩下天生的那两个小肉蛋了

Jsli 发表于 2012-12-21 19:47
德夫有QQ没?

我的情况比你差,这个年纪了王小二一年不如一年

J兄，每个人的经历不同，谈不上谁差还是好，心境不同而已，相由心生，境由心转。

上贴中的那个朋友，曾经很多年前在澳门一夜输掉XXXX万，我初初听人说起的时候，当天人一般的存在，这样的人现实中实在离我太远了。前几年，他一夜玩掉几十万，还能淡定自如。若干年后，他亲口告诉我他以前有多少资金的时候，话语中听出了王小二过年的弦外之音。及至现在，可以连续几天不睡觉不断的玩就因为输了几十万（事实上他现在的实力依然能支撑他这么玩）。我看出了他的无力焦灼和疲惫，他的岁数不小了。就算赢回这几十万，又能怎么样？一个人过的好不好，和他有多少钱真一点关系都没有。


付出了那么大的代价，如果是为了要回曾经失去的，那么人真是很苦，失去的东西就算回来，岁月如何找回？太执着了，执着就是苦。所以怎么找都没用。我一直相信，失去一些东西必然会得到一些东西，所谓等价交换守则。

知足心平常心如果要耗费巨大的代价才能明白，多大的代价才够？有些人一辈子就迷进去了。

你我都比很多人强，有饭吃，有地方住，还能上论坛扯扯淡，很好了，你还能世界到处走走没有签证的麻烦。。。