100个著名初等数学问题

上网课ing。。。有点没意思，翻出来以前的书看了看，《100个著名初等数学问题 历史和解》

---

第1题分牛

比较厉害的列方程。。。

丢番图方程组or费马方程

---

第2题砝码问题

本身不难，有一些延伸问题

比如$k$个砝码称出$1\sim n$的砝码选择方案数，合法方案有没有可能任意$k-1$个砝码都没法称出来一个前缀？

其实就是若干多项式相乘，研究其最终结果的系数，变化很多：问题域的变化（多项式指数的范围），询问的变化（已知元素询问某特殊性质的数，已知条件求可行的元素组成方案数……）

整数对乘法没有逆元真的是好麻烦啊。。。一堆很像背包问题的问题（丢番图方程？）都不好搞了。。。

---

第3题草地与母牛

高等数学降维打击。。。行列式为0。。。

---

第4题7个7

虫食算？手玩的话基本就是一堆逻辑推理吧

---

第5题十五女学生问题

不会。。。只会$3^n$女学生问题（三个齿轮即可递归解决）。。。

数论问题，貌似是同余+构造，暂置

---

第6题错排问题

首先按照逻辑推理可以得到$f_n=(n-1)(f_{n-1}+f_{n-2})$（为计算$f_n$，考虑元素1，其共有$n-1$个位置可以放置，设放在了位置$x$，则再考虑元素$x$，有两种方案：放在位置1or不能放在位置1，方案数分别为$f_{n-2}\ or\ f_{n-1}$）

手玩$f_1=0,f_2=1$，为后文方便，通过递推公式可得$f_0=1$

一开始想直接根据递推找特征解的，找了个$kn!$然后就不会了。。。

考虑降次，凑一波$f_n-af_{n-1}=A(f_{n-1}-af_{n-2})$，$A,a$与$n$有关，则凑$f_n-a_nf_{n-1}=A(f_{n-1}-a_{n-1}f_{n-2})$，得$f_n-nf_{n-1}=-1*(f_{n-1}-(n-1)f_{n-2})$（书中写$A=-1$的平方根？应该写错了）

则$f_n=nf_{n-1}+(-1)^n$

书上两边除$n!$再展开即可。。。唉。。。当时觉得有规律结果暴力展开了。。。最后得到：

$\displaystyle f_n=(-1)^n\sum_{k=0}^n{\bigl(^n_k\bigr)(-1)^kk!}$（其实可以没有之前步骤，直接容斥得到该式子$\displaystyle f_n=\sum_{k=0}^n{(-1)^k\big(^n_k\big)(n-k)!}$）

$\displaystyle f_n=\sum_{k=0}^n{\bigl(^n_k\bigr)(-1)^{n-k}k!}=\sum_{k=0}^n{\bigl(^n_k\bigr)g_{n-k}h_k}=(\xi-1)^n$

$\xi$代表算子或者记号$\xi^n=n!$

同时$\displaystyle (-1)^nf_n=\sum_{k=0}^n{\bigl(^n_k\bigr)(-1)^kk!}$，即$\displaystyle h_n=\sum_{k=0}^n{\bigl(^n_k\bigr)g_k}$

二项式反演（容斥）得到$\displaystyle g_n=\sum_{k=0}^n{\big(^n_k\big)(-1)^kh_k}$

即$\displaystyle n!=\sum_{k=0}^n{\big(^n_k\big)f_k}$，$\displaystyle f_n=n!-\sum_{k=0}^{n-1}{\big(^n_k\big)f_k}$

---

第7题多边形剖分问题

以前见过，所以知道递推公式的推导思路。。。$\displaystyle E_n=\sum_{k=2}^{n-1}E_kE_{n+1-k}$，$E_2=E_3=1$

嗯。。。然后我就用高等数学了。。。

这种类似卷积的东西上生成函数（z变换）试试，令$E_0=E_1=0$，生成函数$E=\sum E_kz^k$

则$E^2=Ez-z^3$，求解得$\displaystyle E=\frac{z}{2}(1-\sqrt{1-4z})$，直接展开就能得系数了。。。

---

第8题配偶夫妇问题

第一感觉容斥，需要解决同构的问题

但翻到最后看了一下$n$较小时候的解。。。发现不理解，怀疑理解错题

3对夫妇时我认为答案为1

---

第9题二项展开式

二项式系数的问题

二项式系数和二项式系数的按$k$前缀和都满足$\big(^n_k\big)=\big(^{n-1}_{k-1}\big)+\big(^{n-1}_k\big)$

差别只是初值不同，感觉可以用傅里叶变换搞搞

---

第10题柯西均值不等式

$\displaystyle \frac{1}{n}\sum a_i\geq (\prod a_i)^{1/n}$

高等数学：1、归纳+求导；2、$f(x)=lnx$的琴生不等式$E[f(x)]\leq f[E(x)]$

初等数学：1、2次幂归纳+反向；2、辅助定理+对方案归纳

如果改成权重向量，则高等数学比较容易解决

指数不等式由有理真分数推广到无理真分数时用到的“如此接近”“非常小的数”真的不算高等数学吗。。。

---

第11题伯努利系数

这个确实有点厉害。。。

能看懂，但自己得不到，以后再看

---

第12题自然常数

这两个数列是真的厉害。。。

$a_n=\displaystyle (1+\frac{1}{n})^n=(\frac{n}{n+1})^{-n}=(1-\frac{1}{n+1})^{-n}\overset{\text{let m=-(n+1)}}{=}(1+\frac{1}{m})^{m+1}=b_{-(n+1)}$

$\displaystyle \lim_{n\to\infty}a_n=\lim_{n\to\infty}b_{-n}=\lim_{n\to-\infty}{b_n}$

令$\displaystyle n=\frac{1}{t}$，那么$a_n,b_n$其实就是一个$0^+$一个$0^-$去逼近$e$

$\displaystyle \frac{a_{n+1}}{a_n}=(1-\frac{1}{(n+1)^2})^n(1+\frac{1}{n+1})>(1-\frac{n}{(n+1)^2})(\frac{n+2}{n+1})=\frac{(n+1)^3+1}{(n+1)^3}>1$，$a_n$递增

直接证$b_n$递减的话可以指数不等式放小第二项$\displaystyle (1+\frac{1}{n+1})=1+(n+1)(1+\frac{1}{(n+1)^2}-1)<(1+\frac{1}{(n+1)^2})^{n+1}$

书中证明单调性是直接用指数不等式，指数为有理式$p/q$则不等式两边都是指数的形式

$\displaystyle e^x=\lim(1+\frac{1}{n})^{nx}=\lim(1+\frac{x}{n})^n$

另外$\displaystyle \lim_{n\to\infty}(1+\frac{x}{n})^{n+k}=e^x,k\in Z$，可据此证$(e^x)’=e^x$