三道百子遴选考试题目及解答

解答

设共有𝑁个人．考虑三人组(𝑎_(1),𝑎_(2),𝑎_(3))，其中𝑎_(1)与𝑎_(2)、𝑎_(3)均握手．（设𝑎_(2)、𝑎_(3)为无序对）
注意到(𝑎_(1),𝑎_(2),𝑎_(3))和(𝑎_(1),𝑎_(3),𝑎_(2))是同一个三人组，但和(𝑎_(2),𝑎_(1),𝑎_(3))不是同一个三人组．
下面计算这样的三人组的个数．
由于每个人恰好与20个人握手，故对于某个确定的𝑎_(1)，有𝐶220=190个这样的三人组．
于是这样的三人组共有190𝑁个．
另一方面，全部的𝑁个人可以组成𝐶2𝑁个二人组，将这些二人组分成两类：互相握过手的（设有𝑥个）；没有握过手的（设有𝑦个）．
于是𝑥+𝑦=𝐶2𝑁．
由于每个人恰好与20个人握手，故共进行了(20𝑁)/(2)=20𝑁次握手（每次握手被计算两次）．
于是𝑥=10𝑁．
由后两个条件可知，三人组(𝑎_(1),𝑎_(2),𝑎_(3))的个数为：（按照𝑎_(2)、𝑎_(3)是否进行握手分类）

公式：\begin{align*} x+6y=&10N+6\left(C_N^2-10N\right)\\=&3N(N-1)-50N \end{align*}

于是

即3(𝑁−1)=240．
于是𝑁=81，即参加晚会的共有81人．

S8第9题

𝑛为不小于2的正整数，求证：

公式：\sum\limits_{1\leq i< j\leq n}\dfrac{i+2ij+j}{\sqrt{(i+1)(j+1)}}<\dfrac{n(n^2-1)}{2}\text{．}

证明

由柯西不等式，𝑛≥2时，有

公式：\left(\sum\limits_{i=1}^n\sqrt{i+1}\right)^2< n\sum\limits_{i=1}^n(i+1)=\dfrac{n^2(n+3)}{2}

以及

公式：\begin{align*} &\left(\sum\limits_{i=1}^n\sqrt{i+1}\right)\left(\sum\limits_{i=1}^n\dfrac{1}{\sqrt{i+1}}\right)\\ >&\left(\sum\limits_{i=1}^n\sqrt{i+1}\cdot\dfrac{1}{\sqrt{i+1}}\right)^2\\ =&n^2 \end{align*}

于是

公式：\begin{align*} &\sum\limits_{1\leq i< j\leq n}\dfrac{i+2ij+j}{\sqrt{(i+1)(j+1)}}\\ =&\sum\limits_{1\leq i< j\leq n}\left(i\sqrt{\dfrac{j+1}{i+1}}+j\sqrt{\dfrac{i+1}{j+1}}\right)\\ =&\sum\limits_{i=1}^n\sum\limits_{j=1}^ni\sqrt{\dfrac{j+1}{i+1}}-\sum\limits_{k=1}^nk\\ =&\left(\sum\limits_{i=1}^n\sqrt{j+1}\right)\cdot\left(\sum\limits_{i=1}^n\left(\sqrt{i+1}-\dfrac{1}{\sqrt{i+1}}\right)\right)-\dfrac{n(n+1)}{2}\\ <&\dfrac{n^2(n+3)}{2}-n^2-\dfrac{n(n+1)}{2}\\ =&\dfrac{n(n^2-1)}{2}\text{．} \end{align*}

S9、10第3题

设公式：f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_2x^2+a_0的所有系数均为正整数，且次数𝑛≥2．数列{𝑏_(𝑛)}满足：𝑏_(1)=𝑎_(0)，𝑏_(𝑛+1)=𝑓(𝑏_(𝑛))．求证：对于任意正整数𝑛≥2，存在素数𝑝满足𝑝∣𝑏_(𝑛)，𝑝∤𝑏_(1)𝑏_(2)⋯𝑏_(𝑛−1)．

证明

使用反证法．假设存在一个正整数𝑛≥2，使得𝑏_(𝑛)的所有素因子均为𝑏_(1)、𝑏_(2)、⋯、𝑏_(𝑛−1)之一的素因子．设𝑞为𝑏_(𝑛)的任意一个素因子，𝑏_(𝑛)=𝑞^(𝑟)𝑙，其中gcd(𝑞,𝑙)=1．于是

公式：\begin{align*} b_{n+1}=&f(b_n)\\ =&a_n\left(q^rl\right)^n+a_{n-1}\left(q^rl\right)^{n-1}+\cdots+a_2\left(q^rl\right)^2+a_0\\ \equiv&a_0=b_1({\rm{mod}}\ q^{r+1}) \end{align*}

接下来，可以用数学归纳法证明：

对于任意正整数𝑖，都有𝑏_(𝑛+𝑖)≡𝑏_(𝑖)(mod𝑞^(𝑟+1))．
这是由于

公式：b_{n+k+1}=f(b_{n+k})\equiv f(b_k)=b_{k+1}({\rm{mod}}\ q^{r+1})\text{．}

于是有

公式：b_n\equiv b_{2n}\equiv \cdots\equiv b_{kn}({\rm{mod}}\ q^{r+1})\text{．}

记𝑣_(𝑝)(𝑛)为𝑛的素因数分解中素数𝑝的指数，则𝑣_(𝑞)(𝑏_(𝑛))=𝑟． 因此

公式：v_q(b_n)=v_q(b_{2n})=\cdots=v_q(b_{kn})=r\text{．}

由假设知，必存在正整数𝑖（1≤𝑖≤𝑛−1），使得𝑞∣𝑏_(𝑖)．重复上面的过程可以得到：

公式：v_q(b_i)=v_q(b_{2i})=\cdots=v_q(b_{ni})

于是有公式：v_q(b_i)=v_q(b_{ni})=v_q(b_n)=r．这表明对于𝑏_(𝑛)的所有素因子𝑞，其在𝑏_(𝑛)中的次数与在𝑏_(1)、𝑏_(2)、⋯、𝑏_(𝑛−1)之一中的次数相等．即𝑏_(𝑛)∣𝑏_(1)𝑏_(2)⋯𝑏_(𝑛−1)．
于是有𝑏_(𝑛)≤𝑏_(1)𝑏_(2)⋯𝑏_(𝑛−1)．又𝑏_(𝑛)=𝑓(𝑏_(𝑛−1))<𝑏2𝑛−1，即𝑏_(𝑛−1)<√(𝑏_(𝑛))．
因此

公式：b_{n-k}<\sqrt{b_{n-k+1}}<\sqrt[4]{b_{n-k+2}}<\cdots< b_n^{\frac{1}{2^k}}\text{．}

于是

公式：0< b_1b_2\cdots b_{n-1}< b_n^{\frac{1}{2^{n-1}}}b_n^{\frac{1}{2^{n-2}}}\cdots b_n^{\frac{1}{2}}< b_n\text{．}

矛盾！

因此对于任意正整数𝑛≥2，存在素数𝑝满足𝑝∣𝑏_(𝑛)，𝑝∤𝑏_(1)𝑏_(2)⋯𝑏_(𝑛−1)．