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)

对上面的递推式用累乘法，发现一些事情：

那么就得到P(\left\{a_n\right\})=\frac{S_n!(n-S_n)!}{(n+1)!}。

上述几条结论不能推出来也没关系。“举例是理解的试金石”，我们不妨算一下01序列010010的概率。

$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}

于是就证完了……

（四）