【全程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为相对应的特征的向量矩阵)