使用并查集(union-find)数据结构，编写程序通过蒙特卡罗模拟(Monte Carlo simulation)来估计渗透阈值。

本校大三课程「离散数学」的同步笔记，已更新「6.1 代数结构」，「6.2 子代数」，「6.3」同态，「6.4」同余，「6.5」商代数，「6.6 半群与独异点」，「6.7 群」，「7.1 格与布尔代数」（更新中）。

前言

这个问题在高中生物中，并不会研究的那么深刻。

所以正式做题时还是应该按照老师的教导，避开这个“雷区”。

1.问题发现

在高中生物-遗传与进化-基因的本质学习中，有一个十分经典的问题。

即：给定碱基对数n，不限定每种碱基(A,C,G,T)的个数，求出最多的DNA种数。

在所有的教材，辅导书，以及老师的授课过程中，对于这个问题的答案，一般都是$4^{n}$或者$ \frac {4^n} {2}$。

对于$4^n$的思路，即每个位置有$4$种碱基对可能，一共有$n$组，根据乘法原理，故为$4^{n}$。

对于$\frac {4^n} {2}$的思路，即在上一种思路的基础上，考虑到有重复的情况，便除了个2​。

但是，@thorn,@opethrax以及本人的对于这些答案深感怀疑，于是我们便手算了当碱基对数为$2$时的所有情况。

利用计算机程序进行打表，以及查询有关$DNA$的资料后，最终我们确定当n=2时，结果理应为10​。

这个答案都不能用上面的公式解答，于是我们继续思考探索。

2.深入探究

通过@opethrax同学辛苦的打表，观察，他发现存在一些情况被忽略。

原先我们认为，一个$DNA$分子拥有$3’$与$5’$段，$3$代表三号碳，$5$代表五号碳。

如下图，从两条链的$3’$端分别扫描，一种序列最多被统计到$2$次。

一个是AGCTA​，另一种是TAGCT。

但是，存在一种$DNA$分子，从其两条链的$3’$端分别扫描，结果相同。

如下图：

都为TCGATCGA。

所以这种情况下，具有这种性质的$DNA$会被少统计一次。

且我们不难发现，满足这种性质当且仅当$DNA$链的长度为偶数（如图一，若为奇数，会出现不对称的情况，即不满足这种性质）。

那么我们分类讨论，之前那个$\frac {4^n} {2}$的公式，可以在n​为奇数时使用。

对于n​为偶数的情况，我们要在原公式的基础上，加上少统计的个数。

现在的问题，即是寻找拥有这种特殊性质的链的个数。

不难发现，一条链的$3’$端的$1$号碱基到该链的第$\frac n 2$号碱基，如果和另一条链的$3’$端的$1$号碱基到该链的第$\frac n 2$号碱基相同，剩下的部分通过碱基互补配对原则，可以保证相同。

下图黑的部分是我们自己确定的一条排列，红色部分是根据碱基互补配对原则形成的。

我们可以把这个理解为一种中心对称。

所以我们只需要构造出一条链中一半的排列，然后按照中心对称放到另一条链的$3’$端，剩下那条按照碱基互补配对原则填充即可满足这种性质。

所以我们不难得出，这种情况下，会有$4^{\frac {n}{2}}$条链会被少统计一次。

至此，我们可以得出公式：
$$
a_n=\begin{cases}\frac{4^n}{2}\ \ \ \ \ \ \ \ n=2k+1\\frac{4^n+4^{\frac{n}{2}}}{2}\ n=2k\ \ (k\in N^*)\end{cases}
$$
这个式子经过打表以及oeis.org的确认，结果正确。

3.声明与感谢

其实$DNA$的结构远比人类脑海中想象的要复杂的多，这里我们只是讨论了理论下的情况。

感谢您的阅读。若您存在任何疑问，或觉得我们有些地方存在纰漏，欢迎您联系我们，我们十分乐意与您探讨。

再次感谢两位同学@thorn,@opethrax深夜的探讨与陪伴，若没有他们的帮助，我们很难单独进行下去。

thorn有关这篇文章的链接：https://www.cnblogs.com/thornblog/p/12381381.html

opethrax有关这篇文章的链接：https://home.cnblogs.com/u/opethrax/

他们两位有关这个内容的博客写的都非常优秀，建议您去访问他们的博客以进行更多的了解。

除非另有说明，本网站上的内容均采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可，请您在转载时注明来源及博客链接。

4.深夜随想

造物主强大的力量是人们无法想象到的。人类很难走到没有任何疑惑的那一天。

每一个个体脑中冒出的新奇想法，或提出的一个问题，都有可能成为筑起人类从无知到有知的桥梁下的一粒石子。

对科学的探索，不是浅尝辄止，而是无穷无尽。

献上一首不错的音乐：

“生于此处却不知此处

日光倾城，万物生长，又是为何

若没有大地的拥抱，我们早已消失于茫茫宇宙之中

若没有原子之稳定，我们亦不复存在

无人问天地变换，斗转星移，是为何故

宇宙又是源于何处

它是否无始无终

时间若愿意倒流，我们的认知是否还会有局限

世间最渺小之物又是什么

滚滚长江，却只留有过去，不知未来

浩淼宇宙，为何我们在此相遇”
——《Moonlight》

形式

$$
\sum_{i=1}^{n}a_i^2 \sum_{i=1}^{n}b_i^2 \geq \sum_{i=1}^{n}a_i^{2}b_i^2
$$

等号成立的条件：
$$
iff:b_i=0 || \exists k \in \mathbb {R},a_i=k \cdot b_i(i \in \mathbb{N^+})
$$

证明

法一：参数配方

思路：巧妙的把常数与方程结合起来，利用性质即可。

证明：

构造函数:
$$
f(t)=\sum_{i=1}^{n}b_i^2\cdot t^2-2\sum_{i=1}^{n}a_ib_it+\sum_{i=1}^{n}a_i^2
$$
化简函数：
$$
f(t)=\sum_{i=1}^{n}b_i^2\cdot t^2-2\sum_{i=1}^{n}a_ib_it+\sum_{i=1}^{n}a_i^2
$$

$$
=\sum_{i=1}^{n}(b_i^2t^2-2a_ib_it+a_i^2)
$$

$$
=\sum_{i=1}^{n}(b_i^2t^2+a_i^2-2a_ib_it)
$$

$$
=\sum_{i=1}^{n}(b_it-a_i)^2
$$

所以：
$$
f(t) \geq 0
$$

$$
\Delta t=b^2-4ac
$$

$$
=4\sum_{i=1}^{n}a_i^2b_i^2-4\times \sum_{i=1}^{n}b_i^2 \times \sum_{i=1}^{n}a_i^2 \leq 0
$$

所以：
$$
4\sum_{i=1}^{n}a_i^2b_i^2 \leq 4\times \sum_{i=1}^{n}b_i^2 \times \sum_{i=1}^{n}a_i^2
$$

$$
\sum_{i=1}^{n}a_i^2 \times \sum_{i=1}^{n}b_i^2 \geq \sum_{i=1}^{n}a_i^2b_i^2
$$

证毕。

因为：
$$
f(t)=\sum_{i=1}^{n}(b_it-a_i)^2
$$
令$f(t)=0$，即
$$
a_i=b_it
$$
此时：
$$
f(t)_{min}=0​
$$
即：
$$
\Delta t \leq 0
$$
故等号可取的一个充分条件即为：
$$
\exists k \in \mathbb {R},a_i=k \cdot b_i(i \in \mathbb{N^+}）
$$

法二：均值不等式证明

思路：运用分析法将原式子化简，使用绝对值三角不等式与均值不等式进行证明。

引用到的均值不等式（证明略）：
$$
ab \leq \frac{a^2+b^2}{2}
$$
适用条件：
$$
a,b \in \mathbb {R^+}
$$
等号成立条件：
$$
iff:a=b
$$

证明：

要证：
$$
\sum_{i=1}^{n}a_i^2\sum_{i=1}^{n}b_i^2 \geq \sum_{i=1}^{n}a_i^{2}b_i^2
$$
只需证：
$$
\sqrt {\sum_{i=1}^{n}a_i^2 \sum_{i=1}^{n}b_i^2} \geq |\sum_{i=1}^{n}a_ib_i|
$$
即：
$$
|\sum_{i=1}^{n}a_ib_i| \leq \sqrt {\sum_{i=1}^{n}a_i^2 \sum_{i=1}^{n}b_i^2}
$$

$$
\frac{|\sum_{i=1}^{n}a_ib_i|}{\sqrt {\sum_{i=1}^{n}a_i^2 \sum_{i=1}^{n}b_i^2}}\leq 1
$$

由绝对值三角不等式：
$$
|a_1+a_2+a_3+\cdots+a_n| \leq |a_1|+|a_2|+|a_3|+ \cdots + |a_n|
$$
可得：
$$
|\sum_{i=1}^{n}a_ib_i| \leq \sum_{i=1}^{n}|a_ib_i|
$$
所以：
$$
\frac{|\sum_{i=1}^{n}a_ib_i|}{\sqrt {\sum_{i=1}^{n}a_i^2 \sum_{i=1}^{n}b_i^2}} \leq \frac{\sum_{i=1}^{n}|a_ib_i|}{\sqrt {\sum_{i=1}^{n}a_i^2 \sum_{i=1}^{n}b_i^2}}
$$
又因为：
$$
\frac{\sum_{i=1}^{n}|a_ib_i|}{\sqrt {\sum_{i=1}^{n}a_i^2 \sum_{i=1}^{n}b_i^2}}
$$

$$
=\sum_{i=1}^{n}\frac{|a_i|}{\sqrt{\sum_{i=1}^{n}a_i^2}}\cdot \frac{|b_i|}{\sqrt{\sum_{i=1}^{n}b_i^2}}
$$

由均值不等式：
$$
ab \leq \frac{a^2+b^2}{2}
$$
可得：
$$
\sum_{i=1}^{n}\frac{|a_i|}{\sqrt{\sum_{i=1}^{n}a_i^2}}\cdot \frac{|b_i|}{\sqrt{\sum_{i=1}^{n}b_i^2}}
$$

$$
\leq \frac{1}{2}\cdot \sum_{i=1}^{n}(\frac{a_i^2}{\sum_{i=1}^{n}a_i^2}+ \frac{b_i^2}{\sum_{i=1}^{n}b_i^2})
$$

$$
\leq \frac{1}{2}\cdot (\frac{\sum_{i=1}^{n}a_i^2}{\sum_{i=1}^{n}a_i^2}+ \frac{\sum_{i=1}^{n}b_i^2}{\sum_{i=1}^{n}b_i^2})
$$

$$
\leq \frac{1}{2} \times 2 = 1
$$

即：
$$
\frac{|\sum_{i=1}^{n}a_ib_i|}{\sqrt {\sum_{i=1}^{n}a_i^2 \sum_{i=1}^{n}b_i^2}}\leq 1
$$
上述结论成立，证毕。

法三：n维向量证法

因为：
$$
|\vec a \cdot \vec b| = |\vec a|\cdot |\vec b| \cdot cos \theta
$$
所以：
$$
|\vec a \cdot \vec b| \leq |\vec a|\cdot |\vec b|
$$

$$
|\vec a \cdot \vec b|^2 \leq |\vec a|^2\cdot |\vec b|^2
$$

$\vec a,\vec b$为$n$维向量时，用坐标的形式展开即可证明。

当$\vec a=k\vec b$，即$a$，$b$共线时，等号成立。

申明与感谢

• 内容采用“知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议”进行许可。请您在转载时注明来源及链接。
• 感谢@thorn的审稿。