别轻视，小学奥数题也能折磨人！！

蓉依山爸

谁来玩玩这道小学的奥数题？

某个新成立的国家，正在设计货币系统。为方便交易，该国的货币只有“元”这一个货币单位；并且，要求1～N元中的所有金额，都最多用三张货币的加减来表示。如：
A、2A、A+B、A-B、3A、2A+B、2A-B、A-2B、A+B+C、A-B-C …… 等
如果货币的面值共分10种，请问：N的最大值是多少？

注意：1～N元是连续的
要求所有金额，都最多用三张货币的加减来表示

补充内容 (2013-12-3 09:09):
问题二：当N最大时，请问十种面值各为多少？

补充内容 (2013-12-3 09:33):
为避免有人把题目看错，我在4楼把题目重新解释一下

Lwins_G

小学的这种题可以不写证明，只写推理过程。

kastin

面值共分10种，具体是哪十个？这个不告诉的话，N就没法确定了。

蓉依山爸

某国正在设计货币系统。为方便交易，该国的货币只有“元”这一个货币单位；并且，1～N元（包括1和N）中的所有金额，都最多用三张货币的加减来表示。如 ——
1、用一张钞票表示金额：A
2、用二张钞票表示金额：A+A、A+B、A-B
3、用三张钞票表示金额：A+A+A、A+A+B、A+A-B、A+B+B、A-B-B、A+B+C、A+B-C、A-B-C …… 等
如果货币的面值共分10种，请问：
①N的最大值是多少？
②当N最大时，十种面值各为多少？

注意：1～N元是连续的。所有的金额，都最多用三张货币的加减来表示。不能有遗漏的金额。

最后，再扩展一下这道题吧！
当N最大时，十种面值的设置方案可能不只一种。
请问：能否找到这样一种具有“发展性”的方案，即：
当该国因通货膨胀发行第十一种面值的钞票时，不用更改前十种面值的钞票，N也能最大。
如果能找到这种具有“发展性”的方案，那么，面值的通项公式是什么？

rayfekeeper

这是组合数论的题目啊。我先给一个最大估计吧：
设$x_{1}<x_{2}...<x_{s}$表示s种面值，对于任意自然数$n(n<N)$,可以写成以下形式

$n=a_{1}x_{i}+a_{2}x_{j}+a_{3}x_{k}$,其中$a_{1},a_{2},a_{3}$为整数还需满足

$\|a_{1}\|+\|a_{2}\|+\|a_{3}\|<=3$

归结成上述问题后，我们只需要去看n有多少个正值(负值取相反数即可)，也就是归结到算上面组合能最多表示多少个表达式的问题，

显然对于s，我们有，

1).只含有一种面值的表达式有$3*C(s,1)$个，分别是$x_{i},2*x_{i},3x_{i}$

2)含有两种面值的表达式有$6*C(s,2)$，分别是$x_{i}+x_{j},x_{i}-x_{j},2x_{i}+x_{j},2x_{i}-x_{j},x_{i}+2x_{j},x_{i}-2x_{j}$

3).含有三种面值的表达式有$4*C(s,3)$，分别是$x_{i}+x_{j}+x_{k},-x_{i}+x_{j}+x_{k},x_{i}-x_{j}+x_{k},x_{i}+x_{j}-x_{k},$

当s=10时，理论上最大值应该是

$3*C(10,1)+6*C(10,2)+4*C(10,3)=780$

rayfekeeper

对于第四问，我给出一些想法来抛砖引玉吧，自己没太多时间考虑。

我这里考虑的是最优解的问题，若不然，可以无视。

1.最大面值$x_{max}<=N/3$

2.设最大的面值为$x_{max}$，那么$x_{max}-1$也必须是一种面值，否则无法表示N-1

3.考虑最大的三种面值，设为$x_{max-2}<=x_{max-1}<=x_{max}$，那么$3*x_{max-2}+1$必然要表示为$2*x_{max-2}+x_{max-1}$,于是$x_{max-1}=x_{max-2}+1$

于是我猜测最优解应该是$x_{max},x_{max}-1,...x_{max}-10,$

显然$2*x_{max}+x_{max-2}=2*x_{max-1}+x_{max}$这说明两种以上的面值无最优解.

rayfekeeper

两种面值时，最优解是4和3，

$3*C(2,1)+6*C(2,2)=12$

4=12/3

3=4-1

kastin

这个题感觉对于小学生来说太难了（本科生都不一定能做出来），虽然只涉及到正整数的四则运算，但是如果一旦涉及到代数（一般情况），那就非常难了——想一想整数划分这个问题表达是多么的简单，但是一般公式也只有拉马努金这样的天才数学家给出了答案。本身对于非具体数字的问题，小学生就难以理解，更重要的是，如果解题用到的方法都比较特殊或者比较高级，他们更难理解。

这类问题应该属于组合优化的问题，属于本科生甚至研究生学习的内容。一看到楼主的问题我就联想到2个曾经思考过并研究过的热门问题。

首先让我想到的是砝码称重问题（也叫“德·梅齐里亚克问题”）——
    一位商人有一个40磅的砝码，由于跌落在地而碎成4块。后来，称得每块碎片的重量都是整磅数，而且可以用这4块恰能称出1至40磅之间的任意整数磅的重物。问这4块砝码碎片各重多少？（注：这里称重的天平的两端都能放砝码，因此可作加减法，于是这个问题可等价于4种货币面值，可连续表示1~N的货币值，其中N最大为40时，求面值方案。）

砝码称重问题相当有名（记得曾出现在我们初中暑假作业的思考题中），最早可以追溯到17 世纪法国的德·梅齐里亚克 (Bachet de Meziriac，1581~1638)，他曾（1624）在自己的著作中提出过该问题，并给出了一个巧妙的解法。

他的解法很简单，基于加减算术和逻辑推理：
    为使两砝码A与B能称出最多种重量,必须是1磅和3磅,用它们能称出1、2、3、4磅的重物。若选第三块砝码C的重量为2x4+1=9磅,则用它们可称出1至9+4=13磅间的所有整数磅重物。最后选第四块砝码D,使它重量为2x13+1=27磅,那么用这四块砝码能称出从1至27+13=40磅的重物.因此,这四块砝码的重量分别为1、3、9、27磅。

上面的思路很清楚，但是难以弄懂这个算式是怎么得出的，当时我看到这个解法，在去食堂吃晚饭的途中就想出来了，过程较为曲折，但是一旦规律想明白就很快知道方法了。简单地说，上面的计算式中含有乘数2是因为加法和减法的对称性，具体自己稍作分析便知，这里不详述。仅举个简单的例子说明：比如想要连续表示1~10，肯定以5或6为界，比如知道1~4连续表示方案（1和3），再附上6，那么1~10就能连续表示。

德·梅齐里亚克问题梅自己给出了方案，但是方案的唯一性没有严格证明（其实他的推理过程中包含了唯一性，但是不太明显）。我们知道，这只是一类问题的一种特例而已，即给定N，找出方案。那么问题可以进一步被推广——有n块不同的砝码，每个都是整数重量，它们利用天平能连续称出1~N的重量，问：
1. 给定N（比如N=87），求n的最小值以及砝码重量方案，如果方案唯一请给出唯一性证明。
2. 给定n(比如n=10)，求N的最大值以及相应的砝码重量方案，如果方案唯一请给出唯一性证明。（这就是楼主的问题）

不难看出，梅给出的答案是3的连续幂次(3^0, 3^1, 3^2, 3^3)。因此可以猜想这个问题本质是三进制表达：砝码要么放在左端（-1），要么不放上去（0），要么放在右端（+1）。问题2的答案是对于给定n块砝码，那么能连续表示的范围是1~(3^n-1)/2。于是楼主问题是n=10，N=(3^10-1)/2=29524。不需要证明过程的话，对于参加奥数小学生（一般对于等比数列比较了解）应该能推出这个答案。问题1则是给定N=87，类似地，可连续表示1~87的最小n应该是ceil(log(2*87+1)/log(3))=5，其砝码方案就是1, 3, 9, 27, 81。

但是对于我们肯定不会止步于猜想，必然想要一个唯一性证明之类的严格过程。

对于组合计数问题，如果大家熟悉母函数的话，都知道母函数对大部分问题是非常有效的[注1]，只不过楼主的问题[注2]与通常情况[注3]不同是，要求加减法都能用并且还要保持连续。其实母函数方法仍能使用，我们可以考虑使用带负幂次的多项式的母函数即可。具体用法网上有篇文章有些简短说明（原文链接：www.guokr.com/article/3742/），直接引用如下——

这种方法是19 世纪的麦克马洪 (MacMahon) 给出的。下面就来领略一下其中的思想吧，或许你会从中学到很多。

因式分解的妙用假设有一个重为 a 克的砝码，那么用它自然能够称出 0 克和 a 克的物品。不过，如果虚设天平的某一端为正的话，利用此天平和砝码我们还能称出 - a 克的物品——不妨规定把 a 克砝码放在天平右侧，将物品放在天平左侧，由此可以称出 a 克的物品；但若把 a 克砝码放在天平左侧，把物品放在天平右侧，由此称出的物品重量记作 - a。目前这样一种设想有点怪异，但这实际上和人类引入负数的思想是相同的。很快大家便会发现，这种设定非常精妙地简化了我们的计算和推导。现在暂且把该砝码能够称出的重量 - a，0，a 放进一个表达式中：
现在，假设有两个不同规格的砝码，分别重 a 克和 b 克（a
可以看到，它不是别的，正好是
的展开式。
另外，假设有 m 个同样重为 a 克的砝码，则可以称出 - ma，- (m - 1)a，…，0，…，(m - 1)a，ma 克的物品。暂且按照上面的办法，把这些数也塞进一个表达式中 ：
结合上面的分析，容易看出，如果有 m 个 a 克的砝码，n 个 b 克的砝码，等等，那么可以称出物品的克数就是表达式
展开后出现过的那些 x 的幂数，而展开式中 x 的 i 次项系数就表示用给定的这组砝码称出 i 克物品的不同方法数。
如果要称出 1 到 40 中所有的整克数，并且要求所用的砝码尽可能少，我们自然希望这些砝码能够“物尽其用”，称出的克数正好都是我们需要的克数，并且称的方法都是唯一的。也就是说，上述表达式展开后应该恰好是
反过来，就是要把
还原成
的形式。
对这个式子进行分解，一共有八种不同的方案：
前四个式子展示了我们实际上是如何对原式进行逐步分解的。它们的意义依次为：(1) 40 个 1 克的砝码；(2) 1 个 1 克，13 个 3 克的砝码 ；(3) 1 个 1 克，1 个 3 克以及 4 个 9 克的砝码；(4) 1 个 1 克，1 个 3 克，1 个 9 克以及 1 个 27 克的砝码。其中，第四个分解式是最基本的，它就是我们想要的答案。
当然我们还要说明，除了上面列举的 8 种组合之外没有其他的组合。这是一个多少有些复杂的讨论，不过我们可以就此为止了，因为上面的分解式看起来应该明显包含了所有可能的分解。最少的那组已经明摆着了，无须再说。

如果上述问题被完全解决了，有兴趣的话我们还可以进一步考虑这种情况：如果要求稍微严格一点，规定砝码只能放在天平的一端，那么上面问题的答案又是如何呢？同样猜想这个问题相当于二进制表示，因为只能做加法，不能做减法。所以天平只有两种状态：要么砝码不放上去（0），要么砝码放上去（+1）。于是方法跟上面一样，只是底数改为2而已。

-------注释----------
[1] 比如最为常见的例子：1分，2分，5分硬币各自有a,b,c枚，问能表示成多少种面值之类的问题。
[2] 若规定砝码能加在天平两端（即可使用加减法，楼主的问题以及梅的问题即是这种类型），
[3] 若规定砝码只能加在一端（即只能使用加法），这种属于简单的线性不定方程的问题，即通常的母函数解决的问题。



我联想到的第二个问题就是所谓的称球问题（这个问题跟德·梅齐里亚克问题有点类似，但有很大不同）。
       有12个不可分辨的实体球，已知其中至少有一个坏球（由于制造工艺问题，可能会有球质量低于标准或者高于标准，这种球被称为坏球，或者不合格的球），现在利用一个没有砝码的天平找出这个坏球，最多需要称n次才能找出坏球（或者找不出坏球，即证明不存在坏球），并判断该球是过轻还是过重。问n是多少？

      答案是3次，即最多三次称重就能找出坏球，并知道是轻球还是重球（或者判定没有坏球）。

大多数人稍作思考便可给出找出坏球的方案，但是要给出同时能判定球是过轻还是过重的方案，不一定能轻易想出来（当时我在草稿纸上比划了很久才想出来）。
分析过程比如，先取出10个球平均分成两组，各自放到天平两端。如果平衡，那么剩下的球便是坏球，进一步可通过与好球比较，得知该球是轻是重。但是这是一种最幸运的情况，仅仅这一步是不够的。
如果天平没有平衡，而是左倾或者右倾，那么对轻球组要进行一种分法，配合重球组进行判断，等等……

上述问题只是一种特例，而且问题问的内容也可改变，比如给定n，问N的取值范围；或者给定n,N，判断问题是否有解，或者是否可定性（判断坏球是否存在，以及球是过轻还是过重）。

为此，该问题可一般表述为：
    有N个颜色、质地、大小一模一样的球，其中有B个球是不合格的球（球的重量要么超过标称值，要么低于标称值，二者居其一），现在有一个没有砝码的天平，需要通过称重比较的方式来挑出不合格的球。（由于没有砝码，因此每次称重时，左右两端球的数量必须一样，否则无法找出不合格的球）。
    问：假如最多允许称n次，那么是否能找出不合格的球（即是否可解）, 如果能找出不合格的球的话（请给出称球方案），能否知道该球是轻是重（是否可定性）？进一步，如果给定n、B，那么N的最大值为多少？

需要说明的是，该问题的答案是比较开放的，因为其解严重依赖其他没有提到的条件，比如B的个数范围（一般来说，B是<=1的），N的范围等。

为了叙述上的简便，我们引入一些符号来表示问题的实例化。（虽然这么做需要稍微费些脑筋去理解这些符号所表示的实例问题的意义，但是这么做有助于分析和表达过程。）

记Pr={n, N, B, M, P, Q, R, G}表示称球问题的相关参数所定义的称球问题的某种实例，其中
   n为无砝码天平的称重次数；
   N为总共待测球的个数；
   B为不合格（轻或重，只能是一种）球的个数；
   P为轻球组个数，至多为1个轻球，其他都是合格球；
   Q为重球组的个数，至多1个重球，其他都是合格球；
   R为待测组，有R个球，其中至多有一个不合格的球；
   G为合格球的个数；
   M为特殊用途参数(下文有说明)。
另记 “不可解”表示“并非总能保证找出不合格的球”；“不可定性”表示“并不总能对不合格的球进行定性（即轻重判定）”。


曾经在某两本数学辅导书（书名忘了）上看到了这个问题的探究，里面提供了大量特例的探索结论，我曾做过笔记，现部分摘录如下：
{n, B<=1, N=(3^n-3)/2}可解，可定性。
{n, B<=1, N>=(3^n-1)/2}不可解。
{n, B=1, N=(3^n-1)/2}可解，不可定性。
由此可知对于给定n,B<=1时，N的最大值是(3^n-1)/2.
另外还有更多条结论——
{n, B<=1, G=1, N=(3^n-1)/2}可解，可定性。
{n, B=1, G=1, N=(3^n+1)/2}可解，不可定性。
{n, B<=1, G任意, N>=(3^n+1)/2}不可解。
{n, B=1, G任意, N>=(3^n+3)/2}不可解。
{n=k, B<=1, 3<=N(=P+Q)<=3^k-1}可解，可定性。
{n=k, N=P+Q=3^k, B<=1, G任意}不可解。
{n=k, N=P+Q=3^k, B=1可解，可定性。
{n=k, N(=P+Q)>=3^k, B=1, G任意}不可解。
一般地，{n, N(=P+Q+R)>=3, B=1, M=P+Q+2R<=3^n}可解。

更一般地，{n, N=P+Q+R, B=1}的问题
对于
n=2
      N=3,4,4,5,6,7,8时，共有
      ……（41条结论）
n=3时，共有
......(35条以上的结论)

从上面的结论可以看出，问题的解与数字“3”有着莫大的关联。其实很简单，由于天平的状态只有三种：“左倾”、“平衡”、“右倾”。每次我们只能得到这三种信息，需要根据这些信息找出不合格的球。本质上这个过程仍然是一个三进制表示状态的问，因此该问题的一般解法（称球方案）跟三进制的表示有关。

书上给出其三进制一般解法，具体是是将N个球标号0~N-1，然后分别用三进制表示之然后有一些四则运算，涉及较多判断比较。文字较多故不再赘述了。
另外一书还提到，这个问题可等价为一些列带约束的线性方程组的正整数解的问题。表达式有些复杂所以当时没有做笔记（只记得约束条件较为复杂，我试图通过纯分析的方法给出计算算法，但是感觉很难便放弃了），现在想起来感觉但是该方法适合计算机编程求解。