2.21 只考加法的面试题

1,如果N可以分解为几个连续整数的和,则N的因式分解必然要有奇数。
证明如下：

a. 首先证明，只要N的因式分解中有奇数，N就能表示为自然数连和。

     如果N的因式分解中有奇数，假设为s，且N= k * s，

     如果k > s/2，
     则 N可以表示为这个序列的和：k - (s / 2), k - (s / 2) + 1 ... k + (s / 2);

     例如 54 = 6 x 9, 可表示为 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10；（6 x 9，偶数为6，则6在这9个自然数的序列的中间）



     如果 k < s/2，
     则N可以表示为这个序列的和：(s + 1)/2 - k, (s+1)/2 - k + 1,..., (s + 1)/2 + k - 1;

     如54 = 2 x 27，则可表示为 12 + 13 + 14 + 15；（中间两个数 13 + 14 = 27）

b. 再证明：如果N的因式分解中没有奇数，则N不能表示成连和的形式。

     反证：如果能，假设N能表示成k个自然数的连和。

     如果k为偶数，设这k个数的中数（中间偏左的一个）为m，将这k个数收尾相加得到k/2个自然数的序列，

     易证这k/2个自然数都等于2m+1，

     那么N = (2m + 1) * k / 2，与N的因式分解中没有奇数矛盾；

     如果k为奇数，设中数为n，那么N = k * n，与N的因式分解中没有奇数矛盾。

     综上，得证。