切割立方体.doc

切割立方体及长方体材料切割优化问题
摘要
本文阐述了将一个长方体切割成单位立方体,在两次切割之间可以任意重新堆置各切块,最少切多少次可以完成的问题。在此基础上对切割长方体问题进行了多方面的讨论,引伸出了在工业生产中,采用何种切割方式从一块长方体材料中切割出一个小长方体,使其加工费用最少。
关键字:长方体;切割;加工;费用
Abstract
This paper describes cutting a rectangular into the unit cube, you can re-stack the cut between cutting in the many times at least it needs to cut plete the this basis,a wide range of issues about cutting the rectangular are discussed derived in industrial production makes manufacture costs to a minimum.
Keywords: Cuboid;Cutting;Manufacture;Cost
1 问题的提出
在Richard A. Brualdi 的《binatorics》的第一章中描述了一个这样的问题:要将一个边长为3英尺的立方体切割成为27个边长为1英尺的立方体,其所需的最少切割次数为多少?
在不改变立方体外形的前提下,若依序进行切割。共计切割6次,每个方向上切2次,即可得到27个单位立方体。若在每次切割后,改变各切块堆置位置,切割次数能否减少呢?对于该问题而言,事实上,6次即为最少切割次数。对此,作者运用了一个巧妙的观点对其进行证明。即位于立方体中间的这个立方体的每个侧面都是通过切割而形成的。既然有6个截面,那就必须切割6次才能形成。因此,至少需要6次切割才能满足题目要求。
将该问题扩展为一般情况。要将一个长为a、宽为b、高为c的长方体切割成为a*b*c个单位立方体,其所需的最少切割次数为多少?
2 问题的分析
我们要处理的问题是一般情况,而对此我们一无所知。唯一的解决的办法就是从简单的情况开始分析考虑。这样分析考虑主要以下几点优势。
从特殊情况的研究中,可能可以猜到一般结果的基本形式,然后再予以证明。
从特殊情况摸索出的证明方法可能可以推广到一般情况的证明当中去。
3 函数声明
将边长为a,b,c的长方体V的最少切割次数记作为K(V)或K(a,b,c).在V的各种切法中,凡是切割次数等于K(V)的都称为V的最优切法。
4 问题的推理、证明
考虑最简单的一维问题,即K(a,1,1)。
观察一:将一个长为的木条截成个单位立方体,可按以下方式进行切割:先在木条的中间切开,把所切的两段并在一起,再从中间切开。如此下去,只需m次即可切割完成。
由此,可猜想,将一个长方体切割m次,最多可产生个切块。
由于一次切割,至多能将已有切块一分为二。因此,一刀至多产生2个单位立方体。两刀至多产生4个单位立方体。运用归纳法可证得,m刀至多产生个单位立方体,即K(,1,1)= m (引理一)。
但若长方体本身一开始长度不为2的幂。
我们现在可以假设若长方体与长方体的一部分全等,则K()<=K()(引理二)。这个假设当然也比较容易证明。长方体与长方体全等的部分在切割的同时,也可被切割成为单位立方体,命题即证。
现在开始考虑时的情况。由以上推理可知,m次切割是不够的,因此。又因为=m+1。所以,此时。
所以,我们可以得出以下结论
命题1
其中,表示x向上取整。
接下来,开始讨论二位问题,即的取值为题。
首先对于的特殊情况进行分析。在长、宽两个方向上用观察一可知。与此同时,利用引理一反方向证明,即可证得。对于的情况,由引理一可知。同时,由引理二可知,。所以,由此可得。
最后一种情况,。由引理一可知,。而由引理二可知,。再此上下界中存在一个间隙。主要是观察a、b的值是接近上界还是下界。从特例讨论着手,特别是a、b接近下界的情况。例,a=3,b=,该立方体至少要切割4次才能得到全部的单位立方体,恰好为m+n+2。下面再举一个例子,a=5,b=3。其中,切割一次后,必有一个切块不小于3*3或2*5。因此,之后切割次数至少为4。因此,最少切割次数仍然为m+n+2。因此,可猜想最少切割次数即为m+n+2。
观察二:将长方体V(a,b,c)切割一次产生了中必有
命题2
对于此命题的证明,可将两个参数a、b合二为一,利用普通数学归纳法进行证明。
令a+b=s。当a=b=1即s=2时,结论成立。假设时,