Sweetlemon蒟蒻的拙作

### （一） 开学了，高一(21)班共有$n (n\in \mathbb{N^{*}})$名同学，他们的学号分别是$1,2,\cdots,n$。班主任为了让同学们相互认识，想了一个好办法。 他在一次班会课上说：“同学们，如果你的学号是$x$，而另一个同学的学号是$y$，并且$x+y=2^{k}+2(k\in \mathbb{N})$，那么你们之间就有缘分。现在请你和所有与你有缘分的同学握手吧！” (1) 当$n=30$时，求所有与$5$号同学握手的同学的学号。 (2) 求同学们握手的总次数。 (3) 班主任的办法很有效，握过手的两名同学**互相**成为了朋友。而且这种朋友关系还具有传递性，即如果甲、乙是朋友，乙、丙是朋友，那么甲、丙也是朋友。现在21班要组建一个团队参加比赛，为了保证团队的团结，要求团队中任意两人都是朋友。求团队中人数的最大值。 --- 题解： (1) $n=30$时，握手关系如下图：  因此所有与$5$号同学握手的同学的学号所组成的集合为$\left \{ 1,13,29 \right\}$。 (2) 把$1$号同学称为“根”~~（可以理解为“全班的希望”）~~。 设$x$为集合$A=\left \{ x\in \mathbb{N} \mid 1<x\le n \right\}$中的任意元素。对于某一个$x$，设$y$是集合$\left \{ y\in \mathbb{N} \mid 1\le y< x \right\}$中的某个元素，且有$x+y=2^{k}+2(k\in \mathbb{N})$。如果存在这样的$y$，那么我们称$y$为$x$的“父亲”~~（$\sout{x}$被$\sout{y}$打败了，被迫承认的）~~。 下面我们证明，对于$A$中的每一个元素，都有且仅有$1$个父亲~~（废话，你还能认两个人作父亲？）~~。 整数$y$是$x$的父亲当且仅当$0<y<x$且$x+y=2^k+2$。 上述条件成立，当且仅当存在一个自然数$k$，使得$0<2^k+2-x<x$。调整得到$x<2^k+2<2x$，即$x-2<2^k<2x-2$。 下面证明对于每一个$x$，有且只有一个自然数$k$满足上式。 设$$x-2=2^{a_1}+2^{a_2}+\cdots+2^{a_n}$$ 其中 $a_1>a_2>\cdots>a_n,\left\{a_1,a_2,\cdots,a_n\right\}\subseteq \mathbb{N}$。 则$$x-2=2^{a_1}+2^{a_2}+\cdots+2^{a_n}\le 2^{a_1}+2^{a_1-1}+2^{a_1-2}+\cdots+2^{1}+2^{0}<2^{a_1+1}$$ 而$2x-4=2(x-2)=2^{a_1+1}+2^{a_2+1}+\cdots+2^{a_n+1}\ge 2^{a_1+1}$。 于是$x-2<2^{a_1+1}\le 2x-4$，知$x-2<2^{a_1+1}<2x-2$，知存在$k=a_1+1$使得上式成立。 再证明$a_1+1$是唯一满足条件的$k$。 若有$k'<a_1+1$满足上式，那么由$k'\in \mathbb{N}$知$k'\le a_1$，则$2^{k'}\le 2^{a_1}\le x-2$，与上式矛盾。 若有$k'>a_1+1$满足上式，那么由$k'\in \mathbb{N}$知$k'\ge a_1+2$，则$2^{k'}\ge 2^{a_1+2}>2^{a_1+1}+2^{a_1}+2^{a_1-1}+\cdots+2^1+2^0$。 而$2x-4=2^{a_1+1}+2^{a_2+1}+\cdots+2^{a_n+1}<2^{a_1+1}+2^{a_1}+2^{a_1-1}+\cdots+2^1+2^0$（此处请注意因为$a_1>a_2>\cdots>a_n\ge0$，所以$a_1+1>a_2+1>\cdots>a_n+1\ge1$。） 于是有$2^{k'}>2x-4$。 然而，若$x-2<2^{k'} <2x-2$，则有$2^{k'}<2x-2$，由$2^{k'}\in \mathbb{N}$知$2^{k'}=2x-3$，且由于$k'>a_1+1\ge1$知$2^{k'}$一定是偶数，出现矛盾。 综上，$a_1+1$是唯一满足条件的$k$。 由此，我们得出，对于$A$中的每一个元素，都有且仅有$1$个父亲。 考虑每一次握手，设握手的两人分别为$x$和$y$，不妨设$x>y$，则由上面的结论知$y$是$x$的父亲，因此每一次握手都仅在一个人和他的父亲之间发生~~（“发生”这个词好恐怖）~~，且学号大于$1$的每个人都会和他的父亲握手。 有多少对父子关系就有多少次握手。$1$没有父亲，而所有学号大于$1$的人都有父亲，因此同学们握手的总次数为$n-1$。 (3) 我们设$1$的祖先为$1$本身~~（我 生 我 自 己）~~，其余点的祖先定义为它父亲的祖先。（可以看上面的图帮助理解，按照图上的箭头反向往上走，走到最上面就是祖先。也可以理解为祖先是父亲的父亲的父亲的……父亲的父亲。） 用符号语言来表示，记一个人的父亲为$\text{par}(x)$，记一个人的祖先为$\text{gpar}(x)$。那么若$x=1$，则$\text{gpar}(x)=1$；否则$\text{gpar}(x)=\text{gpar}(\text{par}(x))$。如$\text{gpar}(2)=\text{gpar}(\text{par}(2))=\text{gpar}(1)=1$。 由父亲和祖先的定义知，一个人和他的祖先一定有朋友关系~~（怎么看着怪怪的）~~。 观察上面的图，我们发现图上每一个人的祖先都是$1$！这是不是巧合呢？ 事实上，我们可以证明，任意满足$1\le x\le n$的整数的祖先都是$1$。 怎么证明呢？我们可以 ~~感性理解~~ 用数学归纳法。 首先，当$x=1$时，按照定义，欲证命题显然成立。 接着，我们设当$x\le k$时欲证命题成立，即“任意满足$1\le x\le k$的整数的祖先都是$1$”成立。下面我们要证明当$x=k+1$时命题也成立。 由(2)，$\text{par}(k+1)<k+1$，由于$\text{par}(k+1)\in \mathbb{N}$，知$\text{par}(k+1)\le k$，由归纳假设知$\text{gpar}(\text{par}(k+1))=1$。由祖先的定义知$\text{gpar}(k+1)=1$，即欲证命题在$x=k+1$时也成立。 根据数学归纳法，对任意满足$1\le x\le n$的整数，$\text{gpar}(x)=1$。 （由于我们还没有学过数学归纳法，因此这段证明过程在实际书写时可以略微 ~~意会~~ 调整。） 于是，每一个人都和$1$号同学是朋友。由朋友关系的传递性，全班同学都彼此是朋友。因此团队中人数的最大值为$n$。 这道题解完了，我们有什么收获呢？ 我们要向高一(21)班的同学学习，让我们的班集体变得更团结~~，变得更团结的方式就是彼此认父亲，并发生握手关系~~。 --- ### （二） 有一个有限集$S=\left\{ a_1,a_2,a_3,\cdots, a_n\right\}$，并且设$A=\left \{x\mid x\subseteq S\right \}$。 现在已知映射$f_0:A\rightarrow \mathbb{R}$，设$A$上的映射$f_1,f_2,\cdots,f_n$， 对所有$1\le k\le n$的整数$k$，满足以下条件： $$\forall x\in A \ \ \wedge \ \ a_k\notin x,\ \ f_{k}(x)=f_{k-1}(x)$$ $$\forall x\in A\ \ \wedge \ \ a_k\in x,\ \ f_k(x)=f_{k-1}(x)+f_{k-1}(\complement_{\left\{ a_{k} \right\} }x)$$ 请写出$f_{n}(S)$的值并给出证明。 --- ### （三） 有一个游戏，初始时$A=\left\{0\right\},B=\left\{-1\right\}$。游戏有$n$次操作，第$k(1\le k\le n)$次会从$A\cup B$中等概率随机选择一个数$x$，如果设这个数$x$所在的集合为$S(S\in \left\{A,B\right\})$，那么这次操作会将$S$变为$S\cup \left\{k\right\}$。求这$n$次操作后，$A$集合的元素数量是$t(1\le t\le n+1)$的概率。 ---- #### 题解 此概率与$t$无关，都为$\frac{1}{n+1}$。 有几种证明方法： ##### 数学归纳法 设$g[i][j]$为进行了$i$次操作，$A$集合中有$j$个数的概率。 则$g[0][1]=1=\frac{1}{0+1}$，初始条件满足。 $\begin{aligned}g[i][j]&=\frac{j-1}{i-1+2}g[i-1][j-1]+\frac{(i-1+2)-j}{i-1+2}g[i-1][j]\\&=\frac{1}{i+1}((j-1)g[i-1][j-1]+(i+1-j)g[i-1][j])\end{aligned}$ 此时若有$g[i-1][x]=\frac{1}{i}$（归纳假设），则 $\begin{aligned}g[i][j]&=\frac{1}{i+1}((j-1)g[i-1][j-1]+(i+1-j)g[i-1][j])\\&=\frac{1}{i+1}(j-1+i+1-j)\frac{1}{i}\\&=\frac{1}{i+1}\end{aligned}$ 因此根据数学归纳法证毕。 ##### 臆想法 这一种方法需要很强的臆想能力。 把“选到的数在$A$中”记为$1$，“选到的数在$B$中”记为$0$。那么$n$次操作可以记为一个$01$序列，不妨记为$\left\{a_n\right\}$。记$\left\{a_n\right\}$的前$n$项和为$\left\{S_n\right\}$。令$S_0=0$。 我们首先计算“操作序列恰好是某个（确定的）$\left\{a_n\right\}$”的概率，记为$P(\left\{a_n\right\})$。 设$g[i]$为“前$i$个操作恰好为$\left\{a_n\right\}$的前$i$项”的概率，那么$P(\left\{a_n\right\})=g[n]$。 令$g[0]=1$。下面考虑$g[i]$的递推式。 $g[i]=\begin{cases}\frac{S_{i-1}+1}{i+1}g[i-1],\ a_i=1,\\ \frac{i-S_{i-1}}{i+1}g[i-1],\ a_i=0\end{cases}(i\ge 1)$ 对上面的递推式用累乘法，发现一些事情： - $g[n]$的分母一定是$2\times 3\times 4\times\cdots\times (n+1)=(n+1)!$ - 假设$a_i$之后下一个为$1$的项是$a_{i'}$，那么 $S_{i'-1}=S_{i-1}+1$。而$i$项的分子是 $S_{i-1}+1$，$i'$项的分子是 $S_{i'-1}+1=S_{i-1}+1+1$，知$i'$项的分子恰好比$i$项的分子多$1$。所以所有$a_i=1$项的分子是从$1$逐个递增到$S_n$的，所有$a_i=1$项的分子的乘积是$S_n!$ - 假设$a_i$之后下一个为$0$的项是$a_{i'}$，那么 $S_{i'-1}=S_{i-1}+(i'-1-i)$。而$i$项的分子是 $i-S_{i-1}$，$i'$项的分子是 $i'-S_{i'-1}=i'-(S_{i-1}+(i'-1-i))=i-S_{i-1}+1$，知$i'$项的分子恰好比$i$项的分子多$1$。一共有$n-S_n$项为$0$，它们的分子从$1$逐个递增到$n-S_n$，于是所有$a_i=0$项的分子的乘积是$(n-S_n)!$ 那么就得到$P(\left\{a_n\right\})=\frac{S_n!(n-S_n)!}{(n+1)!}$。 上述几条结论不能推出来也没关系。“举例是理解的试金石”，我们不妨算一下$01$序列$010010$的概率。 $g[1]=\frac{1}{2}g[0]$，操作后$A$的元素数是$1$，$B$的元素数是$2$； $g[2]=\frac{1}{3}g[1]$，操作后$A$的元素数是$2$，$B$的元素数是$2$； $g[3]=\frac{2}{4}g[2]$，操作后$A$的元素数是$2$，$B$的元素数是$3$； $g[4]=\frac{3}{5}g[3]$，操作后$A$的元素数是$2$，$B$的元素数是$4$； $g[5]=\frac{2}{6}g[4]$，操作后$A$的元素数是$3$，$B$的元素数是$4$； $g[6]=\frac{4}{7}g[5]$，操作后$A$的元素数是$3$，$B$的元素数是$5$. 把式子乘起来得到$g[6]=\frac{1\times 1\times 2\times 3\times 2\times 4}{2\times 3\times 4\times 5\times 6\times 7}=\frac{(1\times 2\times 3\times 4)\times (1\times 2)}{2\times 3\times 4\times 5\times 6\times 7}$ 我们只是把$0$的分子和$1$的分子分开，就得到了结论。 或者，我们可以这么理解：概率的分子就是操作前这个集合中的元素个数。如果$A$集合要从$1$个元素变到$u+1$个元素（即序列中有$u$个$1$），必然经历了$1\rightarrow 2,2\rightarrow 3,\cdots,u\rightarrow u+1$的过程，这些过程中概率的分子之积自然是$u!$。$B$集合也是一样。 不管如何，我们现在得到了——操作序列是某个“含有$u$个$1$”的$01$串的概率是$\frac{u!(n-u)!}{(n+1)!}$（为方便描述，将上面推导过程中的$S_n$用$u$代替了）。从式子中我们发现，所有“含有$u$个$1$”的$01$串的概率是相等的。 当$u=t-1$时，操作结束后，$A$的元素数就是$t$。于是，“操作结束后，$A$的元素数就是$t$”的概率，就等于所有“含有$u$个$1$”的$01$串的概率之和。（这里用的是概率的加法原理，因为这些$01$串两两互斥（操作序列不可能同时为两个$01$串），且总事件全部由这些分事件所组成，因此可以这么计算。） 有多少“含有$u$个$1$”的$01$串呢？这是经典的子集问题，显然有$\mathrm{C}_n^u=\frac{n!}{u!(n-u)!}$个。 神奇的事情发生了——把$01$串数和每个$01$串的概率乘起来： $$\frac{n!}{u!(n-u)!}\times \frac{u!(n-u)!}{(n+1)!}=\frac{n!}{(n+1)!}=\frac{1}{n+1}$$ 于是就证完了…… ### （四） $A$ 是非空有限集，且对于 $A$ 的所有非空子集 $S$，均有 $\left\{\varnothing \right\}\in S$ 或 $\left\{\varnothing \right\}\subseteq S$。求 $A$。