有没有哪些数学题的某一步处理堪称神来之笔？

美国IMO集训队题集里有这么一题：

试求集合{1,...,2000}有多少个子集的元素和是5的倍数。

正常的解法使用线性代数。

但是还有一种特别抽象的做法是用母函数（生成函数）

这种做法我认为从第一步开始就是神来之笔。

以下是生成函数做法：

我们假定一个序列：c0,c1,c2,c3,...,cn

ci表示元素和为i的子集有多少个。

易得c序列的生成函数

这里就有一个神来之笔了，我们暴力展开这个式子，不难（很难）发现我们展开的过程，以及最后合并同类项的过程就是列举出了所有子集，并把元素和相同的子集合并在一起。

我们继续。

此时展开这个生成函数也可写成

故答案为c0+c5+c10+...+cn

这个时候神来之笔又来了：

代入x=-1可得

而f(1)=c0+...+cn

所以f(-1)+f(1)=2c0+2c2+2c4+...+2cn

但是逆天的是你建立一个数轴把-1^0设成一个0->1的长度为1的向量，你就会发现接下来-1^n的值就是把这个向量旋转180度。

这个时候我们可以的到一个显然的规律，因为旋转180度是所有系数为偶数的项，那么旋转5次返回原点其实就代表了，所有系数是五的倍数的项。

继续看

这个时候建立复平面直角坐标系。

画出这5个点，依旧不难发现他们是五次方程 的5个解。

假定这五个解分别是

故答案为

由于这五个解的循环性质

故f(b)=((1+b)(1+b^2)(1+b^3)(1+b^4)(1+b^0))^400

ok，神来之笔又来了。

上面的那个方程也可以写成 ,然后你把a^5-1因式分解，你就会得到a^5-1=(a-b^0)(a-b)(a-b^2)(a-b^3)(a-b^4)

代入a=-1可得(1+b)(1+b^2)(1+b^3)(1+b^4)(1+b^0)=2

然后不用我再多说什么了吧。