摘要有一根正整数单位长树枝，要剁成一定长的短树枝，在剁的过程中可以重叠，问如何剁次数最少？这样的问题被称为剁树枝问题。

剁树枝问题是许多实际问题的一个模型，有着广泛的应用。

本课题的任务是提供一般的方法使剁的次数最少。

采用例举、分析、归纳、证明的流程，给出了剁树枝问题最少次数的递推关系和具体表达式，并对其进行了证明。

关键词初等数论；组合数学；递归；数学归纳法AbstractSuppose there is a positive integer units long branches, to chop them into a certain length of short branches. During the cutting process overlap is allowed, then how many times is needed at least? This problem is known as cutting the tree problem. The cutting branches-problem is a model for many practical problems, with a wide range of applications. Based on the idea of dynamic programming, the recursion formula of the least number of movements necessary for this problem is presented. The direct formula of the least number of movements necessary for this problem is given and proved by triple mathematical induction and pure combinatorics.Key words number theory；combinatorial mathematics；recursive; mathematical目录摘要 (2)第一章．绪论 (4)1.1 剁树枝问题的简介 (4)1.2 剁树枝问题的研究意义及主要方法 (4)第二章．主要理论：递归关系 (5)第三章．推导过程 (6)3.1 剁成1分米长的短树枝的情况 (6)3.2 剁成2或3分米长的短树枝的情况 (9)第四章．结论 (13)致谢 (14)参考文献 (15)附录：外文参考文献 (16)参考文献翻译 (18)第一章.绪论1.1 剁树枝问题的简介有一根正整数单位长树枝，要剁成一定长的短树枝，在剁的过程中可以重叠，问如何剁次数最少？这样的问题被称为剁树枝问题。

例如：长为4分米的树枝要剁成1分米长的短树枝，先剁成两个2分米长度的树枝，再重叠剁成四个1分米的长度的短树枝，这样剁的次数最少，为两次。

又如，长为9分米的树枝要剁成2分米或3分米长的短树枝最少次数是两次。

剁树枝问题是许多实际问题的一个模型，有着广泛的应用。

本课题的任务是提供一般的方法使剁的次数最少。

1.2 剁树枝问题的研究意义及主要方法本课题是主要研究剁树枝这样一个数学模型的一般性解决方法，涉及数论和组合数学知识，为日常生产生活、以及数学中类似问题的解决提供模型和参考。

本课题的研究主要将涉及初等数论、组合数学等方面的知识，尤其是组合数学中的递推关系，将在本课题的研究中起到重要的作用。

力图通过研究任意正整数长度的树枝分别剁成1分米，2或3分米两种情况的最少次数的情况，由其归纳出普遍适用的函数关系式，并通过验证、证明，归纳出最终的结论。

第二章 主要理论：递归关系在组合数学中，递归关系是求解计数问题的重要方法。

一般地说，当01n n k≥+≥时，若数列0(())((0),(1),...,(),...)n f n h h h n ≥=满足(h (n ))=F (h (n -1),h (n -2),…,h (n-k )) （*） （这里F 是k 元函数）则称式（*）为这数列的递推关系（或递归关系）。

而满足递推关系（*）的数列称为这递推关系的解。

当这数列的初始值 h (0),h (1),…,h (0n )给定时，从式（*）可依次计算出00(1),(2)h n h n ++,…. 从而就确定了这数列，也就是可以计算出这数列的每一项。

有时还能得到这数列的通项公式。

第三章.推导过程3.1剁成1分米长的短树枝的情况（为书写方便，所有单位dm均忽略不写）：设n为树枝长度（n∈Z*），f(n)为最少剁的次数。

例举n∈[1,50]的情形。

如：当n=1时，f(1)=0.当n=2时，剁一次，f(2)=1.n=3,f(3)=2.……n=16时，先在中间剁一次为2个8（记为8·2），重叠在中间成4个4（4·2·2），如此往复，依次可得：16=8·2=4·2·2=2·2·2·2=1·2·2·2·2，共剁4次,f(16)=4n=17,先剁成8+9，重叠后剁成(4+4)+(4+5)，重叠后剁成2·7+3，再次重叠剁成1·15+2，最后将2剁成两个1，共计5次。

……n=50, 50=25·2=(12+13)·2=(6·3+7)·2=(3·7+4)·2=(2·9+1·7)·2 =1·50,由等号的个数可以看出f(50)=6.结果如下表所列：通过以上表格和在分析得到此表格的过程，我们可以得到如下发现：1.f(n)随着n的增大而增大或不变，即f(m) ≥f(n),m ≥n.2.f(n) 在以下位置之后值发生改变：f(1)=0, f(2)=1,f(4)=2, f(8)=3, f(16)=4,f(32)=5.……不难发现这样的规律：f(2n)= n，f(2n+ t )= n+1 (1≤t <2n).为了证明这个公式，下面，我将给出以下几个引理：引理1.1f(n) ≤f(n+1)证明：由剁树枝的过程，此定理显然成立。

引理1.2 f(2n)=f(n)+1证明：由剁树枝的过程可发现，对于偶数长度的树枝，先将其对半剁，使2n长度为2个n长。

接着将2个n重叠，以下剁法同长为n的树枝。

故长2n的树枝比长n的树枝多剁一次，即f(2n)=f(n)+1.引理1.3 f(2n-1)=f(2n) n≥2证明：对于大于1的奇数长度的树枝，如2n-1，第一步将其剁为长度相差最小的两段，即(n-1)+n，然后将这两段树枝重叠再剁。

由f(n-1) ≤f(n),故重叠后至少要剁f(n)次。

故f(2n-1)=f(n)+1=f(2n).下面我们开始定理的证明：定理1.对于长度为m（m∈Z*）分米的树枝，将其剁为长度为1分米的短树枝，最少所需次数为f(m)。

则f(m)满足下列公式：任意m∈Z*, 存在n, t ∈Z , 使得m=2n+ t , 其中t∈[0, 2n),t∈Z .n t=0;则f(m)=f(2n+t)=n+11≤t <2n.证明：【一】先考虑t=0的情形：n=0时，f(1)=f(02)=0 .结论成立。

n >0时，由引理1.2，有f (2n )=f (2·12n -)=f (12n -)+1=f (22n -)+2=……=f (02)+n=n. 得证。

【二】再考虑t ≠0 ，即1≤t <2n的情形：n ≥1时，2n < 2n +t < 12n +，故由引理1.1，有 f(2n ) ≤ f(2n +t) ≤ f(12n +) （1）而由引理1.3: f(2n-1)=f(2n) n ≥2，故 f(2n +1)=f(2n +2)=f[2*(12n -+1)]=f(12n -+1)+1=f(12n -+2)+1=f(22n -+1)+2=……=f(2n n-+1)+n=f(2)+n=n+1 .又 f(2n )=n , f(2n+1)=n+1 , f(12n +)=n+1,由（1）式及引理1.1，有n+1= f(2n +1) ≤f(2n +t) ≤ f(12n +)=n+1,故 f(2n+t)=n+1, 1≤t <2n . 得证。

3.2 剁成2或3分米长的短树枝的情况设n 为树枝长度（n ∈Z*），g(n)为最少剁的次数。

例举n ∈[2,50]的情形。

如：当n =2或3时，g(n)=0;当n=4时，剁一次，g(n)=1 ……n=16时，先在中间剁一次为2个8（记为8·2），重叠在中间成4个4（4·2·2），再重叠剁一次即可，依次可得：16=8·2=4·2·2=2·2·2·2，共剁3次,g(16)=3n =17,先剁成8+9，重叠后剁成(4+4)+(4+5)，重叠后剁成2·7+3，共计3次，故g(17)=3。

……n=50, 50=25·2=(12+13)·2=(6·3+7)·2=(3·7+4)·2=3·14+2·4, 由等号的个数可以看出g (50)=5.结果如下表所列：和剁成1分米的情况类似，我们也不难得到如下发现：3.g(n)随着n的增大而增大或不变，即g(m) ≥g(n),m ≥n.4.g(n)在以下位置之后值发生改变：g(3)=0,g(6)=1，g(12)=2,g(24)=3,g(48)=4. ……不难发现这样的规律：g(3·2n)=n，g(3·2n+ t )=n+1 (1≤t <3·2n).为了证明这个公式，同样也将给出以下几个引理：引理2.1g(n) ≤g(n+1)证明：由剁树枝的过程，此定理显然成立。

引理2.2 g(2n)=g(n)+1证明：由剁树枝的过程可发现，对于偶数长度的树枝，先将其对半剁为最简方案，使2n长度为2个n长。

接着将2个n重叠，以下剁法同长为n的树枝。

故长2n的树枝比长n的树枝多剁一次，即g(2n)=g(n)+1.引理2.3 g(2n-1)=g(2n) n≥3证明：对于大于3的奇数长度的树枝，如2n-1，第一步将其剁为长度相差最小的两段，即(n-1)+n，然后将这两段树枝重叠再剁。

由g(n-1) ≤g(n),故重叠后至少要剁g(n)次。

故g(2n-1)=g(n)+1=g(2n).下面我们开始定理的证明：定理2.对于长度为m （m ∈Z*）分米的树枝，将其剁为长度为2或3分米的短树枝，最少所需次数为g(m)。