【全程NOIP计划】数学推导选讲
常见不等式
柯西不等式
对于数列a和b,有以下恒成立
\[\sum_{i=1}^na_i^2 \sum_{i=1}^n b_i^2 \ge (\sum_{i=1}^na_ib_i)^2 \]令
\(A=\sum a_i^2,B=\sum a_ib_i,C=\sum b_i^2\)
构造以下式子
\[f(x)=Ax^2+2Bx+c=\sum(a_ix+b_i)^2 \ge 0 \\ a_i^2x^2+2a_ib_ix+b_i^2\ge 0 \]\(\triangle\le 0\)，然后就得证了
例子：
有\(x_1,x_2,\dots,x_{4n}\ge 0\)，\(x_{i-1}+x_i+x_{i+1} \le 1(x_0=x_{4n},x_{4n+1}=x_1)\)
求：\(\sum_{i=1}^{4n}(x_{i-1}*x_{i+1})\)
这个系列实际上可以是\(0,\dfrac 12 ,0 ,\dfrac 12,\dots \dots\)
实际上我们可以直接把第二个小于号看成等于号
\[x_0 x_2+x_1x_3\le (1-x_1-x_2)x_2+x_1(1-x_1-x_2) \\=(x_1+x_2)[1-(x_1+x_2)] \]然后换元法，二次函数求最大值
又一个例子:
有\(x_1,x_2,\dots,x_n\in Z_+\)，\(\forall i,x_i \not=10,\sum_{i=1}^nx_i=10n\)
求\((\prod_{i=1}^nx_i)^{\frac 1n}\)的最大值
9 11 9 11 9 11……这样循环下去就可以了
\((\prod x_i)^{\frac 1n}\le \dfrac {\sum x_i} n=10\)
实际上就是均值不等式
再一个例子：
设\(f(x)=\sum_{i=0}^na_ix^{n-i}\)，\(f(x)\)有\(n\)个实数根，\(\forall i,a_i \ge 0\)
求\(f(m)\)的最大值
这是一个n-1元函数
n个根
设这n个根为\(-x_1,-x_2,-x_3,-x_4,-x_5,-x_6,\dots,-x_n\)
然后
\[f(m)=(m+x_1)(m+x_2)(m+x_3)\dots \dots (m+x_n) \]\(m+x_i=m*1+x_i \ge (m+1) \sqrt[m+1]{m*1+x_i}\)
还有：
设n次多项式\(f(x)\)满足\(f(k)=\dfrac 1k (k=1,2,\dots ,n+1)\)
求：\(f(n+2)\)
从上一题吸取一点经验
设\(g(x)=x*f(x)-1\)
\(k=1,2,3,\dots ,n+1\)
\(g(k)=k*f(k)-1=0\)
\(g(x)=(x-1)(x-2)\dots(x-n-1)\)
所以\((-1)^{n+1}！*C=-1\)
\(C=\dfrac {(-1)^n} {(n+1)!}\)
\(g(x)=\dfrac {(-1)^n}{(n+1)!}*(x-1)(x-2)\dots(x-n-1)\)
然后\((n+2)*f(n+2)-1=g(n+2)=(-1)^n\)
则\(f(n+2)=\dfrac {(-1)^n+1} {n+2}\)
二阶线性递推数列的特征方程
\(a_{n+2}=c_1a_{n+1}+c_2a_n\)这一个递推式的特征方程为：
\[x^2=c_1x+c_2 \]如果这个方程的两个解为：\(x_1,x_2\)
则\(a_n\)的通项公式为:\(a_n=C_1x_1^n+C_2x_2^n\)
比如斐波那契数列的特征方程就可以求
\(f_{n+2}=f_{n+1}+f_n\)
例子：
已知数列a满足：
\(a_1=-4,a_2=-7,a_{n+2}=5a_{n+1}-6a_n\)
求\(a_n\)的通项公式
实际上用刚才的特征方程就好了
又一个例子:
求\(\lfloor(\dfrac {5+\sqrt{21}} {2})^n \rfloor\)的个位数字
发现上面的其实是\(x^2-5x+1=0\)的两个解
然后\(x^2=5x-1\)
\(a_{n+2}=5a_{n+1}-a_n\)
\(a_n=C_1(\dfrac {5+\sqrt{21}} {2})^n+C_2(\dfrac {5-\sqrt{21}} {2})^n\)
\(a_n=(\dfrac {5+\sqrt{21}} {2})^n+(\dfrac {5-\sqrt{21}} {2})^n\)
所以\(a_0=2,a_1=5\)
然后用
\(a_{n+2}=5a_{n+1}-a_n\)，在加的时候不断模10算出来它的循环节就可以了
还有一个例子：
求所有的数对\((p,n)\),满足\(p^n\)=\(n^p\),\(p\)是质数，\(n\)是正整数
假设\(n=p^x\),所以\(p^n=p^{xp}=np\)
\(p^n=p^{p^x}\)
\(p^{xp}=p^{p^x}\)
所以\(xp=p^x \to x=p^{x-1}\)
但是我们观察到$n=p \space or \space n=2,p=4 $（或者相反）就可以了
更多的例子：
n是一个偶数，给定一个n*n的矩阵B，\(B_{i,j}=(i+j) \space mod \space n\)
选出尽量多个格子，使得其中任意两个格子不在同一行，不在同一列，格子中的元素不同
给出方案
还有：
\(M(a)\)表示使\((a+b)|ab\)为的正整数的b的个数
求\(M(a)\)
设\(\dfrac {ab} {a+b}=c\)
然后\(ab=ac+bc\)
\(ab-ac-bc=0\)
\(ab-ac-bc+a^2=a^2\)
\((a-c)(a+b)=a^2\)
所以我们就结束了
\(ans=\dfrac {d_0(a^2)-1}2\),\(d_0(x)\)为x约数的个数
如何求\(a^2\)的约数个数
\(d_0(12)=(2+1)*(1+1)=6\)
然后\(d_0(12^2)=(4+1)*(2+1)=15\)
然而还有：
一次考试有m道题目，有n个同学参加
如果某道题目正好有x个同学没有答对，那么答对的所有同学得x分
求第一名的分数和最后一名分数之和的最大值
可以很容易看出最大值为m*(n-1)
平面上有2n个点，没有三点共线，任意两点之间连线段
将其中\(n^2+1\)条边染成红色，剩下的边染成蓝色
求同色的三角形最多有多少个？
矩阵的相关概念
若矩阵A，向量x，数\(\lambda\)满足：
\(Ax=\lambda x\)则称$\lambda \(为\)A\(的特征值，\)x\(为\)\lambda\(相对应的\)A$的特征向量
求解方法：
\((A-\lambda I)x=0\)先求解\(|A-\lambda I|=0\)再求解方程
如果\(AB=I\),则A,B互为对方的逆，记为\(B^{-1},A^{-1}\)
求解方法：通过矩阵变换将\([A|I]\)消成\([I|B]\)，则\(B=A^{-1}\)
矩阵的对角化：（三角矩阵\(O(n^3)\)）的矩阵快速幂
\(A=P^{-1}DP\)，其中\(D\)为对角矩阵
(D中元素为A的特征值，P为相对应的特征的向量矩阵)