整数的分拆

第4讲 整数的分拆 第4讲 整数的分拆 　　整数的分拆，就是把一个自然数示成为若干个自然数的和的形式，每一种表示方法，就是自然数的一个分拆。 　　整数的分拆是古老而又有趣的问题，其中最著名的是哥德巴赫猜想。在国内外数学竞赛中，整数分拆的问题常常以各种形式出现，如，存在性问题、计数问题、最优化问题等。 　　例1 电视台要播放一部30集电视连续剧，若要求每天安排播出的集数互不相等，则该电视连续剧最多可以播几天？ 　　分析与解：由于希望播出的天数尽可能地多，所以，在每天播出的集数互不相等的条件下，每天播放的集数应尽可能地少。 　　我们知道，1+2+3+4+5+6+7=28。如果各天播出的集数分别为1，2，3，4，5，6，7时，那么七天共可播出28集，还剩2集未播出。由于已有过一天播出2集的情形，因此，这余下的2集不能再单独于一天播出，而只好把它们分到以前的日子，通过改动某一天或某二天播出的集数，来解决这个问题。例如，各天播出的集数安排为1，2，3，4，5，7，8或1，2，3，4，5，6，9都可以。 　　所以最多可以播7天。 　　说明：本题实际上是问，把正整数30分拆成互不相等的正整数之和时，最多能写成几项之和？也可以问，把一个正整数拆成若干个整数之和时，有多少种分拆的办法？例如： 　　5=1+1+1+1+1=1+1+1+2， 　　=1+2+2　　 =1+1+3 　　=2+3　 　　=1+4，共有6种分拆法（不计分成的整数相加的顺序）。 　　例2 有面值为1分、2分、5分的硬币各4枚，用它们去支付2角3分。问：有多少种不同的支付方法？ 　　分析与解：要付2角3分钱，最多只能使用4枚5分币。因为全部1分和2分币都用上时，共值12分，所以最少要用3枚5分币。 　　当使用3枚5分币时，5×3=15，23-15=8，所以使用2分币最多4枚，最少2枚，可有 　 　23=15+（2+2+2+2）， 　　23=15+（2+2+2+1+1）， 　　23=15+（2+2+1+1+1+1）， 　　共3种支付方法。 　　当使用4枚5分币时，5×4=20，23-20=3，所以最多使用1枚2分币，或不使用，从而可有 　　23=20+（2+1）， 　　23=20+（1+1+1）， 　　共2种支付方法。 　　总共有5种不同的支付方法。 　　说明：本题是组合学中有限条件的整数分拆问题的一个特例。 　　例3 把37拆成若干个不同的质数之和，有多少种不同的拆法？将每一种拆法中所拆出的那些质数相乘，得到的乘积中，哪个最小？ 　　解：37=3+5+29 　　　　　=2+5+7+23=3+11+23， 　　　　　=2+3+13+19=5+13+19 　　　　　=7+11+19=2+5+11+19 　　　　　=7+13+17=2+5+13+17 　　　　　=2+7+11+17， 　　共10种不同拆法，其中3×5×29=435最小。 　　说明：本题属于迄今尚无普遍处理办法的问题，只是硬凑。比37小的最大质数是31，但37-31=6，6不能分拆为不同的质数之和，故不取；再下去比37小的质数是29，37-29=8，而8=3+5。其余的分拆考虑与此类似。 　　例4 求满足下列条件的最小自然数：它既可以表示为9个连续自然数之和，又可以表示为10个连续自然数之和，还可以表示为11个连续自然数之和。 　　解：9个连续自然数之和是其中第5个数的9倍，10个连续自然数之和是其中第5个数和第6个数之和的5倍，11个连续自然数之和是其中第6个数的11倍。这样，可以表示为9个、10个、11个连续自然数之和的数必是5，9和11的倍数，故最小的这样的数是［5，9，11］=495。 　　对495进行分拆可利用平均数，采取“以平均数为中心，向两边推进的方法”。例如，495÷10=49.5，则10个连续的自然数为 　　45，46，47，48，49，（49.5），50，51，52，53，54。 　　于是495=45+46+…+54。 　　同理可得495=51+52+…+59=40+41+…+50。 　　例5 若干只同样的盒子排成一列，小聪把42个同样的小球放在这些盒子里然后外出，小明从每只盒子里取出一个小球，然后把这些小球再放到小球数最少的盒子里去，再把盒子重排了一下。小聪回来，仔细查看，没有发现有人动过小球和盒子。问：一共有多少只盒子？ 　　分析与解：设原来小球数最少的盒子里装有a只小球，现在增加到了b只，由于小明没有发现有人动过小球和盒子，这说明现在又有了一只装有a个小球的盒子，这只盒子里原来装有（a+1）个小球。 　　同理，现在另有一个盒子里装有（a+1）个小球，这只盒子里原来装有（a+2）个小球。 　　依此类推，原来还有一只盒子装有（a+3）个小球，（a+4）个小球等等，故原来那些盒子中装有的小球数是一些连续整数。 　　现在这个问题就变成了：将42分拆成若干个连续整数的和，一共有多少种分法，每一种分法有多少个加数？ 　　因为42=6×7，故可将42看成7个6的和，又 　　（7+5）+（8+4）+（9+3） 　　是6个6，从而 　　42=3+4+5+6+7+8+9， 　　一共有7个加数。 　　又因42=14×3，故可将42写成13+14+15，一共有3个加数。 　　又因42=21×2，故可将42写成9+10+11+12，一共有4个加数。 　　于是原题有三个解：一共有7只盒子、4只盒子或3只盒子。 　　例6 机器人从自然数1开始由小到大按如下规则进行染色： 　　凡能表示为两个不同合数之和的自然数都染成红色，不符合上述要求的自然数染成黄色（比如23可表示为两个不同合数15和8之和，23要染红色；1不能表示为两个不同合数之和，1染黄色）。问：被染成红色的数由小到大数下去，第2000个数是多少？请说明理由。 　　解：显然1要染黄色，2=1+1也要染黄色， 　　3=1+2， 　　4=1+3=2+2， 　　5=1+4=2+3， 　　6=1+5=2+4=3+3， 　　7=1+6=2+5=3+4， 　　8=1+7=2+6=3+5=4+4， 　　9=1+8=2+7=3+6=4+5， 　　11=1+10=2+9=3+8=4+7=5+6。 　　可见，1，2，3，4，5，6，7，8，9，11均应染黄色。 　　下面说明其它自然数n都要染红色。 　　（1）当n为大于等于10的偶数时， 　　n=2k=4+2（k-2）。 　　由于n≥10，所以k≥5，k-2≥3，2（k-2）与4均为合数，且不相等。也就是说，大于等于10的偶数均能表示为两个不同的合数之和，应染红色。（1）当n为大于等于13的奇数时， 　　n=2k+1=9+2（k-4）。 　　由于n≥13，所以k≥6，k-4≥2，2（k-4）与9均为合数，且不相等。也就是说，大于等于13的奇数均能表示为两个不同的合数之和，应染红色。 　　综上所述，除了1，2，3，4，5，6，7，8，9，11这10个数染黄色外，其余自然数均染红色，第k个染为红色的数是第（k+10）个自然数（k≥2）。 　　所以第2000个染为红色的数是2000+10=2010。 　　下面看一类有规律的最优化问题。 　　例7 把12分拆成两个自然数的和，再求出这两个自然数的积，要使这个积最大，应该如何分拆？ 　　分析与解：把12分拆成两个自然数的和，当不考虑加数的顺序时，有 　　1+11，2+10，3+9，4+8，5+7，6+6 　　六种方法。它们的乘积分别是 　　1×11=11，2×10=20，3×9=27， 　　4×8=32，5×7=35，6×6=36。 　　显然，把12分拆成6+6时，有最大的积6×6=36。 　　例8 把11分拆成两个自然数的和，再求出这两个自然数的积，要使这个积最大，应该如何分拆？ 　　分析与解：把11分拆成两个自然数的和，当不考虑加数的顺序时，有1+10，2+9，3+8，4+7，5+6五种方法。它们的乘积分别是 　　1×10=10，2×9=18，3×8=24， 　　4×7=28，5×6=30。 　　显然，把11分拆成5+6时，有最大的积5×6=30。 　　说明：由上面的两个例子可以看出，在自然数n的所有二项分拆中，当n是偶数2m时，以分成m+m时乘积最大；当n是奇数2m+1时，以分成m+（m+1）时乘积最大。换句话说，把自然数S（S＞1）分拆为两个自然数m与n的和，使其积mn最大的条件是：m=n，或m=n+1。 　　例9 试把1999分拆为8个自然数的和，使其乘积最大。 　　分析：反复使用上述结论，可知要使分拆成的8个自然数的乘积最大，必须使这8个数中的任意两数相等或差数为1。 　　解：因为1999=8×249+7，由上述分析，拆法应是1个249，7个250，其乘积249×2507为最大。 　　说明：一般地，把自然数S=pq+r（0≤r＜p，p与q是自然数）分拆 　　为p个自然数的和，使其乘积M为最大，则M为qp-r×（q+1）r。 　　例10 把14分拆成若干个自然数的和，再求出这些数的积，要使得到的积最大，应该把14如何分拆？这个最大的乘积是多少？ 　　分析与解：我们先考虑分成哪些数时乘积才能尽可能地大。 　　首先，分成的数中不能有1，这是显然的。 　　其次，分成的数中不能有大于4的数，否则可以将这个数再分拆成2与另外一个数的和，这两个数的乘积一定比原数大，例如7就比它分拆成的2和5的乘积小。 　　再次，因为4=2×2，故我们可以只考虑将数分拆成2和3。 　　注意到2+2+2=6，2×2×2=8；3+3=6，3×3=9，因此分成的数中若有三个2，则不如换成两个3，换句话说，分成的数中至多只能有两个2，其余都是3。 　　根据上面的讨论，我们应该把14分拆成四个3与一个2之和，即14=3+3+3+3+2，这五数的积有最大值 　　3×3×3×3×2=162。 　　说明：这类问题最早出现于1976年第18届国际数学奥林匹克试卷中。该试卷第4题是： 　　若干个正整数的和为1976，求这些正整数的积的最大值。 　　答案是2×3658。 　　这是由美国提供的一个题目，时隔两年，它又出现在美国大学生数学竞赛中。1979年美国第40届普特南数学竞赛A-1题是： 　　求出正整数n及a1，a2，…，an的值，使a1+a2+…+an=1979且乘积最大。 　　答案是n=660。 　　1992年武汉市小学数学竞赛第一题的第6题是： 　　将1992表示成若干个自然数的和，如果要使这些数的乘积最大，这些自然数是____。 　　答案：这些数应是664个3。 　　上述三题的逻辑结构并不随和的数据而改变，所以分别冠以当年的年份1976，1979和1992，这种改换数据的方法是数学竞赛命题中最简单的方法，多用于不同地区不同级别不同年份的竞赛中，所改换的数据一般都是出于对竞赛年份的考虑。将上述三题的结论推广为一般情形便是： 　　把自然数S（S＞1）分拆为若干个自然数的和： 　　S=a1+a2+…+an， 　　则当a1，a2，…，an中至多有两个2，其余都是3时，其连乘积m=a1a2…an有最大值。 　　例11 把1993分拆成若干个互不相等的自然数的和，且使这些自然数的乘积最大，该乘积是多少？ 　　解：由于把1993分拆成若干个互不相等的自然数的和的分法只有有限种，因而一定存在一种分法，使得这些自然数的乘积最大。 　　若1作因数，则显然乘积不会最大。把1993分拆成若干个互不相等的自然数的和，因数个数越多，乘积越大。为了使因数个数尽可能地多，我们把1993分成2+3…+n直到和大于等于1993。 　　若和比1993大1，则因数个数至少减少1个，为了使乘积最大，应去掉最小的2，并将最后一个数（最大）加上1。 　　若和比1993大k（k≠1），则去掉等于k的那个数，便可使乘积最大。 　　 　　所以n=63。因为2015-1993=22，所以应去掉22，把1993分成 　　（2+3+…+21）+（23+24+…+63） 　　这一形式时，这些数的乘积最大，其积为 　　2×3×…×21×23×24×…×63。 　　说明：这是第四届“华杯赛”武汉集训队的一道训练题，在训练学生时，发现大多数学生不加思索地沿用例10的思考方法，得出答案是3663×4，而忽视了题中条件“分成若干个互不相等的自然数的和”。由此可见，认真审题，弄清题意的重要性。 　　例12 将1995表示为两个或两个以上连续自然数的和，共有多少种不同的方法？ 　　分析与解：为了解决这个问题，我们设1995可以表示为以a为首项的k(k＞1）个连续自然数之和。首项是a，项数为k，末项就是a+k-1，由等差数列求和公式，得到 　　化简为 (2a+k-1）×k=3990。(*) 　　注意，上式等号左边的两个因数中，第一个因数2a+k-1大于第二个因数k，并且两个因数必为一奇一偶。因此，3990有多少个大于1的奇约数，3990就有多少种形如（*）式的分解式，也就是说，1995就有多少种表示为两个或两个以上连续自然数之和的方法。因为1995与3990的奇约数完全相同，所以上述说法可以简化为，1995有多少个大于1的奇约数，1995就有多少种表示为两个或两个以上连续自然数之和的方法。 　　1995=3×5×7×19，共有15个大于1的奇约数，所以本题的答案是15种。 　　一般地，我们有下面的结论： 若自然数N有k个大于1的奇约数，则N共有k种表示为两个或两个以上连续自然数之和的方法。 　　知道了有多少种表示方法后，很自然就会想到，如何找出这些不同的表示方法呢？从上面的结论可以看出，每一个大于1的奇约数对应一种表示方法，我们就从1995的大于1的奇约数开始。1995的大于1的奇约数有。 　　3，5，7，15，19，21，35，57，95， 　　105，133，285，399，665，1995。 　　例如，对于奇约数35，由（*）式，得 　　3990=35×114， 　　因为114＞35，所以 k=35，2a+k-1=114，解得a=40。推知35对应的表示方法是首项为40的连续35个自然数之和，即 　　1995=40+41+42+…+73+74。 　　再如，对于奇约数399，由（*）式，得 　　3990=399×10，因为399＞10，所以k=10，2a+k-1=399，解得a=195。推知399对应的表示方法是首项为195的连续10个自然数之和，即 　　1995=195+196+197+…+204。 　　对于1995的15个大于1的奇约数，依次利用（*）式，即可求出15种不同的表示方法。 练习4 　　1．将210拆成7个自然数的和，使这7个数从小到大排成一行后，相邻两个数的差都是5。第1个数与第6个数分别是几？ 　　2．将135个人分成若干个小组，要求任意两个组的人数都不同，则至多可以分成多少组？ 　　3．把19分成几个自然数（可以相同）的和，再求出这些数的乘积，并且要使得到的乘积尽可能大，最大乘积是多少？ 　　4．把1999分拆成两个自然数的和，当不考虑加数的顺序时，一共有多少种不同的分拆方法？求出这两个自然数的积，要使这个积最大，应将1999如何分拆？ 　　5．把456表示成若干个连续自然数的和。要求写出所有的表达式（如9可以有两种表达形式：9=4+5=2+3+4）。 　　6．几个连续自然数相加，和能等于2000吗？如果能，有几种不同的答案？写出这些答案。如果不能，说明理由。 　　7．把70分拆成11个不同自然数的和，这样的分拆方式一共有多少种？将不同的表示方法列举出来。 　　8．有一把长为13厘米的直尺，在上面刻几条刻度线，使得这把尺子能一次量出1到13厘米的所有整厘米的长度。问：至少要刻几条线？要刻在哪些位置上？ 练习4 　　1.15，40。 　　解：这7个数中第4个数是中间数，它是这7个数的平均数，即210÷7=30。因为相邻 2数的差都是 5，所以这7个数是15，20，25，30，35，40，45。故第1个数是15，第6个数是40。 　　2.15组。 　　解：因为要求任意两个组的人数不相等，且分得的组要尽可能地多，所以，要使每个组分得的人数尽可能地少。 　　由于1+2+3+4+…+14+15=120，所以将 135人分成每组人数不等的15个组后还余15人。剩下的15人不能再组成一个或几个新的小组，否则就会出现两个或两个以上的组的人数相等的情况。因此，应将剩下的15人安插在已分好的15个组之中，所以至多可以分成15个组。这15个组各组人数可以有多种情况，例如，分别是 2，3，4，5，6，…，14，15，16人。 　　3.972。 　　解：要使乘积尽可能大，把19分成的几个自然数中，3要尽量多且不能有1，所以应把19分成5个3及1个4的和。最大乘积为35×4=972。 　　4.有999种方法，分成999+1000时积最大。 　　5.提示：456有三个大于1的奇约数3，19，57。利用例12的方法可得：对于3，有k=3，a=151；对19，有k=19，a=15；对于57，有k=16，a=21。所以456有如下三种分拆方法： 　　456＝151+152+153 　　 　＝21+22+23+…+39 　　 　＝15+16+17+…+33。 　　6.能。 　　提示：与例12类似，2000=24×53，有三个大于1的奇约数5，25，125。对于5，有k=5，a=398；对于25，有k=25，a=68；对于125，有k=32， a=47。所以2000共有如下三种分拆方法： 　　2000＝398+399+400+401+402 　　　　＝68+69+70+…+91+92 　　　　＝47+48+49+…+77+78。 　　7.5种。 　　解：1+2+3+…+11=66，现在要将4分配到适当的加数上，使其和等于70，又要使这11个加数互不相等。 　　先将4分别加在后4个加数上，得到4种分拆方法： 　　70＝1+2+3+4+5+6+7+8+9+10+15 　　　＝1+2+3+4+5+6+7+8+9+14+11 　　　＝1+2+3+4+5+6+7+8+13+10+11 　　　＝1+2+3+4+5+6+7+12+9+10+11。 　　再将4拆成1+3，把1和3放在适当的位置上，仅有1种新方法： 　　1+2+3+4+5+6+7+8+9+13+12。 　　再将4拆成1+1+2或1+1+1+1+1或2+2，分别加在不同的位置上，都得不出新的分拆方法，故这样的分拆方法一共有5种。 　　8.至少要刻4条线，例如刻在1，4，5，11厘米处，便可一次量出1到13厘米的所有整厘米的长度。这是因为由1，4，5，11，13这5个数以及它们之间任意2个的差能够得到1到13这13个整数，见下列各式： 　　5-4=1， 13-11=2， 4-1=3， 　　11-5=6， 11-4=7， 13-5=8， 　　13-4=9， 11-1＝10， 13-1＝12。 　　下面我们来证明，只有3个刻度是不够的。如果只刻了3条线，刻在a厘米、b厘米、 c厘米处（0＜a＜b＜c＜13），那么 a，b，C，13两两之差（大减小），只有至多6个不同的数：13-a，13-b，13-c，c-a，c-b，b-a，再加上a，b，c，13这4个数，至多有10个不同的数，不可能得到1到13这13个不同的整数来。 　　顺便说明一下，刻法不是唯一的。例如我们也可以刻在1厘米、2厘米、6厘米、10厘米这4个位置上。