省刻度尺问题

摘要：本文给出省刻度尺问题的求解方法，建立了直尺长度n （n∈N+）与刻度数k之间的函数关系，并在分析解的结构规律的基础上，给出了刻度方法。

关键词：省刻度尺;分拆;穷举;递推

省刻度尺问题是一个有一百多年历史的数学问题：在一根长为n （n∈N+）的直尺上刻上最少的刻度，使其能度量1，2，…，n的所有长度，即完全度量。换言之，就是：把一根长为 n （n∈N+）的直尺分成一组最少的线段，并且对于任意一个不大于n 的正整数m，都可以从该组线段中选出若干条相邻的线段，使得它们的长度之和为m。显然，这是一个关于正整数分拆的组合问题。

定义设n1，n2，…，nr是r个正整数，如果n =n1+n2+…+nr，那么上式称为一个部分数为r的n-分拆，记为（n ， r）。n i （i=1，2，…r） 称为该分拆的一个部分，用（n1，n2，…，nr）表示（n，r）的一个分拆，Pr（n）表示分拆（n ， r）的个数，[n ， r]表示满足省刻度尺问题要求的分拆。

因为在长为n（n∈N+）的直尺上度量n-1的方法是唯一确定的，所以在省刻度尺问题分拆（n1，n2，…，nr）中有n1=1。

为简便起见，我们约定：如果n的一个分拆从左至右依次含有h1个a1，h2个a2，…，ht个at，则把这个分拆记为ah11ah22…ahtt。

一、求解问题的方法

例1求分拆[7，3]。

解7的n1=1的 3分拆数为 P2（6）=[62]=3，这里[X]表示不超过X的最大整数。即（1，1， 5），（1， 2， 4），（1，3，3）。对于分拆（1，1，5），由于n1=1，所以其全排列的个数为2！=2，即（1，1，5），（1，5，1）。分拆（1，1，5）不能度量3，4（从分拆（1， 1， 5）中不能选出若干相邻的部分，使其和为3，4）;分拆（1，5，1）不能度量2，3，4。

分拆（1，2，4）的全排列的个数为2！=2，即（1，2，4），（1，4，2）。分拆（1，2，4）不能度量5，分拆（1，4，2）不能度量3。分拆（1，3，3）的全排列的个数为1，分拆（1，3，3）不能度量2，5。

综上可知，分拆[7，3]无解。

例2求分拆[7，4]。

解7的n1=1的4分拆数为P3（6）=[62+312]=3，即（1，1，1，4），（1，1，2，3），（1，2，2，2）。

对于分拆（1，1，1，4），由于n1=1，所以其全排列的个数为3！2！=3，即（1，1，1，4），（1，1，4，1），（1，4，1，1）。其中分拆（1，1，1，4）是[7，4]的解。即1=1，2=1+1，3=1+1+1，4=4，5=1+4，6=1+1+4。

分拆（1，1，2，3）的全排列的个数为3！=6，即（1，1，2，3），（1，1，3，2），（1，2，1，3），（1，2，3，1），（1，3，1，2），（1，3，2，1），其中分拆（1，1，2，3），（1，1，3，2），（1，2，3，1），（1，3，1，2），（1， 3， 2， 1）都是[7，4]的解。

分拆（1，2，2，2）的全排列的个数为1，即（1，2，2，2），且分拆（1，2，2，2）是[7，4]的解。

综上可知，分拆[7，4]的全部解为（1，1，1，4）， （1，1，2，3），（1，1，3，2），（1，2，3，1），（1，3，1，2）， （1，3，2，1）（1，2，2，2）。

由例1、例2知求解省刻度尺问题[n，r]的步骤如下：

（1）计算[n，r-1]无解;

（2）计算 n的n1=1的r分拆数Pr-1（n-1），并写出Pr-1（n-1）这个分拆;

（3）对每一个分拆（1，n2，…，nr）求出其全排列数，并写出所有排列;

（4）对上述排列中的每一个分拆进行计算（从该分拆中选出若干相邻的部分，使之和为m，m为任意一个不大于n的正整数），即可得到[n，r]的解。

例3求分拆[28，8]。

解（1）计算P7（27）：

P7（27）=∑7k=1PK（27-7）

=P1（20）+P2（20）+…+P7（20）

=1+[202]+[202+32]+（P1（16）+P2（16）+…+P4（16））+（P1（15）+P2（15）+…+P5（15））+（P1（14）+

P2（14）+…+P6（14））+（P1（13）+ P2（13）+…+ P7（13））

=1+10+33+64+84+90+82=364。

这364个n1=1的分拆（28，8）依次如下：

（1，1，1，1，1，1，1，21）;

（1，1，1，1，1，1，2，20）;

（1，1，1，1，1，1，3，19），（1，1，1，1，1，2，2，19）;

（1，1，1，1，1，1，4，18），（1，1，1，1，1，2，3，18），（1，1，1，1，2，2，2，18）;

…………………;

（1，1，1，1，3，7，7，7），（1，1，1，1，4，6，7，7），（1，1，1，1，5，5，7，7），（1，1，1，1，5，6，6，7），…，（1，1，2，3，3，4，7，7），…，（1，2，3，3，3，4，5，7），（1，2，3，3，4，4，4，7），（1，3，3，3，3，3，5，7），（1，3，3，3，3，4，4，7）;

…………………;

（1，1，1，5，5，5，5，5），（1，1，2，4，5，5，5，5），（1，1，3，3，5，5，5，5），（1，1，3，4，4，5，5，5），…，（1，3，3，3，4，4，5，5），（1，3，3，4，4，4，4，5）;

（1，3，4，4，4，4，4，4）。

（2）对每一个分拆（1，n2，…，n8）求出其全排列数，并写出所有的排列。例如对于分拆（1，1，2，3，3，4，7，7）由于n1=1，故其全排列数为7！2！2！=1260。这1260个排列依次如下：（1，1，2，3，3，4，7，7），（1，1，2，3，3，7，4，7），（1，1，2，3，3，7，7，4），（1，1，2，3，4，3，7，7），…，（1，2，3，3，7，7，4，1），…，（7，7，4，3，3，1，2，1），（7，7，4，3，3，2，1，1）。

（3）对其中的每一个分拆进行计算，得到分拆（1，2，3，3，7，7，4，1），即12327241是[28，8]的解。

二、直尺长度n与刻度数k之间的函数关系

按照求解问题的方法求出分拆[81，15]，[91，16]，[101，17]，[112，18]，[123，19]，[135，20]，[147，21]，[160，22]，…的解分别为16 8 95 7 8 7，17 9 105 8 9 8，17 9 106 8 9 8，18 10 116 9 10 9，18 10 117 9 10 9，19 11 127 10 11 10，19 11 128 10 11 10，110 12 138 11 12 11，…。于是当K=14，15，…，21，…时，有73≤n≤81，82≤n≤91，…，148≤n≤160，…（1）

设F（k）为k个刻度完全度量时最大的直尺长度（F（k）≥n，k=r-1），由（1）知，F（14）=81，F（15）=91，F（16）=101，F（17）=112，F（18）=123，F（19）=135，F（20）=147， F（21）=160，…

因为数列F（14）=81，F（16）=101，F（18）=123，F（20）=147，…是一个二阶等差数列，于是F（k）是k的二次多项式，设F（k）=ak2+bk+c（a≠0），由

F（14）=142a+14b+c=81

F（16）=162a+16b+c=101

F（18）=182a+18b+c=123

解得a=14，b=52， c=-3。所以，F（k）=14k2+52k-3=14（k2+10 k-12）（k=2j，j=7，8，…）。

对于数列F（15）=91，F（17）=112，F（19）=135，F（21）=160，…，同样可以得到F（k）=14（k2+10k-11）（k=2j+1，j=7，8，… ）。

再设f（k）为k个刻度完全度量时最小的直尺长度（f（k）≤n，k=r-1），由（1）知，f（14）=73，f（15）=82，f（16）=92，f（17）=102，f（18）=113，f（19）=124，f（20）=136，f（21）=148，…，同样可以得到f（k）=14（k2+8k-16）（k=2j，j=7，8，…）和f（k）=14（k2+8k-17）（k=2j+1，j=7，8，…）。

由f（k）≤n≤F（k）得到直尺长度n与刻度数k之间函数关系式如下：

14（k2+8k-16），k=2j

14（k2+8k-17），k=2j+1

j=7，8，…≤n≤

14（k2+10k-12），k=2j

14（k2+10k-11），k=2j+1

j=7，8，…（2）

记Δn=F（k）-f（k），则当k=2j或2j+1，j=7，8，…时，Δn=14（k2+10 k-12）-14（k2+8k-16）= 12k+1或 12 k+ 32 。这说明当刻度数k递增2时，Δn递增1。

三、解的结构之间的关系

由（2）可以知道，当k=14～21时，能够完全度量73～160的直尺。按照求解问题的方法，得到它们的解结构分别如表1、表2所示（不唯一）。

从表1、表2中可以看出如下规律：表2中的解比表1中相对应的解在相同的位置数字增加2或1;再由表1的内容知它们构成等差数列，于是当k≥14时，有省刻度尺问题的解如表3所示。

例4求长为200的省刻度尺问题的解。

解我们把表3称为解阵，其中第p行、第q列的解记为Φ（p、q）（p=1，2，3，…，q=1，2，3，4）。现在的问题就是要求出p、q的值。

（1）求刻度数k。

若k为偶数，由（2）得

14（k2+10k-12）≥200，所以k≥24。取k=24，代入上式，则

14（242+10×24-12）=201>200（3）

若k为奇数，由（2）得

14（k2+10k-11）≥200，所以k≥25。取k=25代入上式，则

14（252+10×25-11）=216>200（4）

比较（3）和（4）知，k=24。

（2）求p、q。

因为f（24）=188，F（24）=201，n=200，201-188=13，201-200=1，所以p=13，即倒数第二行，因为k=24=2×11+2，所以m=11，q=3。于是[200，24]的解为Φ（13，3），即11214 154 14 154 13 14 13。

当1≤k≤13时，省刻度尺问题的解如表4所示（不唯一）。

参考文献：

[1]曾令辉.省刻度尺问题初探[J].数学通报，2001（10）.

[2]曹汝成.组合数学[M].广州：华南理工大学出版社，2000.

[3]吴振奎，吴F.数学中的美[M].哈尔滨： 哈尔滨工业大学出版社，2011.