距离新定义

博客园 - Eufisky

距离新定义

Eufisky · 2024-11-08 · via 博客园 - Eufisky

%!TEX program = xelatex
%!TEX endoding = UTF-8 (utf8)
\documentclass[a4paper,fleqn]{article}
\usepackage{amsmath}
\usepackage{amssymb}%与exam-zh冲突

\usepackage{ctex}
\usepackage[dvipsnames,svgnames,x11names,table]{xcolor}
\usepackage{tikz}
\usepackage{tkz-euclide}
\usepackage[explicit]{titlesec}
\usepackage[most]{tcolorbox}
\usepackage{esvect}
\usepackage{tabularray}
\usepackage{geometry}
\geometry{%A4
paperwidth=210mm,
paperheight=297mm,
marginparsep=-1mm,
left=20mm,
right=20mm,
top=20mm,
bottom=30mm
}

\newlength{\zljxiaobiaotilength}
\titleformat{\section}
{\normalfont\Large\bfseries}
{
\begin{tikzpicture}
\path[fill=OliveGreen] (0,0)--(0,2em)--(2em,2em)--(2em,0)--(0,0);
\node[white] at (1em,1em){\thesection};
\end{tikzpicture}
}
{-2em}
{
\settowidth{\zljxiaobiaotilength}{\quad~~{\bf \Large #1}~~\quad}
\begin{tikzpicture}
\draw[OliveGreen,line width=3pt] (0em,0.1em)--({1em+\zljxiaobiaotilength},0.1em);
\node at ({0em+.5\zljxiaobiaotilength},1.1em){\quad~~\color{OliveGreen}#1~~\quad};
\end{tikzpicture}
}
\tcbset{
zljTheostyle/.style={
enhanced,
breakable,
fonttitle=\sffamily\bfseries,
description font={\mdseries},
attach boxed title to top left = {
yshift=-2mm,
xshift=5mm
},
boxed title style={
sharp corners
},
}
}
%
\newtcbtheorem[number within=section]{zljTheo}{定理}
{
zljTheostyle,
colback=red!5,
colframe=red,
colbacktitle=red,
}
{zljTheo}
\newtcbtheorem[number within=section]{zljCoro}{推论}
{
zljTheostyle,
colback=SeaGreen!5,
colframe=SeaGreen,
colbacktitle=SeaGreen,
}
{zljCoro}
\newtcbtheorem[number within=section]{zljLem}{引理}
{
zljTheostyle,
colback=BurntOrange!5,
colframe=BurntOrange,
colbacktitle=BurntOrange,
}
{zljLem}
\newtcbtheorem[number within=section]{zljAxiom}{公理}
{
zljTheostyle,
colback=Maroon!5,
colframe=Maroon,
colbacktitle=Maroon,
}
{zljAxiom}
\newtcbtheorem[number within=section]{zljProp}{性质}
{
zljTheostyle,
colback=blue!5,
colframe=blue,
colbacktitle=blue,
}
{zljProp}
\newtcbtheorem[number within=section]{zljConc}{结论}
{
zljTheostyle,
colback=NavyBlue!5,
colframe=NavyBlue,
colbacktitle=NavyBlue,
}
{zljConc}
\newtcbtheorem[number within=section]{zljDef}{定义}
{
zljTheostyle,
colback=ForestGreen!5,
colframe=ForestGreen,
colbacktitle=ForestGreen,
}
{zljDef}
%
%平行四边形
\newcommand*\pxsbx{
\mathord{\text{
\tikz[baseline]
\draw (0,.1ex) -- (.8em,.1ex) -- (1em,1.6ex) -- (.2em,1.6ex) -- cycle;}
}
}

%%%%%%%%%%%%%%%

\NewTotalTColorBox[auto counter]{\Example}{ +m +m }{
notitle,
colback=blue!5!white,
colbacklower=white,
frame hidden,
boxrule=0pt,
bicolor,
breakable,%跨页显示
sharp corners,
borderline west={4pt}{0pt}{blue!50!black},
fontupper=\sffamily
}{
\textcolor{blue!50!black}{
\sffamily
\textbf{例~\thetcbcounter.}%
}%
#1
\tcblower%
\textcolor{blue!50!black}{
\sffamily
\textbf{解.}%
}%
#2
}

\usepackage{tasks}
\settasks{ %设置
label=\Alph*., %编号
label-format={\bfseries}, %加粗
%item-indent={-0.1em},
%label-offset={-0.05em}
}

\usepackage{pifont}%带圆圈数字
\everymath{\displaystyle}
\allowdisplaybreaks[4]%公式跨页

\begin{document}
\begin{center}
\LARGE\bf 新定义专题:形形色色的距离问题
\end{center}

过眼西湖无一句，易安心事岳王知。

\section{曼哈顿距离}

\textbf{曼哈顿距离}是两点在南北方向上的距离与东西方向上的距离之和,即
$$
d(A,B)=|x_A-x_B|+|y_A-y_B|,
$$
对于一个具有正南正北、正东正西方向规则布局的城镇街道,从一点到达另一点的距离正是在南北方向上旅行的距离加上在东西方向上旅行的距离.因此,曼哈顿距离又称为\textbf{出租车距离}.

\Example{
(2010年广东)设$A(x_1,y_1),B(x_2,y_2)$是平面直角坐标系$xOy$上的两点,现定义由点$A$到点$B$的一种折线距离$\rho (A,B)$为$\rho (A,B)=|x_2-x_1|+|y_2-y_1|$.对于平面$xOy$上给定的不同的两点$A(x_1,y_1),B(x_2,y_2)$.
\begin{enumerate}
\item[(I)] 若点$C(x,y)$是平面$xOy$上的点,试证明: $\rho (A,C)+\rho(C,B)\geqslant \rho(A,B)$;

\item[(II)] 在平面$xOy$上是否存在点$C(x,y)$同时满足

\ding{172} $\rho (A,C)+\rho(C,B)\geqslant \rho(A,B)$; \qquad \ding{173} $\rho (A,C)=\rho(C,B)$.

若存在,请求出所有符合条件的点;若不存在,请予以证明.
\end{enumerate}
}{
(I)证明:因为$\rho (A,C)=|x-x_1|+|y-y_1|$, $\rho (C,B)=|x_2-x|+|y_2-y|$, $\rho (A,B)=|x_2-x_1|+|y_2-y_1|$,所以
\begin{align*}
\rho \left( A,C \right) +\rho \left( C,B \right) &=\left| x-x_1 \right|+\left| y-y_1 \right|+\left| x_2-x \right|+\left| y_2-y \right|
\\
&=\left( \left| x-x_1 \right|+\left| x_2-x \right| \right) +\left( \left| y-y_1 \right|+\left| y_2-y \right| \right)
\\
&\geqslant \left| \left( x-x_1 \right) +\left( x_2-x \right) \right|+\left| \left( y-y_1 \right) +\left( y_2-y \right) \right|
\\
&=\left| x_2-x_1 \right|+\left| y_2-y_1 \right|=\rho \left( A,B \right).
\end{align*}
(II)解:注意到点$A(x_1,y_1)$与点$B(x_2,y_2)$不同,下面分三种情形讨论.

(i)若$x_1=x_2$,则$y_1\neq y_2$,由条件\ding{173}得
$$
\left| x-x_1 \right|+\left| y-y_1 \right|=\left| x_2-x \right|+\left| y_2-y \right|,
$$
即$\left| y-y_1 \right|=\left| y_2-y \right|$,所以$y=\frac{y_1+y_2}{2}$.

由条件\ding{172}得
$$
\left| x-x_1 \right|+\left| y-y_1 \right|+\left| x_2-x \right|+\left| y_2-y \right|=\left| x_2-x_1 \right|+\left| y_2-y_1 \right|.
$$
所以
$$
2\left| x-x_1 \right|+\frac{1}{2}\left| y_2-y_1 \right|+\frac{1}{2}\left| y_2-y_1 \right|=\left| y_2-y_1 \right|,
$$
所以$\left| x-x_1 \right|=0$,所以$x=x_1$.

因此,所求的点$C$为$\left( x_1,\frac{y_1+y_2}{2}\right)$.

(ii)若$y_1=y_2$,则$x_1\neq x_2$,类似于(i),可得符合条件的点$C$为$\left(\frac{x_1+x_2}{2},y_1\right)$.

(iii)当$x_1\neq x_2$且$y_1\neq y_2$时,不妨设$x_1<x_2$.

(1)若$y_1<y_2$,则由(I)中的证明知,要使条件\ding{172}成立,当且仅当$(x-x_1)(x_2-x)\geqslant 0$与$(y-y_1)(y_2-y)\geqslant 0$同时成立,故$x_1\leqslant x\leqslant x_2$且$y_1\leqslant y\leqslant y_2$.

从而由条件\ding{173},得$x+y=\frac{1}{2}(x_1+x_2+y_1+y_2)$.

此时所求点$C$的全体为
$$
M=\left\{ \left( x,y \right) \left| x+y=\frac{1}{2}\left( x_1+x_2+y_1+y_2 \right) ,x_1\leqslant x\leqslant x_2\,\mathrm{且}\, y_1\leqslant y\leqslant y_2 \right. \right\}.
$$

(2)若$y_1>y_2$,类似地由条件\ding{172}可得$x_1\leqslant x\leqslant x_2$且$y_2\leqslant y\leqslant y_1$.

从而由条件\ding{173}得$x-y=\frac{1}{2}(x_1+x_2-y_1-y_2)$.

此时所求点的全体为
$$
N=\left\{ \left( x,y \right) \left| x-y=\frac{1}{2}\left( x_1+x_2-y_1-y_2 \right) ,x_1\leqslant x\leqslant x_2\,\mathrm{且}\, y_2\leqslant y\leqslant y_1 \right. \right\}.
$$
}

\section{切比雪夫距离}

\Example{
在平面直角坐标系中,定义$d(A,B)=\max\{|x_1-x_2|,|y_1-y_2|\}$为两点$A(x_1,y_1)$、$B(x_2,y_2)$的“切比雪夫距离”,又设点$p$及直线$l$上任一点$Q$, 称$d(P,Q)$的最小值为点$p$到直线$l$的“切比雪夫距离”, 记作$d(P,l)$.

(1)求证:对任意三点$A$、$B$、$C$,都有$d(A,C)+d(C,B)\geqslant d(A,B)$;

(2)已知点$P(3,1)$和直线$l:2x-y-1=0$,求$d(P,l)$;

(3)定点$C(x_0,y_0)$,动点$P(x,y)$满足$d(C,P)=r\ (r>0)$,请求出点$P$所在的曲线所围成图形的面积.
}{
(1)证明:设$A(x_1,y_1),B(x_2,y_2),C(x_3,y_3)$,
则$d(A,C)+d(C,B)=\max\{|x_1-x_3|,|y_1-y_3|\}
+\max\{|x_3-x_2|,|y_3-y_2|\}\geqslant
|x_1-x_3|+|x_3-x_2|\geqslant |x_1-x_2|$,
同理可得
$d(A,C)+d(C,B)\geqslant |y_{1}-y_{2}|$,

所以$d(A,C)+d(C,B) \geqslant \max\{|x_1-x_2|,|y_1- y_2|\}=d(A,B)$.

(2)解:设$Q(x,2x-1)$为直线$l:2x-y-1=0$上一点,则$d( P,Q)=\max\{|x-3|,|2-2x|\}$,

由$|x- 3|\geqslant |2- 2x|$,解得$-1\leqslant x\leqslant \frac 53$,
即有$d(P,Q)=|x-3|$,当$x=\frac53$时,取得最小值$\frac 43$;

由$|x-3|<|2-2x|$,解得$x>\frac{5}{3}$或$x<-1$,即有$d(P,Q)=|2x-2|$, $d(P,Q)$的范围是$(3,+\infty)\cup\left(\frac{4}{3},+\infty\right)=\left(\frac{4} {3},+\infty\right)$,无最大值.

综上可得, $P,Q$两点的最小值为$\frac{4}{3}$,所以$d(P,l)=\frac{4}{3}$.

(3)解:设轨迹上动点为$P(x,y)$,则$d\left(C,P\right)=
\max\left\{\left|x-x_0\right|,
\left|y-y_0\right|\right\}=r$,
等价于$\begin{cases}
\left|x-x_0\right|=r,\\
\left|y-y_0\right|\leqslant\left|x-x_0\right|,
\end{cases}$
或$\begin{cases}
\left|x-x_0\right|\leqslant\left|y-y_0\right|,\\
\left|y-y_0\right|=r,
\end{cases}$
所以点$P(x,y)$的轨迹是以$C(x_0,y_0)$为中心,边长为$2r$的正方形,所以点$P$所在的曲线所围成图形的面积为$4r^2$.
}

\Example{
(2024年合肥二模)在数学中,广义距离是泛函分析中最基本的概念之一.对平面直角坐标系中两个点$P_{1}\left(x_{1},y_{1}\right)$
和$P_{2}\left(x_{2},y_{2}\right)$,记
$$\left|P_{1}P_{2}\right|_{t}=\max\left\{\frac{\left|x_{1}-x_{2}\right|}{1+\left|x_{1}-x_{2}\right|},
\frac{\left|y_{1}-y_{2}\right|}{1+\left|y_{1}-y_{2}\right|}\right\},$$
称$|P_1P_2|_t$为点$P_1$与点$P_{2}$之间的“$t-$距离”,其中$\max\{p,q\}$表示$p,q$中较大者.

(1) 计算点$P(1,2)$和点$Q(2,4)$之间的“$t-$距离”;

(2) 设$P_0(x_0,y_0)$是平面中一定点, $r>0$.我们把平面上到点$P_{0}$的“$t-$距离”为$r$的所有点构成的集合叫做以点$P_{0}$为圆心,以$r$为半径的“$t-$圆”.求以原点$O$ 为圆心,以$\frac{1}{2}$为半径的“$t-$圆”的面积;

(3) 证明:对任意点$P_1(x_1,y_1),P_2(x_2,y_2),P_3(x_3,y_3)$, $|P_1P_3| _t\leqslant\left|P_1P_2\right|_t+\left|P_2P_3\right|_t$.
}{
(1)由定义知, $\left|PQ\right| _{t}=\max\left\{\frac{\left|1-2\right|}
{1+\left|1-2\right|},\frac{\left|2-4\right|}
{1+\left|2-4\right|}\right\}
=\max\left\{\frac{1}{2},\frac{2}{3}\right\}
=\frac{2}{3}$;

(2)设$P(x,y)$是以原点$O$为圆心,以$\frac12$为半径的$t -$圆上任一点,则
$\max\left\{{\frac{|x|}{1+| x|}},{\frac{| y|}{1+| y|}}\right\}={\frac{1}{2}}$.

若$\frac{|y|}{1+|y|}\leqslant\frac{| x|}{1+| x|}=\frac{1}{2}$,则$|x|=1,| y|\leqslant 1$,
若$\frac{| x|}{1+| x|}\leqslant\frac{| y|}{1+| y|}=\frac{1}{2}$,则有$| y|=1,| x|\leqslant 1$.

由此可知,以原点$O$为圆心,以$\frac12$为半径的$t-$圆的面积为$4$.

(3)考虑函数$f\left(t\right)=\frac{t}{1+t}\ (t\geqslant 0)$.

因为$f'(t)=\frac{1}{\left(1+t\right)^{2}}>0$,
所以$f\left(t\right)$在$\left[0,+\infty\right)$上单调递增.

又$\left|x_{1}-x_{3}\right|\leqslant
\left|x_{1}-x_{2}\right|+\left|x_{2}-x_{3}\right|$,
于是
\begin{align*}
\frac{\left| x_1-x_3 \right|}{1+\left| x_1-x_3 \right|}&\leqslant \frac{\left| x_1-x_2 \right|+\left| x_2-x_3 \right|}{1+\left| x_1-x_2 \right|+\left| x_2-x_3 \right|}\\
&=\frac{\left| x_1-x_2 \right|}{1+\left| x_1-x_2 \right|+\left| x_2-x_3 \right|}+\frac{\left| x_2-x_3 \right|}{1+\left| x_1-x_2 \right|+\left| x_2-x_3 \right|}\\
&\leqslant \frac{\left| x_1-x_2 \right|}{1+\left| x_1-x_2 \right|}+\frac{\left| x_2-x_3 \right|}{1+\left| x_2-x_3 \right|},
\end{align*}

同理, $\frac{\left| y_1-y_3 \right|}{1+\left| y_1-y_3 \right|}\leqslant \frac{\left| y_1-y_2 \right|}{1+\left| y_1-y_2 \right|}+\frac{\left| y_2-y_3 \right|}{1+\left| y_2-y_3 \right|}$.

不妨设$\frac{\left| y_1-y_3 \right|}{1+\left| y_1-y_3 \right|}\leqslant \frac{\left| x_1-x_3 \right|}{1+\left| x_1-x_3 \right|}$,
则
\begin{align*}
\left| P_1P_3 \right|_t &=\frac{\left| x_1-x_3 \right|}{1+\left| x_1-x_3 \right|}\leq \frac{\left| x_1-x_2 \right|}{1+\left| x_1-x_2 \right|}+\frac{\left| x_2-x_3 \right|}{1+\left| x_2-x_3 \right|}\\
&\leqslant \max \left\{ \frac{\left| x_1-x_2 \right|}{1+\left| x_1-x_2 \right|},\frac{\left| y_1-y_2 \right|}{1+\left| y_1-y_2 \right|} \right\} +\max \left\{ \frac{\left| x_2-x_3 \right|}{1+\left| x_2-x_3 \right|},\frac{\left| y_2-y_3 \right|}{1+\left| y_2-y_3 \right|} \right\}\\
&=\left| P_1P_2\right| _t+\left| P_2P_3\right| _t.
\end{align*}
}

2005年湖南卷理科第20题，取材于著名的Scheafer模型所描述的Logistic种群的固定努力量的收获问题，并用中学生能理解的语言描述了“平衡点”及“防止过度捕捞”的含义：

\Example{
(学军中学2024年适应性测试)在概率较难计算但数据量相当大、误差允许的情况下,可以使用 Union Bound (布尔不等式)进行估计概率.已知 Union Bound 不等式为:记随机事件$A_1,\cdots,A_n$,则$P(A_1\cup A_2\cup\cdots\cup A_{n})\leqslant\sum_{i=1}^{n}P(A_{i})$.其误差允许下可将左右两边视为近似相等.据此解决以下问题:

(1) 有$n$个不同的球,其中$k$个有数字标号.每次等概率随机抽取$n$个球中的一个球.抽完后放回.记抽取$t$次球后$k$个有数字标号的球每个都至少抽了一次的概率为 $P(t)$,现在给定常数 $p$,则满足$P(t)\geqslant p$的$t$的最小值为多少?请用 Union Bound估计其近似的最小值,结果不用取整.这里$n$相当大且远大于$k$;

(2)然而实际情况中, Union Bound精度往往不够,因此需要用容斥原理求出精确值.已知概率容斥原理:记随机事件$A_1,\cdots,A_n$,则
$$
P(A_1\cup A_2\cup\cdots\cup A_n)=
\sum_{k=1}^n\left(-1\right)^{k-1}\sum_{1\leqslant a_1<a_2<\cdots<a_i\leqslant n}P(A_{a_1}A_{a_2}\cdots A_{a_i}).
$$
试问在(1)的情况下,用容斥原理求出的精确的$t$的最小值是多少(结果不用取整)? $n$相当大且远大于$k$.

(1) (2)问参考数据:当$x$相当大时,取$\left(1-\frac1x\right)^{x}=\frac1e$.
}{1}

\Example{
凸集在凸分析中有重要应用,在平面直角坐标系中,设$S$为平面向量组成的集合, $S$非空.若任意$\boldsymbol{\alpha},\boldsymbol{\beta}\in S$, $\lambda\in [0,1]$,均满足 $\lambda\boldsymbol{\alpha}
+(1-\lambda)\boldsymbol{\beta}\in S$,则称$S$为凸集.

(1)设$F=\{\alpha=(x,y)\mid y\leqslant\ln x,x>0\}$,证明: $F$为凸集;

(2)已知集合$C$为凸集,平面向量$\boldsymbol{m}\not\in C$,记$\boldsymbol{m}$到凸集$C$的“投影”为集合$D(\boldsymbol{m},C)=\{\boldsymbol{x}_0\in C\mid \forall\boldsymbol{\alpha}\in C,|\boldsymbol{m}-\boldsymbol{x}_0|\leqslant |\boldsymbol{m}-\boldsymbol{\alpha}|\}$,且 $D(\boldsymbol{m},C)$非空.证明:

(I) $D(\boldsymbol{m},C)$中有且仅有一个元素;

(II)将$D(\boldsymbol{m},C)$中的元素记作 $\boldsymbol{x}_0$,对任意 $\boldsymbol{\alpha}\in C$,
$(\boldsymbol{m}-\boldsymbol{x}_0)
\cdot(\boldsymbol{\alpha}-\boldsymbol{x}_0)\leqslant 0$.
}{1}

[清华附2024年高二期中]给定正整数$n\geqslant 3$,设集合$A=\{a_1, a_2,\cdots,a_n\}$,其中$a_k\in\mathbf{N}^\ast$, $1\leqslant k\leqslant n$且规定$a_1<a_2<\cdots<a_n$,并记$S(A)=a_1+a_2+\cdots+a_n$.

对于$1\leqslant i<j\leqslant n$,若$\frac{S(A)}{a_ia_j}\in\mathbf{N}^\ast$,则称$\{a_i,a_j\}$为集合$A$的一个“二元整除子集”.记集合$A$的“二元整除子集”总个数为$m(A)$.

(1)当$A=(1,2,3\}$时,请直接写出集合$A$的所有“二元整除子集”及$m(A)$的值;

(2)当$n=4$时,求出$m(A)$的最大值,并说明理由;

(3)当$n=5$时,若$a_{2}=2$,求出$m(A)$的最大值及所有相应的集合$A$.

\underline{\hspace{2cm}}.
{\heiti 解法一 \textbf{:}}

\hfill (\quad)
\begin{tasks}(2)
\task
\task
\task
\task
\end{tasks}

%\begin{theorem}[极化恒等式]

%\end{theorem}
%\begin{solution}
1
%\end{solution}

写文章
点击打开undefined的主页
速通 Roth 三项等差数列定理
速通 Roth 三项等差数列定理
P0lyno3ial
P0lyno3ial
依学校要求, 本人言论不代表NJU数学系任何学生
关注
我们在这里给一个Roth定理的简洁版证明, 备忘.

定理设 A\subset[N] 不包含三项等差数列, 则 |A|=O(N/\log\log N).

上面的 [N]=\{1,2,\cdots,N\} . 我们会用到上面的同余结构.

再把期望定义一下:

\mathbb{E}(f(x):x\in A):=\mathbb{E}_{x\in A}f(x):=\frac{1}{|A|}\sum_{x\in A}f(x).\\

可以对集合或者命题求期望, 其实就是平均值.

3-AP 就是三项等差数列, 3- [N] -AP 是 [N] 中的, 也就是同余意义下的等差数列, 一般不是真正的等差数列. 如果只要求 3- [N] -AP 的存在性, 整个证明可以再短一些, 请参考 Yifan 的

整个证明基于 Fourier 变换, 所以我们首先聊聊它的定义和性质. 我们使用以下形式的 Fourier 变换定义:
\hat{f}(k)=\mathbb{E}(f(\xi)\text{e}_N(-x\xi):\xi\in[N])=\frac{1}{N}\sum_{\xi\in[N]}f(\xi)\text{e}_N(-x\xi),\\
其中 \text{e}_N(x)=\text{e}^{2\pi\text{i} x/N} . 许多连续形式 Fourier 变换的性质可以没有困难的移植于此. 我们要用到以下的

(1) (逆变换) f(x)=\sum_{k\in[N]}\hat{f}(k)\text{e}_N(kx);
(2) (Parseval 等式) \sum_{x\in[N]}|f(x)|^2=N\sum_{\xi\in[N]}|\hat{f}(\xi)|^2.
这里注意系数.

可以看到 A,B,C 中 3-[N]-AP 的数量, 即数组 (x,y,z)\in A\times B\times C 使得在 [N] 中有 x+z=2y (或以同余语言表述为 x+z\equiv 2y\ (\text{mod } N)) 的数量可以按如下方式计算. 对子集 S\subset[N], 我们记 S(x)=\chi_S(x) 为特征函数, \delta_S=\frac{|S|}{N} 表示 S 的密度. 常识告诉我们:

\sum_{x\in[N]}\text{e}_N(kx)=N\delta_{0k}, \\

于是

\begin{aligned} S(A,B,C)&=\sum_{x,r\in[N]}A(x-r)B(x)C(x+r)\\ &=\sum_{x,r,a,b,c\in[N]}\hat{A}(a)\hat{B}(b)\hat{C}(c)\text{e}_N(a(x-r)+bx+c(x+r))\\ &=\sum_{a,b,c\in[N]}\hat{A}(a)\hat{B}(b)\hat{C}(c)\sum_{x\in[N]}\text{e}_N((a+b+c)x)\sum_{r\in[N]}\text{e}_N((c-a)r)\\ &=N^2\sum_{l\in[N]}\hat{A}(l)\hat{B}(-2l)\hat{C}(l)\\ &=N^2(\hat{A}(0)\hat{B}(0)\hat{C}(0)+\sum_{0\ne l\in[N]}\hat{A}(l)\hat{B}(-2l)\hat{C}(l)). \end{aligned} \\

第四行的原因如下: 注意到第三行的指数和只有在 a+b+c=0 及 c-a=0 时有贡献, 于是有 l\in[N] 使得 a=c=l, b=-2l. 注意到 \hat{A}(0)=\mathbb{E}(A)=\delta_A, 上式变为

S(A,B,C)=N^2\left[\delta_A\delta_B\delta_C+\sum_{0\ne l\in[N]}\hat{A}(l)\hat{B}(-2l)\hat{C}(l)\right]. \\

第二项可以通过 Cauchy-Schwarz 不等式及 Paserval 等式作如下估计:

\begin{aligned} &|\sum_{0\ne l\in[N]}\hat{A}(l)\hat{B}(-2l)\hat{C}(l) |\\ \le&\|\hat{A}\|_\infty(\sum_{l\ne0} |\hat{B}(-2l)|)^{1/2} (\sum_{l\ne0} |\hat{C}(l)|)^{1/2}\\ \le&N\|\hat{A}\|_\infty(\sum_{x} |B(x)|^2)^{1/2} (\sum_{x} |C(x)|^2)^{1/2}=\|\hat{A}\|_\infty\delta_B^{1/2}\delta_C^{1/2}. \end{aligned} \\

证明的技术在于所谓"密度增量操作": 如果 A 不包含任何 3-AP, 我们将证明存在长等差数列 P 使得 A'=A\cap P 满足 |A'|\ge(\delta_A+\epsilon)|P|, 意即 A 的密度通过把 A 换成 A' 增加了. 然后重复这一过程, 直至有限次操作后 A 的密度严格大于 1, 产生矛盾.

由于我们主要研究 A, 接下来我们记 \delta=\delta_A. 若 \|\hat{A}\|_\infty\le\epsilon, 那么 A 中 3-[N]-AP 的数量即为

S(A,A,A)\ge N^2(\delta^3-\delta\epsilon), \\

于是若 \|\hat{A}\|_\infty\le \frac{\delta^2}{2}, 3-[N]-AP 就存在.

现在我们考察何时 3-[N]-AP 变成真正的 3-AP. 把 [N] 三等分为 L=A\cap[0,\frac{N}{3}), M=A\cap[\frac{N}{3},\frac{2N}{3}) 和 R=A\cap[\frac{2N}{3},N). 对 [N] 中 x+z=2y 的 x,y,z\in A, 若 y,z\in [\frac{N}{3},\frac{2N}{3}), 那么容易知道 x\in [0,N), 从而 (x,y,z) 是 3-AP. 这样的 3-AP 数量为 S(A,M,M).

设 A 不包含任何 3-AP. 我们将使用密度增量方法. 先考虑 M 的密度. 若 \delta_M\le \frac{\delta}{4}, 那么 \delta_L+\delta_R\ge \frac{3\delta}{4}. 不妨设 \delta_L\ge \frac{3\delta}{8}. 注意到 [0,\frac{N}{3}) 是一个长等差数列, L 在 [0,\frac{N}{3}) 中的密度为 3\delta_L\ge \frac{9\delta}{8}>\delta, 于是 L 的密度发生了增加.

现在假设 \delta_M>\frac{\delta}{4}. 若 \|\hat{A}\|_\infty\le \frac{\delta^2}{8}, 那么

S(A,M,M)\ge N^2(\delta\delta_M^2-\|\hat{A}\|_\infty\delta_M)\ge \frac{N^2\delta^2}{32}. \\

于是当 N 很大时, A 中非平凡 3-AP 的数量至少是

\frac{N^2\delta^2}{32}-\delta N>0, \\

这与 A 中不包含 3-AP 相矛盾. 于是 \|\hat{A}\|_\infty>\frac{\delta^2}{8}.

现在我们设 |\hat{A}(r)|>\frac{\delta^2}{8} 对某个 r\in[N] 成立. 通过 Dirichlet 逼近, 可以选取 1\le s\le L 使得 d(\frac{rs }{N},\mathbb{Z})\le \frac{1}{L}. 令 P_0=\{s,2s,\cdots,ms\} 是 [N]-等差数列, 其中 L,m 有待选取. 我们引入均衡函数 f(x)=A(x)-\delta, 那么 \sum f(x)=0 与 \hat{f}=\hat{A} 成立. 注意到

\begin{aligned} \frac{\delta^2}{8}<&|\hat{f}(r)|=\mathbb{E}_{n\in[N]}\text{e}_N(-rn)\mathbb{E}_{x\in P_0}f(x+n)\text{e}_N(-rx)\\ &|\mathbb{E}_{n\in[N]}\text{e}_N(-rn)\mathbb{E}_{x\in P_0}f(x+n)|+|\mathbb{E}_{n\in[N]}\text{e}_N(-rn)\mathbb{E}_{x\in P_0}f(x+n)(\text{e}_N(-rx)-1)|\\ \le&|\mathbb{E}_{n\in[N]}\text{e}_N(-rn)\mathbb{E}_{x\in P_0}f(x+n)|+\mathbb{E}_{n\in[N]}\left|(\text{e}_N(-rn)\mathbb{E}_{x\in P_0}f(x+n)|\text{e}_N(-rx)-1|\right|\\ \le&|\mathbb{E}_{n\in[N]}\text{e}_N(-rn)\mathbb{E}_{x\in P_0}f(x+n)|+\mathbb{E}_{n\in[N]}\left|\text{e}_N(-rn)\mathbb{E}_{x\in P_0}2\pi\{\frac{mrs}{N}\}\right|\\ \le&|\mathbb{E}_{n\in[N]}\text{e}_N(-rn)\mathbb{E}_{x\in P_0}f(x+n)|+2\pi m/L, \end{aligned} \\

那么令 L=[\frac{16\pi}{\delta^2N^{1/2}}]+1, m=[\frac{N^{1/2}}{2}], 就有

|\mathbb{E}_{n\in[N]}\text{e}_N(-rn)\mathbb{E}_{x\in P_0}f(x+n)|\ge \frac{\delta^2}{8}-\frac{2\pi}{L}>\frac{\delta^2}{16}, \\

而注意到 \mathbb{E}_{n\in[N]}f(n)=0, 对某个相位 \theta,

\text{Re }\mathbb{E}_{n\in[N]}[1+\text{e}_N(\theta-rn)]\mathbb{E}_{x\in P_0}f(x+n)>\frac{\delta^2}{16}, \\

从而存在 n\in[N] 使得

\mathbb{E}_{x\in P_0}f(x+n)>\frac{\delta^2}{16\text{Re }[1+\text{e}_N(\theta-rn)]}>\frac{\delta^2}{32}, \\

或 |A\cap (P_0+n)|>(\delta+\frac{\delta^2}{32})|P_0+n|. 虽然 P_1=P_0+n=\{s+n,2s+n,\cdots,ms+n\} 不是真正的等差数列, 但它是等差数列的平移, 所以可以分裂为两个真正的等差数列, 记为 P_2,P_3. 如果 P_1 就是等差数列, 令 P=P_1 即可. 若这一点无法成立, 在其一很短, 例如 |P_3|<\delta^2/64|P_1| 的情况下, |A\cap P_2|\ge|A\cap P_1|-|P_3|>(\delta+\frac{\delta^2}{64})|P_2|, 那我们还是可以取 P=P_2; 而当二者都较长, 即 |P_2|,|P_3|\ge \delta^2/64|P_1| 时, 其一的密度增量至少为 \delta^2/32. 综合上述所有讨论就得到了

定理对于 A\subset[N] 不包含三项等差数列且 |A|=\delta N, 存在等差数列 P 使得 |P|>\frac{\delta^2N^{1/2}}{128} 并且 |A\cap P|\ge\delta(1+\frac{\delta^2}{64})|P|.

现在我们把 A,[N] 换成 A\cap P,P 并重复上述过程. 注意到密度增量为 \delta^2/64, 经过 k 次操作, 密度增量将至少为 \delta(1+\frac{\delta}{64})^k\ge\delta(1+\frac{k\delta}{64}), 于是当 k=\frac{64}{\delta} 时密度变为 2\delta, 翻了一倍; 再经过 \frac{64}{2\delta} 次密度变为 4\delta, 如此往复, 经过不到 \frac{128}{\delta} 次重复之后密度就变为 2^n\delta\to\infty, 这是不可能的.

但只要新得到的等差数列长度不小于 1, 操作就可以继续. 经过 k 次操作, 等差数列的长度至少为 \frac{\delta^2N^{2^{-k}}}{16384}. 令k=\frac{128}{\delta}, 于是只要 \delta^2N^{2^{-128\delta^{-1}}}\ge16384 或

\delta\ge\frac{128\log 2}{\log\log N-c}, \\

我们就得到了矛盾. 所以, 对 A\subset[N] 满足 |A|\ge \frac{CN}{\log\log N}, A 将包含 3-AP.

证毕. 好短.

参考文献:

T. Gowers 的加性数论讲义 (那里的证明不到两页...check细节火葬场) 2.
于品的数学分析讲义 (较详细, 适合用来过细节)
Terence Tao, Van H. Vu - Additive combinatorics-Cambridge University Press (2006) 10.3 (用了这里一个技巧来跨过1. 的一处gap)
其他可供延伸阅读的资料:

赵宇飞的 GTAC 3.3 节, 第 6 章 (万物皆可图论).
R. C. Vaughan - The Hardy-Littlewood method(1997) (万物皆可圆法)
GTM259 第 7 章 (Furstenberg的遍历论证明)
基本上等差数列问题的证明都依赖于某种增量的迭代, 如能量, 密度等. 一个不利用这种方法的证明可以参考 @Vstal 的以下文章.

编辑于 2022-03-03 19:00
数学
组合数学（Combinatorics）
傅里叶变换（Fourier Transform）
赞同 27
5 条评论
分享
喜欢
收藏
申请转载

%https://zhuanlan.zhihu.com/p/351153834

首发于
Some Interesting Combinatorial Problems

写文章
点击打开undefined的主页
我的Prelim考试试题
Yifan
Yifan
数学话题下的优秀答主
关注他
上个月勉强通过prelim考试，准备的不是很充分，不过幸好还是通过了。这里分享一下今天考试的题目，以及我的回答。

考试形式就是committee的教授们分别问我问题，然后我来用白板回答我的答案。考试时间为一小时。

第一题. 什么是 Combinatorial Nullstellensatz？如何证明？如何用它证明 Cauchy-Davenport？Cauchy-Davenport定理取等条件是什么？

答：首先叙述 Combinatorial Nullstellensatz：

定理. 假设 K 是一个域， f\in K[x_1,\dots,x_n]。假设 \prod_{i=1}^m x_i^{t_i} 是 f 中的一项，并且系数非零。如果 \deg(f)=\sum_{i}t_i ，那么对于任意 n 个 K 的非空子集 S_1,\dots ,S_n ，如果 |S_i|>t_i ，那么对每个 i 存在 s_i\in S_i ，使得 f(s_1,\dots,s_n)\neq 0 。
证明：我们首先证明特殊情形，即在 f 中，每个 x_i 的指数均不超过 t_i 。我们对 n 进行归纳： n=1 时证明显然。假设所有小于 n 的情况已证，对于 n ，我们可以把 f 写成 K[x_1,\dots,x_{n-1}][x_n] 中的元素，通过归纳假设，我们完成了这个特殊情况的证明。

一般地，由于定理中只关心 f 在 S_1\times \dots\times S_n 中的像，我们构造 \overline{f}\in K[x_1,\dots,x_d] 使得 f 和 \overline{f} 在 S_1\times \dots\times S_n 具有相同的像，并且 \overline{f} 满足上述的特殊情况，这样就可以完成证明。我们定义 g_i=\prod_{s\in S_i}(x_i-s) 。注意到 g_i 在 S_i 中恒为 0 。我们不妨假设 |S_i|=t_i+1，其余情况证明相同。注意到 g_i(x_i)=x_i^{t_i+1}+h_i(x_i) 中每个 x_i 的指数至多是 t_i+1 。对于 f 中的每个 x_i^{t_{i+1}}，我们都替换为 -h_i(x_i) ，从而得到 \overline{f} 。不难验证 \overline{f} 满足条件，从而得证。

我们接下来叙述 Cauchy-Davenport 定理。

定理. 假设 A,B 是 \mathbb{Z}/p\mathbb{Z} 的非空子集，那么我们有 |A+B|\geq \min\{|A|+|B|-1,p\} .
证明：我们假设 |A+B|\leq |A|+|B|-2 。构造二元多项式 P(x,y)=\prod_{n\in A+B}(x+y-n) ，注意到 \deg P(x,y)=|A+B|\leq |A|+|B|-2 。我们考虑 x^{|A|-1}y^{|B|-1} 在 P(x,y) 中的系数，不难发现应为 \binom{|A+B|}{|A|-1} \ \pmod p 。由于 |A+B|<p ，因此这个系数非零。应用Combinatorial Nullstellensatz，存在 a\in A 和 b\in B 使得 P(a,b)\neq0 ，而这与 P(x,y) 的构造矛盾。证毕。

对于Cauchy-Davenport定理取等的条件，由下文的Vosper定理给出：

定理. 假设 A,B\subseteq\mathbb{Z}/p\mathbb{Z} ，且 |A|,|B|\geq2 ， |A|+|B|<p 。如果 |A+B|=|A|+|B|-1 ，那么 A 和 B 是两个公差相同的等差数列。

第二题. 简述 Roth 定理的证明。

答：首先叙述 Roth 定理

定理. 假设 A\subseteq [n]:=[1,n]\cap \mathbb Z ，并且 d(A):=\frac{|A|}{n}\gg \frac{1}{\log\log n} ，那么 A 中包含长度为 3 的等差数列。
证明概要：首先，我们可以假设 A\subseteq \mathbb{Z}/N\mathbb{Z} ，取 N=3n 即可。不难验证这个版本可以推出上述版本的Roth 定理。对于 f:\mathbb{Z}/N\mathbb{Z}\to\mathbb{C} ，定义傅立叶系数 \hat{f}(x)=\frac{1}{N}\sum_{n\in\mathbb{Z}/N\mathbb{Z}}f(n)e_N(nx) ，其中 e_N(\theta)=e^{\frac{2\pi i\theta}{N}} 。 A 中长度为 3 的等差数列的个数为 N^2\sum_{r\in\mathbb{Z}/N\mathbb{Z}}\hat{1}_A(r)\hat{1}_A(r)\hat{1}_A(-2r) 。这是由于 \begin{align*} \sum_{r\in\mathbb{Z}/N\mathbb{Z}}\hat{1}_A(r)\hat{1}_A(r)\hat{1}_A(-2r)&=\frac{1}{N^3}\sum_{r\in\mathbb{Z}/N\mathbb{Z}}\sum_{n_1,n_2,n_3\in\mathbb{Z}/N\mathbb{Z}}1_A(n_1)1_A(n_2)1_A(n_3)e_N(n_1r)e_N(n_2r)e_N(-2n_3r)\\ &=\frac{1}{N^3}\sum_{n_1,n_2,n_3\in\mathbb{Z}/N\mathbb{Z}}1_A(n_1)1_A(n_2)1_A(n_3)\sum_{r\in\mathbb{Z}/N\mathbb{Z}}e_N(r(n_1+n_2-2n_3))\\ &=\frac{1}{N^2}\sum_{n_1+n_2=2n_3}1_A(n_1)1_A(n_2)1_A(n_3) \end{align*}

我们考虑 \sum_{r\in\mathbb{Z}/N\mathbb{Z}}\hat{1}_A(r)\hat{1}_A(r)\hat{1}_A(-2r)=\hat{1}_A(0)^3+\sum_{r\neq 0}\hat{1}_A(r)\hat{1}_A(r)\hat{1}_A(-2r)=:I+II 。注意到 \hat{1}_A(0)=d(A) 。如果对于所有 r\neq0 ，我们都有 |\hat{1}_A(r)|<d(A)^2/100 。那么

|II|\leq \sum_{r\neq 0}|\hat{1}_A(r)\hat{1}_A(r)\hat{1}_A(-2r)|\leq\frac{d(A)^2}{100}\sum_r |\hat{1}_A(r)|^2=\frac{d(A)^3}{100} ，

因此 I 为主项，得证。所以我们不妨假设存在一个 r\neq0 ，使得 |\hat{1}_A(r)|>\frac{d(A)^2}{100} 。我们固定这个 r 。我们首先证明可以将 \mathbb{Z}/N\mathbb{Z} 划分为长等差数列的并， e_N(rx) 在 x 属于其中一个长等差数列时，差不多是常数。我们定义 \|x\| 为 x 模 N 的正余数。

考虑集合 \{(x,\|xr\|):1\leq x\leq N\} 是 [N]\times[N] 的格点子集，一共包含 N 个点。取 \varepsilon>0 一个很小的正数，我们将 [1,N] 相等的划分成 M 个区间，每个区间长度 N/M ，取 M= N^{1/2}-1 这样的划分将 [1,N]\times[1,N] 分成了 M^2<N 个格子，根据抽屉原理，一定有两个点在同一个格子。不妨设这两个点为 (a,\|ar\|) 和 (b,\|br\|) 。于是， |a-b|<N/M ， \|(a-b)r\|<N/M

设 d=|a-b| ，将 \mathbb{Z}/N\mathbb{Z} 分成公差为 d 的等差数列的并。通过对长等差数列的细分，我们可以假设每个等差数列的长度都在 \varepsilon M 到 2\varepsilon M 之间。取一个这样的等差数列 P ， x,y 为 P 中任意两个人元素。我们有 |e_N(xr)-e_N(yr)|\leq \frac{\|(x-y)r\|}{N}\leq \frac{2\varepsilon M\|dr\|}{N}\leq 2\varepsilon 。

我们定义 balanced function f(x)=1_A(x)-d(A) 。这样子 f(x) 的均值为 0 。我们有

\begin{align*} \frac{d(A)^2N}{100}\leq N|\hat{f}(r)|&=\left|\sum_n f(n)e_N(nr)\right|\leq \sum_i \left|\sum_{n\in P_i}f(n)e_N(nr)\right|\\ &\leq \sum_i \left|\sum_{n\in P_i} f(n)e_N(n_0r)\right|+\sum_i \sum_{n\in P_i} |f(n)|\left|e_N(nr)-e_N(n_0r)\right|\\ &\leq \sum_i \left|\sum_{n\in P_i} f(n)\right|+\sum_i \sum_{n\in P_i} |f(n)|2\varepsilon\\ &\leq \sum_i \left|\sum_{n\in P_i} f(n)\right|+4\varepsilon d(A)N \end{align*}

我们取 \varepsilon=\frac{d(A)}{800} ，于是 \sum_i \left|\sum_{n\in P_i} f(n)\right|\geq \frac{d(A)^2N}{200} 。由于 \sum_i \sum_{n\in P_i} f(n)=0 ， \sum_i \left( \left|\sum_{n\in P_i} f(n)\right| +\sum_{n\in P_i} f(n)\right)\geq \frac{d(A)^2N}{200} 。根据抽屉原理，存在一个 P_i 使得

\left|\sum_{n\in P_i} f(n)\right| +\sum_{n\in P_i} f(n)=2 \sum_{n\in P_i} f(n) \geq \frac{d(A)^2|P_i|}{200} 。于是， |A\cap P_i|\geq \left(d(A)+\frac{d(A)^2}{200}\right)|P_j|，我们得到了一个density increment结果。由于集合的density一定小于1，反复重复上述操作，我们证明了没有长度为3的等差数列集合密度一定小于 \frac{c}{\log\log N} 。

第三题. 叙述sparse regularity lemma，叙述KLR 定理，并且给出几乎稠密图中embedding lemma不成立的构造。

答：定义点集对 (U,V) 是 (\varepsilon,p) -regular的，对于任意 X\subseteq U ， Y\subseteq V ，如果满足 |X|>\varepsilon|U| 以及 |Y|>\varepsilon|V| ，都有 |d(X,Y)-d(U,V)|<\varepsilon p ，其中 d(U,V)=\frac{|E(U,V)|}{|U||V|} 。

对于点集合 V 的一个划分 V=\bigcup_{i=1}^m V_i ，我们说它是 (\varepsilon,p) -regular的，如果除了 \varepsilon m^2 对 (V_i,V_j) 之外，其他的点集对都是 (\varepsilon,p) -regular的。

对于 \eta,b,p>0 ，我们说一个图 G 是 (\eta,b,p) -upper uniform的（即无处稠密），如果对于任意 U,W\subseteq V ， |U|>\eta |V| ， |W|>\eta |V| ，我们有 d(U,W)<bp 。下面我们叙述sparse regularity lemma

定理. 对于任意 \varepsilon,b,m>0 ，存在 \eta, M>0 ，使得对任意 p>0 ，一个 (\eta,b,p) -upper uniform的图 G ，存在一个 (\varepsilon,p) -regular的划分，将 V(G) 分为 K 份，其中 m<K<M
sparse regularity lemma应用的一个问题就是embedding lemma 和 counting lemma不一定成立。然而KLR定理告诉我们，counting lemma在几乎所有情况下都会成立。

定义 \mathcal{G}(H,n,m,p,\varepsilon) 为一类图，其中的图 G 满足如下条件。 G 的点集为 V_1,\dots,V_{|V(H)|} 的不交并，每个 V_i 大小均为 n 。如果 (i,j)\in E(H) ，我们在 V_i,V_j 之间添加一个 (\varepsilon,p) -regular的有 m 条边的二部图。这些边构成了 G 的所有边。我们称 H 到 G 的一个标准嵌入，如果 H 中的每个点 i 落在 V_i 里。我们定义 \mathcal{G}^*(H,n,m,p,\varepsilon) 为 \mathcal{G}(H,n,m,p,\varepsilon) 的子集，满足 \mathcal{G}^*(H,n,m,p,\varepsilon) 中的任何图都没有 H 的标准嵌入。对于图 H ，我们定义它的 2-density m_2(H)=\max\left\{\frac{|E(H')|-1}{|V(H')-1|}: H'\subseteq H, |V(H')|\geq3\right\} 。我们有如下定理

定理. 对于任意图 H ，任意 \beta>0 ，存在 C,n_0,\varepsilon ，使得对任意正整数 n>n_0 ，以及正整数 m>Cn^{2-1/m_2(H)} ， |\mathcal{G}^*(H,n,m,m/n^2,\varepsilon)|\leq \beta^m\binom{n^2}{m}^{|E(H)|} 。
容易构造出，对于非常稀疏的伪随机图，embedding lemma 和 counting lemma不一定成立。实际上，对于几乎稠密的图，counting lemma也不一定成立。

定理. 对任意 p=o(1) ， H 为非二部图， \mathcal{G}^*(H,n,pn^2,p,\varepsilon) 非空。
证明概要：不妨设 H=K_\ell 。取 \ell 个点集，每个点集 n 个点，不同点集之间放入一个概率为 p\asymp 1/n 的随机二部图。由FKG不等式可以证明，存在这样一个图 G 使得其不包含 K_\ell ，并且每两个不同点集之间都是 (\varepsilon,d) -regular的，其中 (1-\varepsilon)p<d<(1+\varepsilon)p 。我们接下来将 G 的每个点换成大小为 N 的独立集，不同的独立集中，如果其所对应的两个点在 G 里有边，我们就嵌入一个完全二部图。我们这样得到了一个新图 G' ，显然也不包含 K_\ell 。 G 中的一个大小为 n 的点集对应 G' 中大小为 nN 的点集，并且 G' 中两个大点集之间也是 (\varepsilon,d) -regular的。注意到 n 和 N 无关，我们只要求他们一起趋于无穷，而 d 只与 n 有关。定理得证。

第四题. 简述最大 K_{2,2} -free和最大 K_{3,3} -free图的构造。简述 \mathrm{ex}(n,K_{s,t})\gg n^{2-\frac{s+t-2}{st-1}} 构造。

答：首先 \mathrm{ex}(n,K_{2,2})\sim n^{3/2}。考虑图 G 的点集为 \mathbb{Z}/p\mathbb{Z}\times\mathbb{Z}/p\mathbb{Z}\setminus \{(0,0)\} ，其中 p 为一个素数。则 |V(G)|=p^2-1 。对于 G 中任意两点 (x,y) 和 (a,b) ，这两个点相邻当且仅当 ax+by=1 。不难发现，任意固定 (x,y) ，至少有 p 个不同的 (a,b) 满足 ax+by=1 。忽略可能的一个解 (a,b)=(x,y) ， G 中每个点的度至少有 p-1 。因此 |E(G)|\gg (p-1)n\sim n^{3/2} 。注意到两条不同直线最多交于一点，于是 G 是 K_{2,2} -free的。

\mathrm{ex}(n,K_{3,3})\sim n^{5/3} 。选取素数 p\equiv 3\pmod 4 。构造图 G ，使得其点集为 \mathbb{F}_p^3 ，两个点 (x,y,z) 与 (a,b,c) 相邻当且仅当 (a-x)^2+(b-y)^2+(c-z)^2=1 。注意到任何一个点在 G 中的degree都是 p^2 ，因此图 G 有 p^5\sim n^{5/3} 条边。不难验证 G 是 K_{3,3} -free的：这是由于过三个点的单位球不可能同时交与另外超过两个点。

对于 \mathrm{ex}(n,K_{s,t})\gg n^{2-\frac{s+t-2}{st-1}} ，我们在 n 点图上以概率 p=\tfrac{1}{2} n^{-\frac{s+t-2}{st-1}} 随机选边。假设图包含 J 个 K_{s,t} ，那么 \mathbb{E}(J)=p^{st}\binom{n}{s}\binom{n}{t}\leq p^{st}n^{s+t} 。另一方面，假设图有 I 条边，则 \mathbb{E}(I)=p\binom{n}{2}\geq n^2p/4 。于是

\mathbb{E}(I-J)\geq pn^2/4-p^{st}n^{s+t}\geq pn^2/4-pn^2\big(\tfrac{1}{2}\big)^{st-1}\geq pn^2/8=\tfrac{1}{16}n^{2-\frac{s+t-2}{st-1}} 。

根据抽屉原理，存在一个图 G ，我们对其包含的每个 K_{s,t} 移除一条边使其 K_{s,t} -free，操作后的图 G 仍然有 \asymp n^{2-\frac{s+t-2}{st-1}} 条边。

发布于 2021-03-14 03:47
数学
组合数学（Combinatorics）
赞同 286
37 条评论
分享
喜欢
收藏
申请转载

文章被以下专栏收录
Some Interesting Combinatorial Problems
Some Interesting Combinatorial Problems
主要介绍组合数学方向中的有趣问题

\section*{复数法训练题}
\subsection*{一、基本结论}
以下均小写字母$x$来表示点$X$所对应复数．

\ex $Z,A,B$三点共线当且仅当$\frac{z-a}{z-b}\in\mathbb{R}$．
\ex $AB$垂直于$CD$当且仅当$\frac{d-c}{b-a}$为纯虚数．
\ex $AB$平行于$CD$当且仅当$\frac{a-b}{c-d}\in\mathbb{R}$．
\ex $A$和$B$关于直线$CD$对称当且仅当$a=\frac{(c-d)\bar{b}+\bar{c}d-c\bar{d}}{\bar{c}-\bar{d}}$．
\ex $AB$在单位圆上，则$Z$在$AB$上的射影为$\frac{a+b+z-ab\bar{z}}{2}$．
\ex $\triangle ABC$和$\triangle XYZ$顺相似当且仅当$\frac{a-b}{b-c}=\frac{x-y}{y-z}$；$\triangle ABC$和$\triangle XYZ$逆相似当且仅当$\frac{a-b}{b-c}=\frac{\bar{x}-\bar{y}}{\bar{y}-\bar{z}}$．
\ex $AB$和$CD$交于点$P$，则$p=\frac{(\bar{a}b-a\bar{b})(c-d)-(a-b)(\bar{c}d-c\bar{d})}{(\bar{a}-\bar{b})(c-d)-(a-b)(\bar{c}-\bar{d})}$；特别地，如果$A,B,C,D$在单位圆上，则$p=\frac{ab(c+d)-cd(a+b)}{ab-cd}$．
\ex $Y$为$AB$和$CD$的位似旋转中心，则$y=\frac{ad-bc}{a+d-b-c}$．
\ex $A,B$在单位圆上，过它们的切线的交点为$P$，则$p=\frac{2ab}{a+b}$．
\ex $\triangle ABC$的内心为$I$，$A,B,C$所对的旁心分别为$I_{A},I_{B},I_{C}$，设$a=u^{2}$，$b=v^{2}$，$c=w^{2}$，则$i=-(uv+vw+wu)$，$i_{A}=uv-vw+wu$，$i_{B}=uv+vw-wu$，$i_{C}=-uv+vw+wu$．
\ex $\triangle ABC$的外心为$O$，则$o=\left|\begin{array}{lll}a & a \bar{a} & 1 \\ b & b\bar{b} & 1 \\ c & c\bar{c} & 1\end{array}\right|\div\left|\begin{array}{lll}a & \bar{a} & 1 \\ b & \bar{b} & 1 \\ c& \bar{c} & 1\end{array}\right|$．
\ex $A,B,C$在单位圆上，$\angle BAC=60^{\circ}$，则$b^{2}+bc+c^{2}=0$．
\ex $A,B,C$在单位圆上，$\triangle ABC$的垂心为$H$，九点圆圆心为$N$，重心为$G$，则$h=a+b+c$，$n=\frac{a+b+c}{2}$，$g=\frac{a+b+c}{3}$．
\ex $A,B$在单位圆上，点$P$在弦$AB$上，则$p+ab\bar{p}=a+b$．
\ex $A,B,C,D$四点共圆当且仅当$\frac{b-a}{c-a}\div\frac{b-d}{c-d}=\frac{\bar{b}-\bar{a}}{\bar{c}-\bar{a}}\div\frac{\bar{b}-\bar{d}}{\bar{c}-\bar{d}}$．
\ex 考虑有向角模$180^{\circ}$，则$\angle ABC=\angle XYZ$当且仅当$\frac{a-b}{c-b}\div\frac{x-y}{z-y}\in\mathbb{R}$．
\ex $\triangle ABC$的面积$S=\frac{\mathrm{i}}{4}\left|\begin{array}{lll}a&\bar{a}&1\\b&\bar{b}&1\\c&\bar{c}&1\end{array}\right|$．
\newpage
\subsection*{二、典型例题}

\setcounter{ex}{0}

\ex $\triangle ABC$的外接圆在点$B,C$处的切线交于点$N$，$M$为$BC$中点．求证：$\angle BAN=\angle CAM$．
\begin{proof}
设$A,B,C$在单位圆上，则$n=\frac{2bc}{b+c}$，$m=\frac{b+c}{2}$．只需证明：
$$r=\frac{\frac{c-a}{m-a}}{\frac{n-a}{b-a}}=\frac{(c-a)(b-a)}{\left(\frac{b+c}{2}-a\right)\left(\frac{2 b c}{b+c}-a\right)}=\frac{2(c-a)(b-a)(b+c)}{(b+c-2 a)(2 b c-a b-a c)} \in \mathbb{R}$$
$$\text{则}\bar{r}=\frac{2\left(\frac{1}{c}-\frac{1}{a}\right)\left(\frac{1}{b}-\frac{1}{a}\right)\left(\frac{1}{b}+\frac{1}{c}\right)}{\left(\frac{1}{b}+\frac{1}{c}-\frac{2}{a}\right)\left(\frac{2}{b c}-\frac{1}{a b}-\frac{1}{a c}\right)}=\frac{2(c-a)(b-a)(b+c)}{(b+c-2 a)(2 b c-a b-a c)}=r.$$

于是$r\in\mathbb{R}$，证毕．
\end{proof}
\ex 求证：圆内接四边形$ABCD$的密克点、对角线的交点、外接圆的圆心，这三点共线．
\begin{proof}
设$ABCD$内接于单位圆$O$．设$ABCD$的密克点为$M$，则由$\triangle MBC$顺相似于$\triangle MAD$知：$\frac{m-b}{m-c}=\frac{m-a}{m-d}$，即$m=\frac{bd-ac}{b+d-a-c}$，$\bar{m}=\frac{\frac{1}{bd}-\frac{1}{ac}}{\frac{1}{b}+\frac{1}{d}-\frac{1}{a}-\frac{1}{c}}=\frac{ac-bd}{ac(b+d)-bd(a+c)}$．

设$ABCD$的对角线交点为$N$，则$n=\frac{ac(b+d)-bd(a+c)}{ac-bd}$，

于是$\bar{m}n=m\bar{n}=1$．

因此$\frac{0-m}{0-n}=\frac{0-\bar{m}}{0-\bar{n}}$，即$O,M,N$三点共线，证毕．
\end{proof}
\newpage
\ex \textbf{（2009年IMO预选题G4）}在圆内接四边形$ABCD$中，$AC\cap BD=E$，$AD\cap BC=F$．$G,H$分别是$AB,CD$的中点．求证：$EF$是$\triangle EGH$的外接圆的切线．
\begin{proof}
设$M$为$EF$的中点，则由牛顿线定理知：$G,H,M$三点共线．故只需证明：$ME^{2}=MG\cdot MH$．

设$(ABCD)$的半径为$R$，简记$\vv{OX}$为$x$．即证：
$$\begin{aligned}
&\left(\frac{e-f}{2}\right)^{2}=\left(\frac{e+f}{2}-\frac{a+b}{2}\right)\cdot\left(\frac{e+f}{2}-\frac{c+d}{2}\right)\\
\iff&4e\cdot f-(e+f)\cdot (a+b+c+d)+(a+b)\cdot (c+d)=0.
\end{aligned}$$
记$\rho(X)$为点$X$对$\odot O$的圆幂，则有：
$$\begin{aligned}
&\rho(E)=(e-a)\cdot (e-c)=(e-b)\cdot (e-d)=e^{2}- R^{2}\\
&\rho(F)=(f-a)\cdot (f-b)=(f-b)\cdot (f-c)=f^{2}-R^{2}
\end{aligned}$$
$F$在$E$的极线上，故$4e\cdot f=4R^{2}$．

以上五式相加即证．
\end{proof}
\newpage

\ex \textbf{（2014年IMO第4题）}点$P,Q$在锐角$\triangle ABC$的边$BC$上，满足$\angle PAB=\angle BCA$，且$\angle CAQ=\angle ABC$．点$M,N$分别在直线$AP,AQ$上，使得$P$为$AM$的中点，且$Q$为$AN$的中点．求证：直线$BM$与$CN$的交点在$\triangle ABC$的外接圆上．
\begin{proof}
我们证明$BM\cap(ABC)=CN\cap(ABC)$，注意到$M,N$地位对等，只需证明$X=BM\cap(ABC)$的表达式是关于$b,c$对称的．导角知$\triangle PBA$和$\triangle ABC$逆相似，于是
$$\frac{p-b}{p-c}=\frac{\bar{a}-\bar{b}}{\bar{c}-\bar{b}}\Rightarrow p=\frac{\frac{1}{a}-\frac{1}{b}}{\frac{1}{c}-\frac{1}{b}}(a-b)+b=\frac{c(a-b)^{2}}{a(c-b)}+b$$
由$P$为$AM$中点：$m=2p-a=2\left(\frac{c(a-b)^{2}}{a(c-b)}+b\right)-a$．

若$X\in(ABC)$，则$\bar{x}=\frac{1}{x}$，于是
$$\begin{aligned}
&\frac{m-b}{\bar{m}-\bar{b}}=\frac{x-b}{\bar{x}-\bar{b}}=-bx\\
\Rightarrow&x=-\frac{m-b}{b(\bar{m}-\bar{b})}=-\frac{2\left(\frac{c(a-b)^{2}}{a(c-b)}+b\right)-a-b}{b\left[2\left(\frac{\frac{1}{c}(\frac{1}{a}-\frac{1}{b})^{2}}{\frac{1}{a}(\frac{1}{c}-\frac{1}{b})}+\frac{1}{b}\right)-\frac{1}{a}-\frac{1}{b}\right]}=-\frac{ab+ac-2bc}{b+c-2a}
\end{aligned}$$
上式关于$b,c$对称，于是命题得证．
\end{proof}
\newpage
\ex $\triangle ABC$的内心为$I$，内切圆与三边的切点分别为$R,S,T$．$M,N$分别为$AR$和$BC$的中点．求证：$M,I,N$三点共线．
\begin{proof}
设内切圆为单位圆，内心为原点．于是有
$$a=\frac{2st}{s+t},b=\frac{2rt}{r+t},c=\frac{2rs}{r+s}.$$
$$n=\frac{b+c}{2}=\frac{rt}{r+t}+\frac{rs}{r+s}=\frac{r(rs+rt+2st)}{(r+s)(r+t)}$$
$$\bar{n}=\frac{\frac{1}{r}\left(\frac{1}{rs}+\frac{1}{rt}+\frac{2}{st}\right)}{\left(\frac{1}{r}+\frac{1}{s}\right)\left(\frac{1}{r}+\frac{1}{t}\right)}=\frac{s+t+2r}{(r+s)(r+t)}$$
$$m=\frac{a+r}{2}=\frac{st}{s+t}+\frac{r}{2}=\frac{rs+rt+2st}{2(s+t)},\bar{m}=\frac{\frac{1}{rs}+\frac{1}{rt}+\frac{2}{st}}{2\left(\frac{1}{s}+\frac{1}{t}\right)}=\frac{s+t+2r}{2r(s+t)}.$$
于是
$$\frac{m}{\bar{m}}=\frac{r(rs+rt+2st)}{s+t+2r}=\frac{n}{\bar{n}}$$
因此$M,I,N$三点共线，证毕．
\end{proof}
\newpage
\ex $\triangle ABC$的重心为$G$，点$A$在$BC$边上的射影为$H$，过点$A$作$BC$的平行线，交$\triangle ABC$的外接圆于另一点$D$．求证：$H,G,D$三点共线．
\begin{proof}
熟知$g=\frac{a+b+c}{3}$，$h=\frac{a+b+c-\frac{bc}{a}}{2}$．设$(ABC)$为单位圆，则由$AD\parallel BC$知：
$$\frac{a-d}{\bar{a}-\bar{d}}=\frac{b-c}{\bar{b}-\bar{c}}\iff \frac{a-d}{\frac{1}{a}-\frac{1}{d}}=\frac{b-c}{\frac{1}{b}-\frac{1}{c}}\iff d=\frac{bc}{a}$$
$H,G,D$三点共线$\iff\frac{d-g}{\bar{d}-\bar{g}}=\frac{d-h}{\bar{d}-\bar{h}}$．
$$d-g=\frac{bc}{a}-\frac{a+b+c}{3}=\frac{3bc-a^{2}-ab-ac}{3a}.$$
$$\bar{d}-\bar{g}=\frac{a}{bc}-\frac{1}{3a}-\frac{1}{3b}-\frac{1}{3c}=\frac{3a^{2}-bc-ab-ac}{3abc}.$$
$$d-h=\frac{bc}{a}-\frac{a+b+c-\frac{bc}{a}}{2}=\frac{3bc-a^{2}-ab-ac}{2a}.$$
$$\bar{d}-\bar{h}=\frac{a}{bc}+\frac{a}{2bc}-\frac{1}{2a}-\frac{1}{2b}-\frac{1}{2c}=\frac{3a^{2}-bc-ca-ab}{2abc}$$
于是$\frac{d-h}{d-h}=\frac{2}{3}=\frac{\bar{d}-\bar{g}}{\bar{d}-\bar{h}}$，证毕．
\end{proof}

2024年中科大少年班创新班入围考数学真题(回忆版)

一、填空(90分,每题5分,共18题)

1. $a,b\in \mathbf{R}$,正确的是\underline{\hspace{2cm}}.

\ding{172} $a\neq 0$是$|a|>0$的充要条件;

\ding{173} 若$a,b$为无理数,则$ab$为无理数;

\ding{174} $\forall a,\exists b\in \mathbf{Z}$,使 $0\leqslant a+b<1$;

\ding{175} $\exists a\in \mathbf{Q}$使$\sqrt{a^{2}+1}\in \mathbf{Q}$.

2. $S_{1}=\left\{a\left|a^{\frac{1}{3}}<2\right. \right\}$, $S_{2}=\left\{a\left| \left(\frac{1}{3}\right)^{a}<\frac{1}{2}\right.\right\}$,
$S_{3}=\left\{a\left|\log_{a}\frac{2}{3}<1\right.\right\}$,
求$(S_{1}\cap S_{2})\cup S_{3}$.

3. $x^2+y^2=2|x|-2|y|$所围成的面积为\underline{\hspace{2cm}}.

4.求$f(x)=\left|\sin\frac{x}{2}+\sin\frac{x}{3}
+\sin\frac{x}{4}\right|$的最小正周期为\underline{\hspace{2cm}}.

5. $\angle A=30^\circ$, $|AB|=2,|BC|=\sqrt{2}$,求$|AC|$.

6. $A$为复平面内一点, $|\alpha|=2$, $|\beta|=3$, $\alpha$与$\beta$ 夹角为$60^\circ$, $\overrightarrow{AP}=x\alpha+y\beta$, $\{0\leqslant x\leqslant y\leqslant 1\}$,
则所有$P$点构成的的图形面积为\underline{\hspace{2cm}}.

7. $P$点在复平面内坐标为$(a,b)$,将$\overline{OP}$顺时针旋转$90^\circ$得到$\overrightarrow{OQ}$,旋转后对应的复数为\underline{\hspace{2cm}}.

8. $x^2+y^2-axy+x+y=1$是双曲线,求$a$范围为\underline{\hspace{2cm}}.

9. $A(1,0,1),B(0,1,-1),C(1,1,0),D(1,1,1)$,
则$D$到平面$ABC$的距离为\underline{\hspace{2cm}}.

10. $z=\cos\frac{2\pi}n+\mathrm{i}\sin\frac{2\pi}n$,
求$|1-z|\cdot\left|1-z^2\right|\cdot\left|1-z^3\right|
\cdots\left|1-z^ {n-1}\right|=$\underline{\hspace{2cm}}.

11.一只蚂蚁从一个正方体(边长为$1$)的顶点沿棱长爬,爬过所有棱长且回到原点的最短路径为\underline{\hspace{2cm}}.

12. $x,y\in \mathbf{R}$, $\cos(x+y)+\cos x+\cos y$ 的取值范围为\underline{\hspace{2cm}}.

13.若$e^x>cx$对任意$x>0$均成立,求$c$的范围为\underline{\hspace{2cm}}.

14. $x_{1}$到$x_{7}$分别为$22,23,30,35,40,45,50$,求$\sum_{i=1}^7|x_i-t|$取最小值时, $t$为\underline{\hspace{2cm}}.

15. $\left(x+\frac{1}{x}+1\right)^{6}$的常数项系数为\underline{\hspace{2cm}}.

16. $8$本不同书分给$5$个人, $3$个人各拿一本, $1$个人拿两本, $1$个人拿三本,共\underline{\hspace{2cm}}种选法.

17. $A$、$B$事件相互独立, $A$、$B$发生概率相同, $P(A\cup B)=0.64$,则$A$发生的概率为

18.甲乙两人比赛,甲胜概率为$P$,乙胜概率为$1-P$,比对方先多胜两局判胜,则甲胜概率为\underline{\hspace{2cm}}.

二、(10 分) 给正六面体$8$个顶点, $6$个面的中点编号为$1\sim 14$,是否能让每个面上顶点与中心编号和相等?并证明.

答案解析

1. \ding{172} \ding{174} \ding{175}

2. $\mathbf{R}^+$

3. $2\pi-4$

4. $24\pi$

5. $\sqrt{3}-1$或$\sqrt{3}+1$

6. $\frac{3\sqrt{3}}{2}$

7. $b-a\mathrm{i}$

8. $(-\infty,-2)\cup(2,3)\cup(3,+\infty)$

9. $\frac{\sqrt{3}}{3}$

10. $n$

11. $16$

12. $\left[ -\frac{3}{2},3 \right]$

13. $c\in\left(-\infty,\mathrm{e}\right)$

14. $35$

15. $141$

16. $67200$

17. $0.4$

18. $\frac{p^2}{2p^{2}-2p+1}$

二.证明:将8个顶点设为$a_1\sim a_8$, 6个面的中心设为$b_1\sim b_6$,则
$$
\sum a_k+\sum b_k=1+2+\cdots+14=\frac{14\times15}{2}=105,
$$
$6$个面总和为$\sum b_k+3\sum a_k=105+2\sum a_k$为奇数.

而6面总和应是6的倍数,矛盾.综上,不成立.

2023年中科大创新班初试数学试题解答

1.复数$z$满足$z^{2023}-z-1=0$,求证: $|z|\leqslant 1$当且仅当$\mathrm{Re}(z)\leqslant -\frac12$.

证明:由题意知: $z^{2023}=z+1$,两边取模得: $|z| ^{2023}=|z+1|$.于是
\begin{align*}
|z|^{4046}=& |z+1|^{2} = (z+1)(\bar{z}+1) \\
&= |z|^2+2\mathrm{Re}(z)+1
\end{align*}
即 $2\mathrm{Re}(z)+1=|z|^2(|z|^{2022}+1)(|z|^{2022}-1)$.

于是
\begin{align*}
&\mathrm{Re} (z)\leqslant -\frac{1}{2} \\
&\Leftrightarrow 2\mathrm{Re} (z)+1\leqslant 0 \\
&\Leftrightarrow |z|^2(|z|^{2022}+1)(|z|^{2022}-1)\leqslant 0 \\
&\Leftrightarrow \left|z\right|\leqslant 1.
\end{align*}

2.设$\overrightarrow{\alpha}_i\ (1\leqslant i\leqslant 5)$为$\mathbf{R}^3$中的五个非零向量. 求证:存在非零向量$\overrightarrow{\beta}\in\mathbf{R}^3$,使得存在$1\leqslant j_1<j_2<j_3<j_4\leqslant 5$,满足$\overrightarrow{\beta}$与$\overrightarrow{\alpha}_{j_k}$的夹角均不超过$\frac\pi2\ (k=1,2,3,4)$.

证明:设$\overrightarrow{\alpha}_i$的起点均为$O$, 终点分别为$A_i\ (1\leqslant i\leqslant 5)$.

考虑平面$OA_1A_2$,由抽屉原理, $A_3$、$A_4$、$A_5$中必存在两点,在平面$OA_1A_2$的同侧(含平面上),不妨设为$A_3$、$A_4$.

取平面$OA_1A_2$的法向量$\overrightarrow{\beta}$,且使$\overrightarrow{\beta}$指向$A_3$、$A_4$一侧,易知$\overrightarrow{\beta}$满足题意.

3.甲、乙两盒中各放2只兔子,一雌一雄.称一次操作是从甲、乙盒中各随机抽一支兔子交换,记$n$次操作后甲、乙盒中仍各有一雌一雄的概率为$p_n$.求$p_n$及$\lim_{n\to\infty}p_n$.

解答:若交换前笼子里均为一雄一雌,则一共有4种交换情况,其中两种交换后仍均为一雄一雌 (雄换雄或雌换雌),另两种交换后笼子里为两雄和两雌.而两雄和两雌的情况交换后必然回到均为一雄一雌.于是有递推关系:
$$
p_{n+1}=\frac12p_n+(1-p_n)=1-\frac12p_n,\quad p_0=1.
$$
于是$p_{n+1}-\frac{2}{3}=-\frac{1}{2}\left(p_{n}
-\frac{2}{3}\right)$,可得
$$
p_n=\frac23+\frac13\left(-\frac12\right)^n,
$$
于是$\lim_{n\to\infty}p_n=\frac23$.

4. (1) $x>0$,证明: $x-\frac{x^3}6<\sin x<x$.

(2) $0<a_1<\sqrt{3}$, $a_{n+1}=a_n-\frac{\sin a_n}{n+1}$.证明:对任意正整数$n$,都有$na_n<\frac{3a_1}{3-a_1^2}$.

证明:

(1)求导易证,实际上为$\sin x$一阶和三阶的泰勒展开,是第二问的提示.

(2)由题意知:
\begin{align*}
(n+1)a_{n+1} &=(n+1)a_n-\sin a_n\\
&<(n+1)a_n-a_n+\frac16a_n^3=na_n+\frac16a_n^3.
\end{align*}
于是$\frac{a_n}{a_{n+1}}<\frac{n+1}{n}$,归纳易知$a_n$递减,因此
\begin{align*}
\frac1{na_n}&<\frac1{(n+1)a_{n+1}}+\frac{a_n^2}{6n(n+1)a_{n+1}} \\
&< \frac1{(n+1)a_{n+1}}+\frac{a_n}{6n^2}< \frac1{(n+1)a_{n+1}}+\frac{a_{1}}{6n^{2}}.
\end{align*}
累加得:
\begin{align*}
\frac1{a_1}-\frac1{na_n} &<
\sum_{k=1}^{n-1}\frac{a_1}{6k^2} <\frac{a_{1}}{6}\left(1+\sum_{k=2}^{n-1}
\frac{1}{k(k-1)}\right) \\
&=\frac{a_{1}}{6}\cdot\left(2-\frac{1}{n-1}\right) <\frac{a_{1}}{3},
\end{align*}
解得: $na_n<\frac{3a_1}{3-a_1^2}$,证毕.

5.将正整数去除完全平方数后由小到大排成一排,记作$a_1,a_2,\cdots$.比如$a_1=2$, $a_2=3$, $a_3=5$, $\cdots$.求证:对任意正整数$n$,都有$|a_n-n-\sqrt{n}|<\frac12$.

证明:满足$k^2<a_n<(k+1)^2$的$a_n$共有$2k$个,此时有
$$
2+4+\cdots+2(k-1)<n\leqslant 2+4+\cdots+2k
$$
即$(k-1)k<n\leqslant k(k+1)$,
即$\left( k-\frac{1}{2} \right) ^2<n+\frac{1}{4}\le \left( k+\frac{1}{2} \right) ^2$,故$k-\frac{1}{2}<\sqrt{n}\leqslant k+\frac{1}{2}$,易知等号无法取得.

在$a_n$之前共有$k$个完全平方数被去除,于是$a_n=n+k$.

因此$-\frac{1}{2}<a_n-n-\sqrt{n}<\frac{1}{2}$,证毕.

2024年中科大少年班及少创班科学营第一阶段试题

中科大少年班及创新班科学营第一阶段

时间: 2024年3月30日,上午8:30一10:10

本试卷共5题,每题20分,满分100分.

1.从$\{1,2,\cdots,9\}$中选取三个不同的数,从大到小排成一个三位数$X$,再从$\{1,2,\cdots,8\}$中选取三个不同的数,从大到小拼成一个三位数$Y$.求: $X>Y$的概率?

2.设$x\geqslant -1$且$x\in \mathbf{R}$,令$a_1=\sqrt{2x+3}$, $a_{n+1}=\sqrt{2a_n+3}$,
试求使数列$\{a_n\}$中有无穷多个正整数的$x$的全部取值.

3.求所有实数$a$,使得$|x^2+ax+1|\geqslant |x+1| $在$x\in \mathbf{R}$上恒成立.

4.求所行$2024$次多项式$f(x)$,使得$f(x^2)=f(x)\cdot f(x+2)$.

5. 复数$|z_1|=|z_2|=\cdots=|z_n|=1$, $z_1+z_2+\cdots+z_n=n-2+i$,其中$n\geqslant 2024$ $n\in \mathbf{Z}$,求$\mathrm{Re}(z_1)$的最小值.

2024年中科大少创班科学营第二阶段数学试题

2024年4月20日上午

9:00—10:00播放学习视频, 10:00—11:30测试

围绕度量空间展开，包含空间、集合等考题，融合了分析、数论等内容，综合性较强。

解答题（共5题，每小题20分，计100分）

1.在$n$维数组空间$\mathbb{R}^n$中,可以定义距离$d_2(x,y)=\sqrt{\sum_{i=1}^n(x_i-y_i)^2}$.

(1)对$n=2$的情形,证明$d_{2}$是$\mathbb{R}^n$上的距离.

(2)定义距离$d_1=\sum_{i=1}^n|x_i-y_i|$, $d_\infty=\max_{i=1,\cdots,n}\{|x_i-y_i|\}$,证明: $d_1,d_2,d_\infty$是等价距离.

2.设有限集$A=\{1,2,\cdots,q\}$,定义集合$X=A^n$.在集合$X$上定义两个元素$x=(x_1,\cdots,x_n)$和$y=(y_1,\cdots,y_n)$的汉明距离$d(x,y)=\#\{i\in A\mid x_i\neq y_i\}$.

(1)证明:已知正整数$r\leqslant n$,则集合$\{y\in X\mid d(x,y)\leqslant r\}$的元素个数为$\sum_{i=0}^{r}(q-1)^iC_n^i$.

(2)证明恒等式: $q^n=\sum_ {i=0}^n(q-1)^iC_n^i$,只允许使用第 (1) 问的结论.

(3)设$X$的子集$C$有$M$个元素,满足条件:

(i) $C$中任意两个元素的距离不小于$r$;

(ii) $C$是满足条件的最大子集,证明不等式
$$M\geqslant\frac{q^{n}}
{\displaystyle\sum_{i=0}^{r-1}(q-1)^{i}C_{n}^{i}}.$$

3. 证明以下结论:

(1)单点集$\{x_0\}$是闭集.

(2)任意个开集的并仍是开集.

(3)有限个开集的交仍是开集.

(4)在有理数集$\mathbb{Q}$上定义$p$-进距离,则$\mathbb{Z}\subseteq\mathbb{Q}$不是闭集.

4. 回答下列问题:

(1)写出柯西序列的定义.

(2)已知$\{x_n\}$和$\{y_n\}$是距离空间$\mathbb{R}$上的柯西序列,求证: $\{x_ny_n\}$也是$\mathbb{R}$上的柯西序列.

(3)设$\{x_n\}$是汉明空间上的柯西序列,求证: $\exists N\in\mathbb{Z}^\ast$,使得$\forall n>N$, $x_n=x_N$.

5.在有理数集$\mathbb{Q}$上,定义$p-$进距离$d_p(x,y)=|x-y|_p$.

(1)证明:不同的$p-$进距离互不等价.

(2)证明:在$p-$进距离下$\lim_{n\to+\infty}(1+p)^{p^n}=1$.

中科大创新科学营次轮学习能力测试物理试题

2024年4月20日下午

15: 00 $\sim$ 16: 00,播放学习视频 16:00 $\sim$ 17: 30 测试

解答题 (共4题,计100分)

1.写出波的相速与群速的物理意义,并给出用频谱计算相速与群速的方法. (5 分)

2.一维单原子链,每个原子的质量为$M$,在最邻近近似下,相邻原子间用劲度系数为$K$,原长为$a$的弹簧连接.

(1) 解释简谐近似的物理意义. (5 分)

(2)在最邻近近似下求解一维单原子链的频谱,并在第一步里渊区$q\in\left[-\frac\pi a,\frac\pi a\right]$内画出频
谱,纵轴单位取为$2\sqrt{\frac{K}{M}}$. (5 分)

(3) 计算格波的相速与群速和波数的关系,并在第一步里渊区内画出图像. (5 分)

(4)说明$\lambda_{1}=6a$和$\lambda_{2}=\frac{6}{7}a$对应的振动情况完全相同. (5 分)

(5)解释周期性边界条件,并求出波数$q$的所有可能取值. (5 分)

(6) 解释长波极限的含义,并求出一维单原子链的声速.当$q=\pm\frac\pi a$时,指出各原子的振动模式并解释其产生原因. (5分)

(7)考虑次临近作用,设相邻原子间用劲度系数为$K_{1}$的弹簧连接,间隔一个原子的两个原子间用劲度系数为$K_{2}$的弹簧连接.求解此时的色散关系,相速,群速和声速. (5 分)

(8)单原子链中混入一个质量为$m<M$的杂质原子,求解色散关系. (5 分)

(9)预测声速最大的固体单质,并给出理由. (5分)

3.一个全同原子组成的平面方格子,晶格常数为$a$,原子质量为$M$,最邻近原子的作用力常数为$K$.记第$l$行,第$m$列原子偏离平衡位置的位移为$u_{l,m}$.

(1)列出第$l$行,第$m$列原子的动力学方程. (5 分)

(2)设解的形式为$u_{l,m}=u(0)\exp[i(\omega t-lq_xa-mq_ya)]$,求出色散关系. (5 分)

(3)确定$q_x$和$q_y$可取的值. (5分)

(4)证明此介质中声波的角频率正比于波数$|q|$. (5 分)

面试话题

面试包含3个话题，涉及12个材料，话题分别与量子信息技术、生物移植、人工智能相关。

量子信息的题目分别是：量子通信、量子计算、量子测量、量子探测（量子雷达）。

生物移植的题目分别是：自体移植、同种同基因移植、同种异基因移植、异种移植。

人工智能的题目分别是：AI和数学、物理、化学、生物的关系。

\Example{
求组合数的倒数和$\sum_{n=m}^p{\frac{1}{C_{n}^{m}}}$.
}{
由
$$
\frac{1}{C_{n}^{k}}-\frac{1}{C_{n+1}^{k}}=\frac{C_{n}^{k-1}}{C_{n}^{k}C_{n+1}^{k}}=\frac{k}{\left( n+1 \right) C_{n}^{k}}=\frac{k}{\left( k+1 \right) C_{n+1}^{k+1}}
$$
可得
$$
\sum_{n=m}^p{\frac{1}{C_{n}^{m}}}=\frac{m}{m-1}\left( 1-\frac{1}{C_{p+1}^{m-1}} \right).
$$}

\Example{
(北京大学2023年实验班几何学I期中)设有一个椭圆,长轴端点分別为 $A_1$, $A_2$,短轴端点为$B_1$, $B_2$,两焦点为$F_1$, $F_2$,其中$|A_1F_1|<|A_2F_2|$.

(a)证明每个自$F_{1}$发出的光线经过椭圆反射都经过$F_{2}$.

(b)从线段 $A_1F_1$ 的中点向$B_1$发出光线,证明存在一个椭圆与这光线经过多次反射后的诸光线都相切.

(c)若$\overrightarrow{F_1A}=\frac{1}{3}
\overrightarrow{F_1F_2}$,从$A$向$B_{1}$发出光线,是否还存在一个椭圆与多次反射后的光线都相切?证明你的结论. (这一问确实记不太清了)
}{1}

\Example{
(九州大学2003年前期5分)设$n\geqslant 2,n\in \mathbf{N}^\ast$,数列$\{H_n\}$满足$H_n=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}$.

(1)证明不等式$\ln (n+1)<H_n<1+\ln n$;

(2)对于数列$\{c_n\}$,记$\Delta c_n=c_{n+1}-c_n\ (n=1,2,\cdots)$.证明:对于任意数列$\{a_n\}$和$\{b_n\}$,总有
$$
\sum_{k=1}^{n-1}{a_k\Delta b_k}=a_nb_n-a_1b_1-\sum_{k=1}^{n-1}{b_{k+1}\Delta a_k}
$$
成立.若$\sum_{k=1}^{n-1}{kH_k}=\left( H_n-\frac{1}{2} \right) p\left( n \right)$,求整式$p(n)$;

(3)证明不等式
$$
\left| \frac{2}{n\left( n-1 \right)}\sum_{k=1}^{n-1}{kH_k}-\ln n \right|<\frac{1}{2}.
$$
}{
(1)由于函数$f(x)=\frac{1}{x}$非负且单调递增,则有
$$
\int_k^{k+1}{\frac{1}{x}}\mathrm{d}x<\frac{1}{k}
<\int_{k-1}^k{\frac{1}{x}}\mathrm{d}x,
$$
于是
$$
H_n=\sum_{k=1}^n{\frac{1}{k}}>\sum_{k=1}^n{\int_k^{k+1}{\frac{1}{x}}\text{d}x}=\int_1^{n+1}{\frac{1}{x}}\text{d}x=\ln \left( n+1 \right)
$$
且
$$
H_n=\sum_{k=1}^n{\frac{1}{k}}<1+\sum_{k=2}^n{\int_{k-1}^k{\frac{1}{x}}\text{d}x}=1+\int_1^n{\frac{1}{x}}\text{d}x=1+\ln n.
$$

(2)因为$a_k\Delta b_k+b_{k+1}\Delta a_k=a_k\left( b_{k+1}-b_k \right) +b_{k+1}\left( a_{k+1}-a_k \right) =a_{k+1}b_{k+1}-a_kb_k$,则
$$
\sum_{k=1}^{n-1}{\left( a_k\Delta b_k+b_{k+1}\Delta a_k \right)}=\sum_{k=1}^{n-1}{\left( a_{k+1}b_{k+1}-a_kb_k \right)}=a_nb_n-a_1b_1,
$$
所以
$$
\sum_{k=1}^{n-1}{a_k\Delta b_k}=a_nb_n-a_1b_1-\sum_{k=1}^{n-1}{b_{k+1}\Delta a_k}.
$$

令$b_n=\frac{n(n-1)}{2}$,则
$$
\Delta b_k=b_{k+1}-b_k=\frac{k\left( k+1 \right)}{2}-\frac{\left( k-1 \right) k}{2}=k.
$$
因此
\begin{align*} \sum_{k=1}^{n-1}{k}H_k&=\sum_{k=1}^{n-1}{H_k\Delta b_k}=H_nb_n-H_1b_1-\sum_{k=1}^{n-1}{b_{k+1}\Delta H_k}\\
&=H_n\frac{n\left( n-1 \right)}{2}-\sum_{k=1}^{n-1}{\frac{k\left( k+1 \right)}{2}}\cdot \frac{1}{k+1}\\
&=H_n\frac{n\left( n-1 \right)}{2}-\sum_{k=1}^{n-1}{\frac{k}{2}}=H_n\frac{n\left( n-1 \right)}{2}-\frac{n\left( n-1 \right)}{4}\\
&=\left( H_n-\frac{1}{2} \right) \cdot \frac{n\left( n-1 \right)}{2},
\end{align*}
故$p(n)=\frac{n^2-n}{2}$.

(3)由(2)可知
$$
\frac{2}{n\left( n-1 \right)}\sum_{k=1}^{n-1}{kH_k}=H_n-\frac{1}{2},
$$
由(1)可知
\begin{align*}
-\frac{1}{2} &<\ln \left( n+1 \right) -\ln n-\frac{1}{2}<\frac{2}{n\left( n-1 \right)}\sum_{k=1}^{n-1}{kH_k}-\ln n\\
&<1+\ln n-\ln n-\frac{1}{2}=\frac{1}{2}.
\end{align*}
因此
$$
\left| \frac{2}{n\left( n-1 \right)}\sum_{k=1}^{n-1}{kH_k}-\ln n \right|<\frac{1}{2}.
$$
}

\Example{
(奈良医大2011年)数列$\{a_n\}$满足对任意正整数$p,q$,均有不等式$|a_{p+q}-a_p-a_q|\leqslant 1$成立.

(1)设$n\in \mathbf{N}^\ast,k\in\mathbf{N}^\ast,k\geqslant 2$,证明: $|a_{kn}-ka_n|\leqslant k-1$;

(2) 设$n\in \mathbf{N}^\ast,k\in\mathbf{N}^\ast$,证明: $|na_{n+k}-(n+k)a_n|\leqslant 2n+k-2$.
}{
(1)由于$\left| a_{kn}-a_{\left( k-1 \right) n}-a_n \right|\leqslant 1$, $\left| a_{(k-1)n}-a_{\left( k-2 \right) n}-a_n \right|\leqslant 1$, $\cdots$,
$\left| a_{2n}-a_{n}-a_n \right|\leqslant 1$,
由绝对值不等式可得
\begin{align*}
k-1 & \geqslant \sum_{j=2}^k\left|a_{jn}-a_{(j-1)n}-a_{n} \right|
\geqslant \left|\sum_{j=2}^k\left[a_{jn}-a_{(j-1)n}-a_{n}\right] \right|\\
&=\left|a_{kn}-a_{(k-1)n}-a_n+a_{(k-1)n}-a_{(k-2)n}-a_n +\cdots +a_{2n}-a_{n}-a_n \right|\\
&=|a_{kn}-ka_n|.
\end{align*}

(2)当$n=1$时,不等式$|a_{kn}-ka_n|\leqslant k-1$也成立,故$|a_{kn}-ka_n|\leqslant k-1,k\in \mathbf{N}^\ast$.

由$|a_{n+k}-a_n-a_k|\leqslant 1$可得$|na_{n+k}-na_n-na_k|\leqslant n$,再由$|a_{kn}-ka_n|\leqslant k-1$, $|na_{k}-a_{kn}|\leqslant n-1$和绝对值不等式可得
$|na_{n+k}-(n+k)a_n|\leqslant 2n+k-2$.
}

\Example{
若数列$\{a_n\}$满足对任意正整数$m,n$,均有不等式$|a_{m+n}-a_m-a_n|\leqslant 1$成立,则称$\{a_n\}$为$L$型数列.

(1)判断下列数列是否为$L$型数列,并说明理由.

\ding{172} $a_n=2n+2$;\quad \ding{173} $a_n=\ln n$.

(2)若$\{a_n\}$为$L$型数列.

(i)设$\{a_n\}$是公差为$1$的等差数列,求$a_1$的取值范围;

(ii)设$a_1=1$,证明: $|a_n-n|\leqslant n-1,n\in \mathbf{N}^\ast$;

(iii)证明: $|na_{n+k}-(n+k)a_n|\leqslant 2n+k-2,n\in \mathbf{N}^\ast,k\in\mathbf{N}^\ast$.
}{1}

\Example{
设数列$A:a_1,a_2,\cdots,a_n$中每一项都是互不相同的正整数,对于$1\leqslant i<j\leqslant n$,如果存在$1\leqslant p<q\leqslant n$,使得$a_q-a_p=2(a_j-a_i)$,则称$(i,j)$为数列$A$的完美数组.

(1)求数列$A:1,2,3,4$的所有完美数组;

(2)证明:数列$A:3^1,3^2,\cdots,3^{100}$中不存在完美数组;

(3)若$n=100$,求数列$A$中完美数组个数的最大可能值.
}{1}

\Example{
设数列$\{a_n\}$满足$a_1=1$,且$a_{n+1}=\begin{cases}
a_n+203, & \mbox{若$x_n$不是偶数},\\
\frac{a_n}{2}, & \mbox{若$x_n$是偶数}.
\end{cases}$
}{
(1)求$a_3$和$a_5$;

(2)

(3)若存在$k\in \mathbf{N}^\ast$使得$x_k$为$2^n$的倍数,求正整数$n$的最大值.}
%$n=8$

\Example{
已知有限集合$A=\{a_1,a_2,\cdots,a_n\}\ (n\geqslant 2,n\in \mathbf{N})$,若集合$A$中任意元素$a_i$都满足$-1<a_i<1$,则称该集合$A$为收敛集合.对于收敛集合$A$,定义$\Gamma$变换有如下操作:从$A$中任取两个元素$a_i$、$a_j\ (i\neq j)$,由$A$中除了$a_i$、$a_j$以外的元素构成的集合记为$C_1$,令$A_1=C_1\cup \left\{\frac{a_i+a_j}{1+a_ia_j}\right\}$,若集合$A_1$还是收敛集合,则可继续实施$\Gamma$变换,得到的新集合记作$A_{2}$, $\cdots$,如此经过$k$次$\Gamma$变换后得到的新集合记作$A_k$.

(1)设$A=\left\{-\frac{1}{2},0,\frac{1}{7}\right\}$,请写出$A_{1}$的所有可能的结果;

(2)设$A=\{a_1,a_2,\cdots,a_{10}\}$是收敛集合,试判断集合$A$最多可进行几次$\Gamma$变换,最少可进行几次$\Gamma$变换,并说明理由;

(3)设$A=\left\{-\frac{1}{9},-\frac{3}{11},-\frac{1}{6},-\frac{1}{2},
\frac{1}{6},\frac{1}{7},\frac{1}{9},
\frac{5}{13}\right\}$,对于集合$A$反复$\Gamma$变换,当最终所得集合$A_k$只有一个元素时,求所有的满足条件的集合$A_k$.
}{
1
}

%https://www.cnblogs.com/HeNuclearReactor/p/17552175.html
贝尔数

\Example{
记$f^{(n)}(x)$为函数$f(x)$的$n$阶导函数, $f'(x)=f^{(1)}(x)$且有$f^{(n)}(x)=\left[f^{(n-1)}(x)\right]'\ (n\in\mathbf{N}^\ast)$,若对任意$n\in \mathbf{N}^\ast$, $f^{(n)}(0)$均存在,
则记为$f\in C^\infty (0)$,并记$\odot_n f=\frac{f^{(n)}(0)}{n!}$.

(1)已知$f(x)=1+x+2x^2+\cdots+2024x^{2024}$,
求$\odot_{100} f$.

(2)设$q\in \mathbf{R},k,n\in \mathbf{N}^\ast$且$1\leqslant k\leqslant n$, $f\left( x \right) =\left( 1+x \right) \left( 1+qx \right) \cdots \left( 1+q^{n-1}x \right)$,
求$\odot_k f$.
}{1}

\Example{
高斯二项式定理被广泛应用于量子微积分、组合数学等领域.
设$q\in \mathbf{R},n\in \mathbf{N}^\ast$,
记$[n]=1+2+\cdots+q^{n-1},[n]!=[n]\times [n-1]\times\cdots \times [1]$,规定$[0]!=1$.
对于$F(x;n;a)=\left( x+a \right) _{q}^{n}=\left( x+a \right) \left( x+qa \right) \cdots \left( x+q^{n-1}a \right)$,定义$D_{q}^{k}F(x;n;a) =\left[ n \right] \left[ n-1 \right] \cdots \left[ n-k+1 \right] \left( x+a \right) _{q}^{n-k}$.

(1)求$F(x;2;1)-D_{q}^{1}F(x;2;1)$;

(2)求$\frac{\left[ n-k \right] !}{\left[ n \right] !}D_{q}^{k}F\left( 0;n;a \right)$;

(3)证明: $F\left( x;n;a \right) =\sum_{k=0}^n{\frac{D_{q}^{k}F\left( 0;n;a \right)}{\left[ j \right] !}x^k}$.
}{
(1)因为$F\left( x;2;1 \right) =\left( x+1 \right) \left( x+q \right) =x^2+\left( 1+q \right) x+q$,
而$D_{q}^{1}F\left( x;2;1 \right) =\left[ 2 \right] \left( x+1 \right) _{q}^{1}=\left( 1+q \right) \left( x+1 \right)$,所以$F(x;2;1)-D_{q}^{1}F(x;2;1)=x^2-1$.

(2)因为
\begin{align*}
D_{q}^{k}F\left( 0;n;a \right) &=\left[ n \right] \left[ n-1 \right] \cdots \left[ k+1 \right] \left( 0+a \right) _{q}^{k}\\
&=\left[ n \right] \left[ n-1 \right] \cdots \left[ n-k+1 \right] q^{\left( n-k \right) \left( n-k-1 \right) /2}a^{n-k}\\
&=\frac{\left[ n \right] !}{\left[ n-k \right] !}q^{\left( n-k \right) \left( n-k-1 \right) /2}a^{n-k},
\end{align*}
故
$$
\frac{\left[ n-k \right] !}{\left[ n \right] !}D_{q}^{k}F\left( 0;n;a \right) =q^{\left( n-k \right) \left( n-k-1 \right) /2}a^{n-k}.
$$

(3)要证
$F\left( x;n;a \right) =\sum_{k=0}^n{\frac{D_{q}^{k}F\left( 0;n;a \right)}{\left[ j \right] !}x^k}$,
只需证

}

$a$换成$x$, $x$改为$1$

\newpage

\Example{高斯二项式定理被广泛应用于量子微积分、组合数学等领域.
设$y,q\in \mathbf{R},n\in \mathbf{N}^\ast$,
记$[n]=1+q+\cdots+q^{n-1},[n]!=[n]\times [n-1]\times\cdots \times [1]$,并规定$[0]!=1$.
对于$F(x,n)=\left( x+y \right) _{q}^{n}=\left( x+y \right) \left( x+qy \right) \cdots \left( x+q^{n-1}y \right)$,定义$D_{q}^{k}F(x,n) =\left[ n \right] \left[ n-1 \right] \cdots \left[ n-k+1 \right] \left( x+y \right) _{q}^{n-k}$,其中$k=0,1,2,\cdots,n$.

(1)若$y=q=1$,求$F(x,2)$和$D_{q}^{1}F(x,2)$;

(2)求$\frac{\left[ n-k \right] !}{\left[ n \right] !}D_{q}^{k}F\left( 0,n \right)$;

(3)证明: $F\left( x,n \right) =\sum_{k=0}^n{\frac{D_{q}^{k}F\left( 0,n \right)}{\left[ k \right] !}x^k}$.
}{
(1)若$y=q=1$, $F\left( x,2 \right) =\left( x+y \right) \left( x+qy \right) =x^2+\left( 1+q \right) xy+y^2=(x+1)^2$,
而$D_{q}^{1}F\left( x,2 \right) =\left[ 2 \right] \left( x+y \right) _{q}^{1}=\left( 1+q \right) \left( x+y \right)=2(x+1)$.

(2)因为
\begin{align*}
D_{q}^{k}F\left( 0,n \right) &=\left[ n \right] \left[ n-1 \right] \cdots \left[ k+1 \right] \left( 0+y \right) _{q}^{n-k}\\
&=\left[ n \right] \left[ n-1 \right] \cdots \left[ n-k+1 \right] q^{\left( n-k \right) \left( n-k-1 \right) /2}y^{n-k}\\
&=\frac{\left[ n \right] !}{\left[ n-k \right] !}q^{\left( n-k \right) \left( n-k-1 \right) /2}y^{n-k},
\end{align*}
故
$$
\frac{\left[ n-k \right] !}{\left[ n \right] !}D_{q}^{k}F\left( 0;n;a \right) =q^{\left( n-k \right) \left( n-k-1 \right) /2}y^{n-k}.
$$

(3)要证
$F\left( x,n \right) =\sum_{k=0}^n{\frac{D_{q}^{k}F\left( 0,n \right)}{\left[ k \right] !}x^k}$,
只需证
\begin{align*}
\left( x+y \right) \left( x+qy \right) \cdots \left( x+q^{n-1}y \right) &=\sum_{k=0}^n{\frac{\left[ n \right] !}{\left[ n-k \right] !\left[ k \right] !}q^{\left( n-k \right) \left( n-k-1 \right) /2}y^{n-k}x^k}\\
&=\sum_{k=0}^n{\frac{\left[ n \right] !}{\left[ n-k \right] !\left[ k \right] !}q^{k\left( k-1 \right) /2}x^{n-k}y^k}.
\end{align*}

令$G\left( y \right) =\left( x+y \right) \left( x+qy \right) \cdots \left( x+q^{n-1}y \right)=\sum_{k=0}^n{a_{k}y^k}$,

一方面,
$$
\left( x+y \right) G\left( qy \right) =\left( x+y \right) \sum_{k=0}^n{a_{k}q^ky^k}=xa_{0}+\sum_{k=1}^n{\left( xq^ka_{k}+q^{k-1}a_{k-1} \right) y^k}+a_{n}q^ny^{n+1},
$$

另一方面,
$$
\left( x+q^ny \right) G\left( y \right) =\left( x+q^ny \right) \sum_{k=0}^n{a_{k}y^k}=xa_{0}+\sum_{k=1}^n{\left( xa_{k}+q^na_{k-1} \right) y^k}+a_{n}q^ny^{n+1},
$$

再由
$$
\left( x+y \right) G\left( qy \right) =\left( x+q^ny \right) G\left( y \right),
$$
当$q\neq 1$时,比较两式中$y^k$的系数可得$xq^ka_{k}+q^{k-1}a_{k-1}=xa_{k}+q^na_{k-1}$,
则
$$
\frac{a_{k}}{a_{k-1}}=\frac{q^n-q^{k-1}}{x\left( q^k-1 \right)}=\frac{q^{k-1}\left[ n-k+1 \right]}{x\cdot \left[ k \right]},
$$
由$a_{0}=x^n$可知
$$
a_{k}=a_{0}\prod_{m=1}^k{\frac{q^{m-1}\left[ n-m+1 \right]}{x\cdot \left[ m \right]}}=\frac{\left[ n \right] !}{\left[ n-k \right] !\left[ k \right] !}q^{k\left( k-1 \right) /2}x^{n-k}.
$$

当$q=1$时,由$\left[ n \right] =1+q+\cdots +q^{n-1}=n,\left[ n \right] !=n!$
可知
$$
\left( x+y \right) ^n=\sum_{k=0}^n{\frac{\left[ n \right] !}{\left[ n-k \right] !\left[ k \right] !}y^{n-k}x^k}=\sum_{k=0}^n{C_{n}^{k}y^{n-k}x^k}
$$
也成立.

综上所述, $F\left( x,n \right) =\sum_{k=0}^n{\frac{D_{q}^{k}F\left( 0,n \right)}{\left[ k \right] !}x^k}$.
}

{
记$F\left( x;n \right) =\sum_{k=0}^n{a_{n,k}x^k}$,则有$a_{n,0}=1,a_{n,n}=q^{n(n-1)/2}$.

一方面,
\begin{align*}
F\left( x;n \right) &=\left( 1+q^{n-1}x \right) F\left( x;n-1 \right) =\left( 1+q^{n-1}x \right) \sum_{k=0}^{n-1}{a_{n-1,k}x^k}\\
&=a_{n-1,0}+\sum_{k=1}^{n-1}{\left( a_{n-1,k}+a_{n-1,k-1}q^{n-1} \right) x^k}+a_{n-1,n-1}q^{n-1}x^n.
\end{align*}

另一方面,
\begin{align*}
F\left( x;n \right) &=\left( 1+x \right) F\left( qx;n-1 \right) =\left( 1+x \right) \sum_{k=0}^n{a_{n-1,k}q^kx^k}\\
&=a_{n-1,0}+\sum_{k=1}^{n-1}{\left( a_{n-1,k}q^k+a_{n-1,k-1}q^{k-1} \right) x^k}+a_{n-1,n-1}q^{n-1}x^n.
\end{align*}

比较$x^k$的系数可得
$a_{n-1,k}+a_{n-1,k-1}q^{n-1}
=a_{n-1,k}q^k+a_{n-1,k-1}q^{k-1},
$
即
$$
a_{n-1,k}=\frac{q^{k-1}\left[ n-k-1 \right]}{\left[ k-1 \right]}a_{n-1,k-1}.
$$
因此
\begin{align*}
a_{n,k} &=a_{n,0}\prod_{m=1}^k{\frac{q^{m-1}\left[ n-m+1 \right]}{\left[ m \right]}}\\
&=\frac{q^{k\left( k-1 \right) /2}\left[ n-1 \right] \left[ n-2 \right] \cdots \left[ n-k+1 \right]}{\left[ k \right] !}=\frac{q^{k\left( k-1 \right) /2}\left[ n \right] !}{\left[ n-k \right] !\left[ k \right] !},
\end{align*}
由此得证.
}

, $\left[ \begin{array}{c}
n\\
k\\
\end{array} \right] =\frac{\left[ n \right] !}{\left[ n-k \right] !\left[ k \right] !}$.

圆周率:
%http://chenkang.js.cn/

\Example{
数列$\{x_n\}\ (n=0,1,2,\cdots)$满足$x_0=\sqrt{2}$,且$x_n=k_n+\frac{1}{x_{n+1}}$,其中$k_n$为不超过$x_n$的最大整数.
已知数列$\{A_n\},\{B_n\}\ (n=0,1,2,\cdots)$满足$A_0=B_1=1,A_1=k_0,B_0=0$且$\left( \begin{matrix}
A_{n+1}& A_n\\
B_{n+1}& B_n\\
\end{matrix} \right) =\left( \begin{matrix}
A_n& A_{n-1}\\
B_n& B_{n-1}\\
\end{matrix} \right) \left( \begin{matrix}
k_n& 1\\
1& 0\\
\end{matrix} \right)$.

(1)证明: $\left| \begin{matrix}
A_n& A_{n-1}\\
B_n& B_{n-1}\\
\end{matrix} \right|=\left( -1 \right) ^n\ (n=1,2,\cdots)$
和$\left| \begin{matrix}
A_n& A_{n-2}\\
B_n& B_{n-2}\\
\end{matrix} \right|=\left( -1 \right) ^{n-1}\ (n=2,3,\cdots)$
;

(2) $\frac{x_nA_n+A_{n-1}}{x_nB_n+B_{n-1}}
=\sqrt{2}$;

(3) $\left| \sqrt{2}-\frac{A_n}{B_n} \right|<\frac{1}{B_{n}^{2}}\ (n=1,2,\cdots)$.
}{1}

%2017m

%https://math.sjtu.edu.cn/course/
%上海交通大学

\newpage

\Example{
数列$\{x_n\}\ (n=0,1,2,\cdots)$满足$x_0=\sqrt{2}$,且$x_n=k_n+\frac{1}{x_{n+1}}$,其中$k_n$为不超过$x_n$的最大整数.定义数列$\{A_n\},\{B_n\}\ (n=0,1,2,\cdots)$为$B_0=0,A_0=A_1=B_1=1$且
\begin{align*}
A_{n+1} &=k_nA_n+A_{n-1},\\
B_{n+1} &=k_nB_n+B_{n-1}.
\end{align*}

(1)令$y_n=A_nB_{n-1}-A_{n-1}B_n$,求$k_1,y_2$以及$\{y_n\}$的通项公式;

令$z_n=A_nB_{n-2}-A_{n-2}B_n$,求$\{z_n\}$的通项公式;

(2)求$\frac{x_nA_n+A_{n-1}}{x_nB_n+B_{n-1}}\ (n=1,2,\cdots)$;

(3)证明: $\left| \sqrt{2}-\frac{A_n}{B_n} \right|<\frac{1}{B_{n}^{2}}\ (n=1,2,\cdots)$.
}{
(1)首先有$k_0=1$,由$\sqrt{2}=x_0=k_0+\frac{1}{x_1}=1+\frac{1}{x_1}$可得$x_1=\sqrt{2}+1$,则$k_1=2$.
因此$A_2=k_1A_1+A_0=3,B_2=k_1B_1+B_0=2$,
则$y_2=A_2B_1-A_1B_2=1$.

又
\begin{align*}
y_{n+1} &=A_{n+1}B_n-A_nB_{n+1}=\left( k_nA_n+A_{n-1} \right) B_n-A_n\left( k_nB_n+B_{n-1} \right)\\
&=-\left( A_nB_{n-1}-A_{n-1}B_n \right) =-y_n,
\end{align*}
又$y_1=-1$,则$\{y_n\}$为首项是$-1$,公比为$-1$的等比数列,故$y_n=(-1)^n$.

(2)因为
$$
\frac{x_nA_n+A_{n-1}}{x_nB_n+B_{n-1}}=\frac{\left( k_n+\frac{1}{x_{n+1}} \right) A_n+A_{n-1}}{\left( k_n+\frac{1}{x_{n+1}} \right) B_n+B_{n-1}}=\frac{A_{n+1}+\frac{A_n}{x_{n+1}}}
{B_{n+1}+\frac{B_n}{x_{n+1}}}
=\frac{x_{n+1}A_{n+1}+A_n}{x_{n+1}B_{n+1}+B_n},
$$
则常数数列$\frac{x_nA_n+A_{n-1}}{x_nB_n+B_{n-1}}=\frac{x_1A_1+A_0}{x_1B_1+B_0}=\frac{\sqrt{2}+1+1}{\sqrt{2}+1}
=\sqrt{2}$.

(3)由$\frac{1}{x_n}=x_{n-1}-k_{n-1}\in (0,1)$可知$x_n>1$,又$B_n\geqslant 0$,则
\begin{align*}
\left| \sqrt{2}-\frac{A_n}{B_n} \right| &=\left| \frac{x_nA_n+A_{n-1}}{x_nB_n+B_{n-1}}-\frac{A_n}{B_n} \right|=\left| \frac{A_{n-1}B_n-A_nB_{n-1}}{\left( x_nB_n+B_{n-1} \right) B_n} \right|\\
&=\left| \frac{\left( -1 \right) ^n}{\left( x_nB_n+B_{n-1} \right) B_n} \right|=\frac{1}{\left( x_nB_n+B_{n-1} \right) B_n}\leqslant\frac{1}{\left( x_nB_n \right) B_n}<\frac{1}{B_{n}^{2}}.
\end{align*}
}

\Example{
设$x$为给定的正无理数,数列$\{x_n\}\ (n=0,1,2,\cdots)$满足$x_0=x$,且$x_n=k_n+\frac{1}{x_{n+1}}$,其中$k_n$为不超过$x_n$的最大整数.

(1)若$x=\sqrt{2}$,请直接写出$k_0,k_1$和$\{x_n\}\ (n=1,2,\cdots)$的通项公式(不需要说明理由);

%14页, 2017年
(2)定义数列$\{A_n\},\{B_n\}\ (n=0,1,2,\cdots)$为$B_0=0,A_0=B_1=1,A_1=k_0$且
\begin{align*}
A_{n+1} &=k_nA_n+A_{n-1},\\
B_{n+1} &=k_nB_n+B_{n-1}.
\end{align*}

%(i)令$y_n=A_nB_{n-1}-A_{n-1}B_n$, $z_n=A_nB_{n-2}-A_{n-2}B_n$,求$\{y_n\},\{z_n\}$的通项公式;

(i)证明: $\frac{x_nA_n+A_{n-1}}{x_nB_n+B_{n-1}}=x\ (n=1,2,\cdots)$;

(ii)证明: $\left| x-\frac{A_n}{B_n} \right|<\frac{1}{B_{n}^{2}}\ (n=1,2,\cdots)$.
}{
(1)首先有$k_0=1$,由$\sqrt{2}=x_0=k_0+\frac{1}{x_1}=1+\frac{1}{x_1}$可得$x_1=\sqrt{2}+1$,则$k_1=2$.
因此$A_2=k_1A_1+A_0=3,B_2=k_1B_1+B_0=2$,
则$y_2=A_2B_1-A_1B_2=1$.

\Example{
对于$m,n\in \mathbf{N}^\ast$,定义数列$f\left( m,n \right)$满足$f(1,1)=1$,且$f\left( m,n \right) =f\left( n,m \right) ,f\left( m+1,n \right) =\frac{m}{m+n}f\left( m,n \right)$.

(1)求$f(1,3)$;

(2)求$f(m,n)$; %$f\left( m,n \right) =\frac{\left( m-1 \right) !\left( n-1 \right) !}{\left( m+n-1 \right) !}$

(3)记$f(n,n+1)$的前$n$项和为$S_n$,证明: $S_n<\frac{2}{3}$.
}{
(2)首先有
$$
f\left( n,1 \right) =\frac{n-1}{n}f\left( n-1,1 \right) =\cdots =\frac{\left( n-1 \right) !}{n!}f\left( 1,1 \right) =\frac{\left( n-1 \right) !}{n!},
$$
因此
\begin{align*}
f\left( m,n \right) &=\frac{m-1}{m+n-1}f\left( m-1,n \right) =\cdots =\frac{\left( m-1 \right) !}{\left( m+n-1 \right) \cdots \left( n+1 \right)}f\left( 1,n \right)\\
&=\frac{\left( m-1 \right) !}{\left( m+n-1 \right) \cdots \left( n+1 \right)}f\left( n,1 \right) =\frac{\left( m-1 \right) !}{\left( m+n-1 \right) \cdots \left( n+1 \right)}\cdot \frac{\left( n-1 \right) !}{n!}\\
&=\frac{\left( m-1 \right) !\left( n-1 \right) !}{\left( m+n-1 \right) !}.
\end{align*}

(3)由于
$$
f\left( n,n+1 \right) =\frac{\left( n-1 \right) !n!}{\left( 2n \right) !}=\frac{1}{n\cdot 4^n}\cdot \frac{\left( 2n \right) !!}{\left( 2n-1 \right) !!},
$$
当$n\geqslant 2$时,由于$\frac{2n}{2n-1}<\frac{\sqrt{n}}{\sqrt{n-1}}$,则
$$
\frac{\left( 2n \right) !!}{\left( 2n-1 \right) !!}<2\prod_{k=2}^n{\frac{\sqrt{k}}{\sqrt{k-1}}}
=2\sqrt{n}.
$$
因此
$$
f\left( n,n+1 \right) =\frac{1}{n\cdot 4^n}\cdot \frac{\left( 2n \right) !!}{\left( 2n-1 \right) !!}\leqslant \frac{2\sqrt{n}}{n\cdot 4^n}\leqslant \frac{2}{4^n}.
$$
由此可得
$$
S_n<\frac{\frac{1}{2}\left( 1-\frac{1}{4^n} \right)}{1-\frac{1}{4}}=\frac{2}{3}.
$$
}

一般地,
$$
\frac{\left( 2n \right) !!}{\left( 2n-1 \right) !!}\sim \sqrt{\pi n}.
$$

%http://www.360doc.com/content/20/1121/11/71283309_947032464.shtml
%https://www.doc88.com/p-1458981422745.html

\Example{
(2005年湖南卷理科)自然状态下的鱼类是一种可再生的资源.为持续利用这一资源,需从宏观上考察其再生能力及捕捞强度对鱼群总量的影响.用$x_n$表示某鱼群在第$n$年年初的总量, $n\in\mathbf{N}^\ast$,且$x_1>0$.不考虑其他因素,设在第 $n$年内鱼群的繁殖量及被捕捞量都与$x_n$成正比,死亡量与 $x_n^2$成正比,这些比例系数依次为正常数$a,b,c$.

(I)求$x_n$与$x_{n+1}$的关系式;

(II)猜测:当且仅当 $x_1,a,b,c$满足什么条件时,每年年初鱼
群的总量保持不变? (不要求证明)

(III)设$a=2,c=1$,为保证对一切$x_1\in(0,2)$的值,都有$x_n>0$, $n\in\mathbf{N}^\ast$,则捕捞强度$b$的最大允许值是多少?证明你的结论.
}{
What is truth? Can anything be proven?
}

\Example{若数列$\{x_n\}$满足:存在等比数列$\{c_n\}$,使得集合 $\{x_n+c_n\mid n\in\mathbf{N}^\ast\}$元素个数不大于$k\ (k\in\mathbf{N}^\ast)$,则称数列$\{x_n\}$具有 $P(k)$性质 .

(1)已知数列$\{a_n\}$满足$a_1=0,a_{n+1}=-\frac{a_n}{2}-\frac{\sqrt{3}}{2}
\cos\frac{2n\pi}{3}\ (n\in\mathbf{N}^\ast)$.

(i)证明:数列$\{a_n+\sin\frac{2n\pi}3\}$为等比数列,且数列$\{a_n\}$具有$P(3)$性质;

(ii)记$S_n$为数列$\{a_n\}$的前$n$项和.证明:数列$\{S_n\}$具有$P(2)$性质.

(2)记数列$\{p_n\}$的前$n$项和为$T_n$.若数列$\{T_n\}$具有$P(k)$性质,是否存在$m\in\mathbf{N}^\ast$,使得数列 $\{p_n\}$具有$P(m)$性质?说明理由.

%https://mp.weixin.qq.com/s?__biz=Mzg4OTUwNDYzNg==&mid=2247486880&idx=1&sn=9eca2070510da485de2837f7a0755d00&chksm=cfeb9bb3f89c12a57651f1744869070cfe1657bb6512485bb9e11e6029f9306918948f5b26a7&mpshare=1&scene=1&srcid=0420bafKVSguILPwbsUyc71P&sharer_shareinfo=81188926f9aa7c8d5d1abfacb4bd13e6&sharer_shareinfo_first=81188926f9aa7c8d5d1abfacb4bd13e6#rd
}
{
(1) (i)设$b_{n} =a_{n}+\sin\frac{2n\pi}{3}$,
则$b_{1}=a_{1}+\sin\frac{2\pi}{3}
=\frac{\sqrt{3}}{2}$,
并且
\begin{align*}
b_{n+1}& =a_{n+1}+\sin\left(\frac{2n\pi}3+\frac{2\pi}3\right) \\
&=\left(-\frac{a_n}2-\frac{\sqrt{3}}2\cos\frac{2n\pi}3\right)+\left(-\frac12\sin\frac{2n\pi}3+\frac{\sqrt{3}}2\cos\frac{2n\pi}3\right) \\
&=-\frac{a_n}2-\frac12\sin\frac{2n\pi}3=-\frac12b_n. \end{align*}
因此数列$\left\{a_n+\sin\frac{2n\pi}3\right\}$是首项为 $\frac{\sqrt{3}}2$,公比为$-\frac12$的等比数列.

取$q_{n}=-\frac{\sqrt{3}}{2}\left(-\frac{1}{2}\right)^{n-1}$,
则$a_{n}+\sin\frac{2n\pi}{3}=-q_{n}$,即 $a_{n}+q_{n}=-\sin\frac{2n\pi}{3}$,
因此$\{a_n+q_n\mid n\in\mathbf{N} ^\ast\}=\left\{0,\frac{\sqrt{3}}2,-\frac{\sqrt{3}}2\right\}$.
所以数列$\{a_n\}$具有$P(3)$性质.

(ii) $\{a_n\}$的通项公式是 $a_n=\frac{\sqrt{3}}2\cdot\left(-\frac12\right)^{n-1}
-\sin\frac{2n\pi}3$.

取$c_n=\sin\frac{2n\pi}3$,当$k\in\mathbf{N}$时,
\begin{align*}
&c_{3k+1}+c_{3k+2}+c_{3k+3} \\
&=\sin\frac{2(3k+1)\pi}3+\sin\frac{2(3k+2)\pi}3+\sin\frac{2(3k+3)\pi}3 \\
&=\sin\frac{2\pi}3+\sin\frac{4\pi}3+\sin(2\pi) =0, \end{align*}
所以$c_1+c_2+\cdots+c_n$的所有可能取值为
$c_{1}=\frac{\sqrt{3}}{2}$, $c_{1}+c_{2}=0$, $c_{1}+c_{2}+c_{3}=0$.

由于
\begin{align*}
S_{n}& =\frac{\sqrt3}2\left[1+\left(-\frac12\right)^1+\cdots+\left(-\frac12\right)^{n-1}\right]-(c_1+c_2+\cdots+c_n) \\
&=\frac{\sqrt{3}}{2}\cdot\frac{1-(-\frac{1}{2})^n}{1-(-\frac{1}{2})}-(c_1+c_2+\cdots+c_n) \\
&=\frac{\sqrt{3}}{3}\cdot\left[1-\left(-\frac{1}{2}\right)^n\right]
-(c_1+c_2+\cdots+c_n).
\end{align*}

因此,可以取$p_n=\frac{\sqrt{3}}{3}\left(-\frac{1}{2}\right)^n$,它是首项为$-\frac{\sqrt{3}}{6}$,公比为$-\frac{1}{2}$的等比数列,并且集合 $\{S_n+p_n\mid n\in\mathbf{N}^\ast\}
=\left\{\frac{\sqrt{3}}{3},
-\frac{\sqrt{3}}{6}\right\}$恰有两个元素.

(2)记集合$X_k=\{T_n+c_n\mid n\in\mathbf{N} ^\ast\}=\{x_1,x_2,\cdots,x_k\}$,其中$c_n=c_1\cdot q^{n-1}$.当$n\geqslant 2$时,
\begin{align*}
p_{n}&=T_n-T_{n-1}=(T_n+c_n)-(T_{n-1}+c_{n-1})
-(c_n-c_{n-1})\\
&=(T_n+c_n)-(T_{n-1}+c_{n-1})-c_1
\left(1-\frac1q\right)q^{n-1}.
\end{align*}

\ding{172} 若$q\neq1$,取$d_n=c_1\left(1-\frac1q\right)q^{n-1}$,则$\{d_n\}$ 是等比数列,并且当$n\geqslant 2$时,
$$
p_n+d_n=(T_n+c_n)-(T_{n-1}+c_{n-1})\in\{x-y\mid x,y\in X_k\}.
$$

于是 $\{p_n+d_n\mid n\in\mathbf{N}^\ast\}\subseteq\{p_1+d_1\} \cup\{x-y\mid x,y\in X_k\}$.

因此$p_n+d_n$的不同取值最多只有不超过 $k^2+1$个,故存在正整数 $m=k^2+1$,使得$\{p_n\}$具有$P(m)$性质.

\ding{173} 若$q=1$,则当$n\geqslant 2$时, $p_n= (T_n+c_n)-(T_{n-1}+c_{n-1})\in \{x-y\mid x,y\in X_k\}$.

取$d_n=(-1)^{n-1}$,则 $\{p_n+d_n\mid n\in\mathbf{N}^\ast\}\subseteq\{p_1+1\}\cup
\{x-y+1\mid x,y\in X_k\}\cup\{x-y-1\mid x,y\in X_k\}$.

因此$p_n+d_n$的不同取值最多只有不超过$2k^2+1$个,故存在正整数$m=2k^2+1$,使得$\{p_n\}$具有$P(m)$性质.

综上所述,若数列$\{T_n\}$具有$P(k)$性质,则存在正整数 $m=2k^2+1$,使得$\{p_n\}$具有$P(m)$性质.

\textbf{注1:}在$\{x-y\mid x,y\in X_k\}$中,当$x=y$ 时, $x-y=0$,可以排除掉$k-1$个重复的情况.不过由于$P(k)$ 性质的定义是“不超过$k$个”,所以是否排除掉有限个不会对解答造成影响.

\textbf{注2:}第(2) 问需讨论公比是否为 1,因为如果 $\{c_n\}$是常数列,那么$c_n-c_{n-1}$恒为 0,它就不是等比数列了.此时需要构造一个$d_n=(-1)^{n-1}$出来.

\textbf{注3:}原本第(1)问设置为如下,满分为7分(第(2)问满分为5分):记数列$\{a_n\}$的前$n$项和为$S_n$.若数列 $\{a_n\}$满足 $a_1=0$, $a_{n+1}=-\frac{a_n}2+\frac12(-1)^n\ (n\in\mathbf{N}^\ast)$,

证明:

(i)数列 $\{a_n+(-1)^n\}$ 为等比数列,且数列 $\{a_n\}$ 具有 $P(2)$ 性质;

(ii)数列$\{S_n\}$具有$P(2)$性质.

解答如下: (1) (i)设$b_n=a_n+(-1)^n$,则$b_1=-1$,并且
\begin{align*}
b_{n+1}& =a_{n+1}+(-1)^{n+1}=-\frac{a_n}2+\frac12(-1)^n-(-1)^n \\
&=-\frac{a_n}2-\frac12(-1)^n =-\frac12b_{n}.
\end{align*}

因此数列 $\{a_n+(-1)^n\}$是首项为$-1$,公比为 $-\frac{1}{2}$的等比数列,故$a_n+(-1)^n=-\left(-\frac12\right)^{n-1}$.

整理得$a_n+\left(-\frac12\right)^{n-1}=(-1)^{n-1}$,
于是集合 $\left\{a_n+\left(-\frac12\right)^{n-1}\mid n\in\mathbf{N}^\ast\right\}=\{-1,1\}$,
所以数列$\{a_n\}$具有$P(2)$性质.

(ii)由(i), $a_n=(-1)^{n-1}-\left(-\frac12\right)^{n-1}$, 所以
$$
S_n=\frac{1-\left( -1 \right) ^n}{1-\left( -1 \right)}-\frac{1-\left( -\frac{1}{2} \right) ^n}{1-\left( -\frac{1}{2} \right)}=-\frac{1}{6}-\frac{1}{2}\left( -1 \right) ^n+\frac{2}{3}\left( -\frac{1}{2} \right) ^n.
$$

取数列$r_n=-\frac23\left( -\frac{1}{2} \right)^n$,则$\{r_n\}$是等比数列,并且
$$
S_n+r_n=-\frac16-\frac12(-1)^n.
$$
因此集合 $\{S_n+r_n\mid n\in\mathbf{N}^\ast\}
=\left\{-\frac{2}{3},\frac{1}{3}\right\}$. 所以数列$\{S_n\}$具有$P(2)$性质.
}

\section{闵可夫斯基距离}

闵可夫斯基距离又称为闵氏距离,是两组数据间距离的定义.设两组数据分别为$A=(a_1,a_2,\cdots,a_n)$
和$B=(b_1,b_2,\cdots,b_n)$,这两组数据间的闵氏距离定义为$d_{AB}(q)=\left[\sum_{k=1}^n|a_k-b_k|^q\right]^{\frac1q}$,
其中$q$表示阶数.

证明: $d_{AB}(q)+d_{BC}(q)\geqslant d_{AC}(q)$.

\Example{
(合肥市2024届高三第一次教学质量检查) “$q$-数”在量子代数研究中发挥了重要作用.设$q$是非零实数,对任意$n\in \mathbf{N}^\ast$,定义“$q$-数”
$$(n)_q=1+q+\cdots+q^{n-1}$$
利用“$q$-数”可定义“$q$-阶乘”
$$(n)!_q=(1)_q(2)_q\cdots (n)_q,\quad \text{且} (0)!_q=1.$$
和“$q$-组合数”,即对任意$k\in \mathbf{N},n\in \mathbf{N}^\ast,k\leqslant n$,
$$\binom{n}{k}_q=\frac{(n)!_q}{(k)!_q(n-k)!_q}.$$

(1)计算: $\binom{5}{3}_2$;

(2)证明:对于任意$k,n\in \mathbf{N}^\ast,k+1\leqslant n$,
$$\binom{n}{k}_q=\binom{n-1}{k-1}_q
+q^k\binom{n-1}{k}_q;$$

(3)证明:对于任意$k,m\in \mathbf{N},n\in \mathbf{N}^\ast,k+1\leqslant n$,
$$\binom{n+m+1}{k+1}_q-\binom{n}{k+1}_q
=\sum_{i=0}^{m}q^{n-k+i}\binom{n+i}{k}_q.$$
}{
(1)由定义可知,
\begin{align*}
{\binom{5}{3}}_{2}&=\frac{{\left(5\right)!}_{2}}
{{\left(3\right)!}_{2}{\left(2\right)!}_{2}}
=\frac{\left(1\right)_{2}\left(2\right)_{2}
\left(3\right)_{2}\left(4\right)_{2}\left(5\right)_{2}}
{\left[\left(1\right)_{2}\left(2\right)_{2}
\left(3\right)_{2}\right]
\left[\left(1\right)_{2}\left(2\right)_{2}\right]}\\
&=\frac{(4)_{2}(5)_{2}}{(1)_{2}(2)_{2}}
=\frac{\left(1+2+2^{2}+2^{3}\right)
\left(1+2+2^{2}+2^{3}+2^{4}\right)}
{1\times\left(1+2\right)}=155.
\end{align*}

(2)因为${\binom{n}{k}}_{q}=\frac{(n)!_{q}}{(k)!_{q}(n-k)!_{q}}
=\frac{(n)_{q}\cdot(n-1)!_{q}}{(k)!_{q}(n-k)!_{q}}$, \begin{align*}
{\binom{n-1}{k-1}}_{q}+q^{k}{\binom{n-1}{k}}_{q}
&=\frac{(n-1)!_{q}}{(k-1)!_{q}(n-k)!_{q}}
+\frac{q^{k}\cdot(n-1)!_{q}}{(k)!_{q}(n-k-1)!_{q}}\\
&=\frac{\left(n-1\right)!_{q}}{\left(k\right)!_{q}
\left(n-k\right)!_{q}}
\left[\left(k\right)_{q}+q^{k}\cdot
\left(n-k\right)_{q}\right].
\end{align*}
又$(k)_{q}+q^{k}\cdot(n-k)_{q}=1+q+\cdots+q^{k-1}
+q^{k}(1+q+\cdots+q^{n-k-1})=1+q+\cdots+q^{n-1}
=\left(n\right)_q$,所以${\binom nk}_q={\binom{n-1}{k-1}}_q+q^k{\binom{n-1}k}_q$.

(3)由定义得:对任意$k\in\mathbf{N}$, $n\in\mathbf{N} ^\ast$, $k\leqslant n$, ${\binom{n}{k}}_{q}={\binom{n}{n-k}}_{q}$.

结合(2)可知
$${\binom nk}_q={\binom n{n-k}}_q={\binom{n-1}{n-k-1}}_q
+q^{n-k}{\binom{n-1}{n-k}}_q
={\binom{n-1}{k}}_{a}+q^{n-k}{\binom{n-1}{k-1}}_{q},$$
即${\binom{n}{k}}_{q}={\binom{n-1}{k}}_{q}
+q^{n-k}{\binom{n-1}{k-1}}_{q}$,
也即${\binom{n}{k}}_{q}-{\binom{n-1}{k}}_{q}
=q^{n-k}{\binom{n-1}{k-1}}_{q}$.

所以${\binom{n+m+1}{k+1}}_{q}-{\binom{n+m}{k+1}}_{q}
=q^{n+m-k}{\binom{n+m}{k}}_{q}$,

${\binom{n+m}{k+1}}_{q}-{\binom{n+m-1}{k+1}}_{q}
=q^{n+m-1-k}{\binom{n+m-1}{k}}_{q}$,

$\cdots \cdots$

${\binom{n+1}{k+1}}_{q}-{\binom{n}{k+1}}_{q}
=q^{n-k}{\binom{n}{k}}_{q}$.

上述$m+1$个等式两边分别相加得:
$$
{\binom{n+m+1}{k+1}}_q-{\binom{n}{k+1}}_q
=\sum_{i=0}^mq^{n-k+i}{\binom{n+i}{k}}_q.
$$
}

\Example{
This is an example.
}{
What is truth? Can anything be proven?
}

\section{集合间的距离}

(2021 China Girls Math Olympiad) Given a finite set $S$, $P(S)$ denotes the set of all the subsets of $S$. For any $f:P(S)\rightarrow \mathbb{R}$ ,prove the following inequality:$$\sum_{A\in P(S)}\sum_{B\in P(S)}f(A)f(B)2^{\left| A\cap B \right|}\geq 0.$$

Got literally the same solution. The idea is that $2^{|A \cap B|}$ is just size of $P(A \cap B)$, so we might want to rearrange the sigmas:
\begin{align*}
\sum_{A, B \in P(S)}f(A)f(B)2^{|A \cap B|} &= \sum_{A, B \in P(S)}\sum_{T \subseteq (A \cap B)}f(A)f(B) \\
&= \sum_{T \subseteq S}\sum_{T \subseteq A, B \subseteq S}f(A)f(B) \\
&= \sum_{T \subseteq S} \left( \sum_{T \subseteq A \subseteq S}f(A) \right)^2 \ge 0.
\end{align*}The equality holds iff $f \equiv 0$, this can be proven inductively.

\Example{
(2010年北京理科)已知集合$S_n=\{X\mid X= (x_1,x_2,\cdots,x_n),x_i\in \{0,1\},i=1,2,\cdots,n\}\ (n\geqslant 2)$,
对于$A=(a_1,a_2,\cdots a_n)$, $B=(b_{1},b_{2},\ldots b_{n})\in S_{n}$,
定义$A$与$B$的差为
$A-B=\left(|a_{1}-b_{1}|,
|a_{2}-b_{2}|,\cdots,|a_{n}-b_n|\right)$; $A$与$B$之间的距离为$d(A,B)=\sum_{i=1}^n |a_{i}-b_{i}|$.

(I)证明: $\forall A,B,C\in S_n$,有$A-B\in S_n$,且$d(A-C,B-C)=d(A,B)$;

(II)证明: $\forall A,B,C\in S_n$, $d(A,B),d(A,C),d(B,C)$三个数中至少有一个是偶数;

(III)设$P \subseteq S_n$, $P$中有$m\ (m\geqslant 2)$个元素,记$P$中所有两元素间距离的平均值为$\overline{d} (P)$.证明: $\overline {d}(P)\leqslant \frac {mn}{2(m-1)}$.
}{
证明: (I)设$A=(a_1,a_2,\cdots,a_n)$, $B=(b_1,b_2,\cdots,b_n)$,
$C=(c_1,c_2,\cdots,c_n)\in S_n$,
因为$a_i,b_i\in\{0,1\}$,所以$|a_i-b_i|\in\{0,1\},(i=1,2,\cdots,n)$,
从而$A-B=(|a_1-b_1|,|a_2-b_2|,\cdots,|a_n-b_n|)\in S_n$.

又$d(A-C,B-C)=\sum_{i=1}^{n}||a_{i}-c_{i}|-|b_{i}-c_{i}||$,
由题意知$a_i,b_i,c_i\in\{0,1\}\ (i=1,2,\cdots,n)$.

当$c_i=0$时, $||a_i-c_i|-|b_i-c_i||=|a_i-b_i|$;

当$c_{i}=1$时, $||a_i-c_i|-|b_i-c_i||=|1-a_i-(1-b_i)|=|a_i-b_i|$.

所以$d(A-C,B-C)=\sum_{i=1}^{n}|a_{i}-b_{i}|=d(A,B)$.

(II)设$A=(a_1,a_2,\cdots,a_n)$, $B=(b_1,b_2,\cdots,b_n)$, $C=(c_1,c_2,\cdots,c_n)\in S_n$,
$d(A,B)=k$, $d(A,C)=l$, $d(B,C)=h$.

记$O=(0,0,\cdots,0)\in S_n$,由(I)可知
$d(A,B)=d(A-A,B-A)=d(O,B-A)=k$,
$d(A,C)=d(A-A,C-A)=d(O,C-A)=l$,
$d(B,C)=d(B-A,C-A)=h$,

所以$|b_i-a_i|\ (i=1,2,\cdots,n)$中1的个数为$k$, $|c_i-a_i|\ \left(i=1,2,\cdots,n\right)$的$1$的个数为$l$.

设$t$是使$|b_i-a_i|=|c_i-a_j|=1$成立的$i$的个数,则$h=l+k-2t$,
由此可知, $k,l,h$三个数不可能都是奇数,
即$d(A,B),d(A,C),d(B,C)$三个数中至少有一个是偶数.

(III) $\overline{d}(P)=\frac1{2C_{m}^{2}}\sum _{A,B\in P}d(A,B)$,其中$\frac{1}{2}\sum_{A,B\in P}d(A,B)$表示$P$中所有两个元素间距离的总和,
设$P$中所有元素的第$i$个位置的数字中共有$t_i$个$1$, $m-t_i$个$0$,则$\frac{1}{2}\sum_{A,B\in P}d(A,B)=\sum_{i=1}^{n}t_{i}(m-t_{i})$.

由于$t_{i}(m-t_{i})\leqslant \frac{m^{2}}{4}\ (i=1,2,\cdots,n)$,
所以$\frac{1}{2}\sum_{A,B\in P}d(A,B)\leqslant\frac{nm^{2}}{4}$,
从而
$$\overline{d}(P)=\frac{1} {2C_{m}^{2}}\sum_{A,B\in P}d(A,B)\leqslant
\frac{nm^2}{4C_{m}^{2}}=\frac{mn}{2(m-1)}.$$
}

\Example{
(台州2024年高三二模)设$A,B$是两个非空集合,如果对于集合$A$中的任意一个元素$x$,按照某种确定的对应关系 $f$,在集合$B$中都有唯一确定的元素 $y$和它对应,并且不同的$x$对应不同的$y$;同时$B$中的每一个元素 $y$,都有一个$A$中的元素$x$与它对应,则称 $f:A{\to}B$为从集合$A$到集合$B$的一一对应,并称集合$A$与$B$等势,记作$\overline{\overline{A}}=\overline{\overline{B}}$.若集合$A$与$B$之间不存在一一对应关系,则称$A$与$B$不等势,记作$\overline{\overline{A}}\neq\overline{\overline{B}}$.

例如:对于集合 $A=\mathbf{N}^\ast, B=\left\{2n\left|n\in\mathbf{N}^\ast\right.\right\}$, 存在一一对应关系 $y=2x\ (x\in A,y\in B)$,因此
$\overline{\overline{A}}=\overline{\overline{B}}$.

(1)已知集合$C=\left\{(x,y)\left|x^{2}+y^{2}=1\right.\right\}$, $D=\left\{(x,y)\left|\frac{x^{2}}{4}+\frac{y^{2}}{3}=1\right.\right\}$,
试判断$\overline{\overline{C}}=\overline{\overline{D}}$是否成立?请说明理由;

(2)证明: \ding{172} $\overline{\overline{(0,1)}}
=\overline{\overline{(-\infty,+\infty)}}$;

\ding{173} $\overline{\overline{\mathbf{N}^\ast}}\neq \overline{\overline{\{x\mid x\subseteq\mathbf{N}^\ast\}}}$.
}{
(1)设$P(x_{0},y_{0})\in C$, $Q=(x,y)\in D$,令$\begin{cases}
x=2x_{0},\\
y=\sqrt{3}y_{0},
\end{cases}$
则$C$与$D$存在一一对应,所以集合$\overline{C}=\overline{D}$.

(2) \ding{172}取函数$y=\tan\pi\left(x-\frac12\right)$,其中$x\in(0,1)$, $y\in(-\infty,+\infty)$,两个集合之间存在一一对应,
故$\overline{\overline{(0,1)}}
=\overline{\overline{(-\infty,+\infty)}}$.

备注:函数举例不唯一,只要保证定义域为$(0,1)$,值域为$\mathbf{R}$即可,

如: $y=\begin{cases}\frac{1} {x}-2, &0<x\leqslant\frac{1}{2},\\
\frac{1}{x-1}+2, &\frac{1}{2}<x<1.
\end{cases}$
或$y=\begin{cases}
\ln 2x, &0<x\leqslant\frac{1} {2},\\
-\ln(2-2x),&\frac{1}{2}<x<1.
\end{cases}$
等等均可.

\ding{173}设$A=\mathbf{N}^{\ast}$, $B=\{x|x\subseteq\mathbf{N}^{\ast}\}$,
假设$\overline{\overline{A}}=\overline{\overline{B}}$,即存在对应关系$f:A\to B$为一一对应,对于集合$B$中的元素$\{1\},\{2\},\{1,2\}$,至少存在一个$x\in A\ (x\neq1$,且$x\neq 2)$与这三个集合中的某一个对应,所以集合$A$中必存在$x\notin f(x)$.

记$D=\{x\in A|x\notin f(x)\}$,则$D\subseteq A$,故$D\in B$,

从而存在$a\in A$,使得$f(a)=D$;

若$a\in D$,则$a\notin f(a)=D$,矛盾;

若$a\notin D$,则$a\in f(a)=D$,矛盾.

因此,不存在$A$到$B$的一一对应,所以$\overline{\overline{A}}\neq\overline{\overline{B}}$.
}

\Example{
(2024年石家庄二模)设集合$M$是一个非空数集,对任意$x,y\in M$,定义$\rho(x,y)=|x-y|$,称$\rho$为集合$M$的一个度量,称集合$M$为一个对于度量$\rho$而言的度量空间,该度量空间记为$(M,\rho)$.

定义1:若 $f:M\to M$是度量空间$(M,\rho)$上的一个函数,且存在 $\alpha\in(0,1)$,使得对任意$x,y\in M$,均有: $\rho(f(x),f(y))\leqslant\alpha\rho(x,y)$,则称$f$是度量空间$(M,\rho)$上的一个“压缩函数”.

定义2:记无穷数列$a_0,a_1,a_2,\cdots$为$\left\{a_n\right\}_{n=0}^{+\infty}$,若$\left\{a_n\right\}_{n=0}^{+\infty}$是度量空间$\left(M,\rho\right)$上的数列,且对任意正实数 $\varepsilon>0$,都存在一个正整数$N$,使得对任意正整数 $m,n\geqslant N$,均有 $\rho(a_m,a_n)<\varepsilon$,则称$\{a_n\}_{n=0}^{+\infty}$是度量空间$(M,\rho)$上的一个“基本数列”.

(1)设 $f(x)=\sin x+\frac12$,证明: $f$是度量空间$\left(\left[\frac12,2\right],\rho\right)$上的一个“压缩函数”;

(2)已知 $f:\mathbf{R}\to\mathbf{R}$是度量空间 $(\mathbf{R},\rho)$上的一个压缩函数,且 $a_0\in\mathbf{R}$,定义 $a_{n+1}=f\left(a_n\right)$, $n=0,1,2,\cdots$,证明: $\left\{a_{n}\right\}_{n=0}^{+\infty}$为度量空间$\left(\mathbf{R},\rho\right)$上的一个“基本数列”.
}{
(1)由正弦函数的性质可知: $f(x)=\sin x+\frac12$ 在$\left[\frac12,\frac\pi2\right]$上单调递增,在$\left[\frac\pi2,2\right]$上单调递减,所
以$f_{\min}\left(x\right)=\min\left\{\sin\frac{1}{2}
+\frac{1}{2},\sin2+\frac{1}{2}\right\}
=\sin\frac{1}{2}+\frac{1}{2}>\frac{1}{2}$,
且$f_{\max}\left(x\right)=\sin\frac{\pi}{2}+\frac{1}{2}
=\frac{3}{2}<2$,
故$f(x)$在$\left[\frac12,2\right]$上的值域是$\left[\sin\frac12+\frac12,\frac32\right]
\subseteq\left[\frac12,2\right]$,故$f$是从$\left[\frac12,2\right]$
到$\left[\frac12,2\right]$的函数.

另一方面,我们证明存在$\alpha\in (0,1)$,对任意$x,y\in\left[\frac12,2\right]$,都有$\rho(f(x),f(y))\leqslant\alpha\rho(x,y)$.

取$\alpha=\cos\frac{1}{2}$,则对任意$x,y\in\left[\frac{1}{2},2\right]$,不妨设$x<y$,分两种情形讨论:

\ding{172}当$\sin x\leqslant\sin y$时,令$F(x)=\alpha x-\sin x$,则$F'(x)=\alpha-\cos x\geqslant \alpha-\cos\frac{1}{2}=0$,所以$F(x)$在
$x\in\left[\frac{1}{2},2\right]$上单调递增,因为$x<y$,所以$F(x)<F(y)$,即
$\alpha x-\sin x<\alpha y-\sin y\Rightarrow \sin y-\sin x<\alpha y-\alpha x$,即: $\rho(f(x),f(y))\leqslant \alpha\rho(x,y)$.

\ding{173} 当$\sin x>\sin y$时,令$G(x)=\alpha x+\sin x$,则
$G'(x)=\alpha+\cos x\geqslant \alpha+\cos 2=\cos\frac{1}{2}-\cos(\pi-2)>0$,
所以$G(x)$在$x\in\left[\frac12,2\right]$上单调递增,因为$x<y$,所以$G(x)<G(y)$,即
$\alpha x+\sin x<\alpha y+\sin y\Rightarrow \sin x-\sin y<\alpha y-\alpha x$,即: $\rho(f(x),f(y))\leqslant \alpha\rho(x,y)$.

综上所述,对任意$x,y\in\left[\frac{1}{2},2\right]$, $\rho(f(x),f(y))\leqslant\cos\frac{1}{2}\rho(x,y)$,所以$f$是度量空间$\left(\left[\frac12,2\right],\rho\right)$上的一个压缩函数.

(2)因为$f$是度量空间$(R,\rho)$上的一个压缩函数,故必存在$\alpha\in(0,1)$,使得对任意$x,y\in \mathbf{R}$,均有: $\rho(f(x),f(y))\leqslant
\alpha\rho (x,y)$, 即: $|f(x)-f(y)|\leqslant \alpha |x-y|$.

因为: $a_{n+1}=f(a_n)$,所以:
$$
\left|a_{k+1}-a_{k}\right|=\left|f\left(a_{k}\right)
-f\left(a_{k-1}\right)\right|\leqslant
\alpha\left|a_{k}-a_{k-1}\right|\leqslant
\alpha^{2}\left|a_{k-1}-a_{k-2}\right|
\leqslant\cdots\leqslant
\alpha^{k}\left|a_{1}-a_{0}\right|,
$$
(其中$k$为正整数).

由绝对值三角不等式可知:对任意$m>n\geqslant N$,有:
\begin{align*}
|a_{m}-a_{n}| &=\left|a_{m}-a_{m-1}+a_{m-1}-a_{m-2}+\cdots
+a_{n+1}-a_{n}\right|\\
&\leqslant
\left|a_{m}-a_{m-1}\right|+\left|a_{m-1}-a_{m-2}\right|
+\cdots+\left|a_{n+1}-a_{n}\right|\\
&\leqslant \alpha^{m-1}\left|a_{1}-a_{0}\right|
+\alpha^{m-2}\left|a_{1}-a_{0}\right|+\cdots
+\alpha^{n}\left|a_{1}-a_{0}\right|
=\frac{\alpha^{n}\left(1-\alpha^{m-n}\right)}
{1-\alpha}\left|a_{1}-a_{0}\right|.
\end{align*}

又因为$\alpha\in(0,1)$,所以$\alpha^n\leqslant \alpha^N$,故: $|a_{m}-a_{n}|\leqslant\frac{\alpha^{n}
\left(1-\alpha^{m-n}\right)}{1-\alpha}|a_{1}-a_{0}|
\leqslant\frac{\alpha^{n}}{1-\alpha}|a_{1}-a_{0}|
\leqslant\frac{\alpha^{N}}{1-\alpha}|a_{1}-a_{0}|$.

\ding{172} 当$a_1=a_0$时,对任意$m>n\geqslant N$, $|a_m-a_n|\leqslant\frac{\alpha^N}{1-\alpha}
|a_1-a_0|=0$,故$|a_m-a_n|=0$,所以对$\forall\varepsilon >0$,对任意正整数$N$,当$m>n\geqslant N$时,均有$|a_m-a_n|<\varepsilon$,即$\rho(a_m,a_n)<\varepsilon$.

\ding{173} 当$a_1\neq a_0$时,对$\forall\varepsilon>0$,取一个正整数$N>\log_{a}\frac{\varepsilon\left(1-\alpha\right)}
{\left|a_{1}-a_{0}\right|}$,
则$\alpha^{N}<\frac{\varepsilon\left(1-\alpha\right)}
{\left|a_{1}-a_{0}\right|}
\Rightarrow\frac{\alpha^{N}}{\left(1-\alpha\right)}
\left|a_{1}-a_{0}\right|<\varepsilon$,
则当$m>n\geqslant N$时,必有: $\rho (a_m,a_n)=|a_m-a_n|\leqslant \frac{\alpha^N} {1-\alpha}|a_1-a_0|<\varepsilon$.

综上所述,对任意正实数$\varepsilon>0$,都存在一个正整数$N$,使得对任意正整数$m,n\geqslant N$,均有$\rho(a_m,a_n)<\varepsilon$.故$\left\{a_n\right\}_{n=0}^{+\infty}$为度量空间$\left(\mathbf{R},\rho\right)$上的一个“基本数列”.
}

\Example{
(2024年海淀一模)已知$Q:a_1,a_2,\cdots,a_{m^2}\ (m\geqslant 2,m\in\mathbf{N}^\ast)$为有穷正整数数列,其最大项的值为$m$,且当$k=0,1,\cdots,m-1$时,均有$a_{km+i}\neq a_{km+j}\ (1\leqslant i<j\leqslant m)$.设$b_0=0$,对于$t\in\{0,1,\cdots,m-1\}$,定义
$b_{t+1}=\min\left\{n|n>b_t,a_n>t\right\}$,其中, $\min M$表示数集$M$中最小的数.

(1)若$Q:3,1,2,2,1,3,1,2,3$,写出$b_1,b_3$的值;

(2)若存在$Q$满足: $b_1+b_2+b_3=11$,求$m$的最小值;

(3)当$m=2024$时,证明:对所有$Q$, $b_{2023}\leqslant 20240$.
}{
(I)由$Q:3,1,2,2,1,3,1,2,3$, $b_0=0$,则$b_1=\min\left\{n\mid n>0,a_n>0\right\}$,故$b_1=1$, 则$b_2=\min\left\{n\mid n>1,a_n>1\right\}$,故$b_2=3$,
则$b_3=\min\{n\mid n>3,a_n>2\}$,故$b_3=6$;

(II)由题意知$m\geqslant 3$.

当$m=3$时,因为$a_1\geqslant 1$, $b_0=0$, $b_1=\min\left\{n\mid n>0,a_n>0\right\}$,
所以$b_1=1$.

则$b_2=\min\left\{n|n>1,a_n>1\right\}$,
因为$a_2\neq a_3$,且$a_2,a_3$均为正整数,所以$a_2>1$,或$a_3>1$.所以$b_2\leqslant 3$.

又$b_3=\min\left\{n\mid n>b_2,a_n>2\right\}$,因为$a_4,a_5,a_6$是互不相等的正整数,所以必有一项大于$2$.
所以$b_3\leqslant 6$.

所以$b_1+b_2+b_3\leqslant 10$,不合题意.

当$m=4$时,对于数列$Q:4,1,3,2,1,2,3,4,1,2,3,4,1,2,3,4$
有$b_1+b_2+b_3=1+3+7=11$.

综上所述, $m$的最小值为$4$.

(III)因为$b_{t+1}=\min\left\{n\mid n>b_t,a_n>t\right\},t=0,1,\cdots,2023$,
所以$b_{t+1}>b_t,t=0,1,\cdots,2023$.

(i)若$b_{t+1}\leqslant 2024$,则当$n<b_{t+1}$时,至少以下情况之一成立;

\ding{172} $a_n\leqslant t$,这样的$n$至少有$t$个;

\ding{173} 存在$i\leqslant t,b_i=n$,这样的$n$至多有$t$个.

所以小于$b_{t+1}$的$n$至多有$2t$个.

所以$b_{t+1}\leqslant t+t+1=2t+1$.

令$2t+1\leqslant 2024$,解得$t+1\leqslant 1012$.

所以$b_{1012}\leqslant 2024$,

(ii)对$k\in\mathbf{N}^\ast$,若$b_t\leqslant 2024k<b_{t+1}$,且$2024k<b_{t+l+1}\leqslant 2024(k+1)$, 因为$b_{t+l+1}=\min\left\{n\mid n>b_{t+l},a_n>t+l\right\}$,所以当$n\in (2024k, b_{t+l+1})$时,至少以下情况之一成立:

\ding{172} $a_n\leqslant t+l$,这样的$n$至多有$t+l$个;

\ding{173} 存在$i$, $t<i\leqslant t+l$且$b_i=n$,这样的$n$至多有$l$个.

所以$b_{t+l+1}\leqslant 2024k+t+l+l+1=2024k+t+2l+1$.

令$t+2l+1\leqslant 2024$,解得$l\leqslant\left[\frac{2023-t}{2}\right]$,即$t+l+1\leqslant \left[\frac{2025+t}{2}\right]$,
其中$[x]$表示不大于$x$的最大整数.

所以当$b_t\leqslant 2024k<b_ {t+1}$时, $b_{\left[\frac{2025+t}{2}\right]\leqslant 2024(k+1)}$;

综上所述,定义$C_{1}=1012$, $C_{k+1}=\left[\frac{2025+C_{k}}{2}\right]$,
则$b_{C_{k}}\leqslant 2024k$.

依次可得: $C_ {2}=1518$, $C_{3}=1771$, $C_{4}=1898$, $C_{5}=1961$, $C_{6}=1993$, $C_{7}=2009$, $C_8=2017$, $C_9=2021$, $C_{10}=2023$.

所以$b_{2023}\leqslant 2024\times 10=20240$.
}

\textbf{注:}这里最大项的值为$m$,且当$k=0,1,\cdots,m-1$时,均有$a_{km+i}\neq a_{km+j}\ (1\leqslant i<j\leqslant m)$是指将这$m^2$个数的数列分成$m$组,每组的最大值都是$m$,且每个数互不相同.

\Example{
This is an example.
}{
What is truth? Can anything be proven?
}

\Example{
(清华附 2024 年高一上学期期中)对非空整数集合$M$及$k\in\mathbf{N}$,定义$M\oplus k=\{m+t|m\in M,t=-k,-k+1,\cdots,k\}$,对于非空整数集合$A$, $B$,定义$d(A,B)=\min\left\{k\in\mathbf{N}|A\subseteq B\oplus k,B\subseteq A\oplus k\right\}.$

(1)设$M=\{2,4,6\}$,请直接写出集合$M\oplus 1$;

(2)设$A=\{1,2,3,4,\cdots,100\}$, $d(A,B)=1$,求出非空整数集合$B$的元素个数的最小值;

(3)对三个非空整数集合$A$, $B$, $C$,若$d(A,B)=4$且$d(B,C)=1$,求$d(A,C)$所有可能取值.
}{
(1)若$M=\{2,4,6\}$,则由集合新定义可知$M\oplus 1=\{1,3,5\}\cup\{2,4,6\}\cup\{3,5,7\}
=\{1,2,3,4,5,6,7\}$.

(2)设$B$有$|B|$个元素,下证$|B|_{\min}=34$.

一方面, $B=\{2,5,8,\cdots,98,101\}$,则$A$不包含于$B\oplus 0=B$,所以$d(A,B)\neq 0$,即$d(A,B)\geqslant 1$,而$B\subseteq A\oplus1=\{0,1,2,3,4,\cdots,101\}$,
$A\subseteq B\oplus 1=\{1,2,3,4,\cdots,102\}$,
这表明了$d(A,B)=1$满足题意,此时$|B|=\frac{101-2}{3}+1=34$,故$|B|_{\min}=34$;

另一方面,若$|B|=j\leqslant 33$,不妨设$B=\{b_1,b_2,\cdots,b_j\}$且$b_1<b_2<\cdots<b_j$,由题意可知$A\subseteq B\oplus 1=\{b_1-1,b_1,b_1+1\}\cup\{b_2-1,b_2,b_2+1\}
\cup\cdots\cup\{b_j-1,b_j,b_j+1\}$,

而$B\oplus 1$最多含有$3j\leqslant 99$个元素,当且仅当$\{b_k-1,b_k,b_k+1\},(1\leqslant k\leqslant j)$两两不同且$|B|=j=33$时,等号成立,但这与$A$有$100$个元素矛盾,所以$|B|=j\geqslant 34$.

综上所述,非空整数集合$B$的元素个数的最小值是34.

(3)一方面,先来证明$(M\oplus k)\oplus l\subseteq M\oplus (k+l)$, $M\oplus k=\{m+t|m\in M,t=-k,-k+1,\cdots,k\}=\{n\in\mathbf{Z}|\exists m\in M,|n-m|\leqslant k\}$,因此只要$M_1\subseteq M_2$,就有$M_1\oplus k\subseteq M_2\oplus k$,

而$\forall x\in ( M\oplus k) \oplus l$, $\exists p\in M\oplus k$, $|x- p|\leqslant l$,
所以$\exists m\in M$, $|p-m|\leqslant k$,
所以$|x-m|=|x-p+p-m|\leqslant |x-p|+|p-m|\leqslant l+k$,
即$\forall x\in M\oplus (k+l)$,
从而$(M\oplus_{k})\oplus l\subseteq M\oplus (k+l)$.

另一方面,如果$d(A,B)=p$, $d(B,C)=q$, $d(A,C)=r$,
那么$A\subseteq B\oplus p$, $B\subseteq C\oplus q$, $B\oplus p\subseteq (C\oplus q)\oplus p\subseteq C\oplus (p+q)$,
从而$A\subseteq C\oplus (p+q)$,同理$C\subseteq A\oplus(p+q)$,因此由定义可得$d\left(A,C\right)=r\leqslant d\left(A,B\right)+d\left(B,C\right)=p+q$,即$d$满足距离的三角不等式.

所以在本题中, $d(A,C)\leqslant d(A,B)+d(B,C)=4+1=5$, $d(A,C)\geqslant d(A,B)-d(B,C)=4-1=3$,
即$d(A,C)\in\{3,4,5\}$,

取$A=\{0\},B=\{4\},C=\{5\}$,可知$d(A,C)=5$可能成立;

取$A=\{0\},B=\{4\},C=\{3\}$,可知$d(A,C)=3$可能成立;

取$A=\{0\},B=\{4\},C=\{3,4\}$,可知$d(A,C)=4$可能成立.

综上所述, $d(A,C)$所有可能取值为3或4或5.
}

\Example{
This is an example.
}{
What is truth? Can anything be proven?
}

\section{函数与数列递推}

假设$n\in \mathbf{N}$,那么$f(nx)\leqslant nf(x)$, $f(x/n)\geqslant 1/nf(x)$.用归纳法直接验证.

%https://zhuanlan.zhihu.com/p/32887828

在数学中,次可加性是一种常见且有用的性质.满足$f(x+y)\leqslant f(x)+f(y)$的函数$f$称为次可加的.显然范数就是次可加的.另一个例子是平方根函数,因为$\sqrt{x+y}\leqslant \sqrt{x}+\sqrt y$.把数列$\{a_n\}$看作定义在$\mathbb N_+$上的函数 $f(n)=a_n$,那么数列的次可加性就是$f(m+n)\leqslant f(m)+f(n)$.

引理:对次可加数列$\{f(n)\}$,极限$\lim_{n \to \infty}{\frac{f(n)}{n}}$存在,且等于$\inf_{n \in \mathbb{N}_+}{\frac{f(n)}{n}}$ (允许极限是$-\infty$,例如$f(n)=\ln n!$).

证明:首先,上极限$\varlimsup_{n \to \infty}{\frac{f(n)}{n}}$总是存在的.

取$\left\{ \frac{f(n)}{n} \right\}$的一个收敛到上极限的子列$\left\{\frac{f(n_k)}{n_k}\right\}$,即满足$\lim_{k \to \infty}{\frac{f(n_k)}{n_k}} = \varlimsup_{n \to \infty}{\frac{f(n)}{n}}$.
对固定的$n$,作带余除法$n_k = q_kn +r_k$,由次可加性得
\begin{align*}
\frac{f(n_k)}{n_k} &= \frac{f(q_kn+r_k)}{q_kn+r_k} \\
&\leqslant \frac{q_kf(n)+f(r_k)}{q_kn+r_k} \\
&\leqslant \frac{q_kf(n)+f(r_k)}{q_kn} \\
&= \frac{f(n)}n+\frac{f(r_k)}{q_kn}.
\end{align*}
余数$r_k$满足$0 \le r_k < n$,在$n$固定的情况下, $r_k$ 只有有限种取值,因而$f(r_k)$是有界的.

当$k \to \infty$时, $n_k\to\infty$,所以$q_k \to \infty$.

所以$\lim_{k\to\infty}\frac{f(n_k)}{n_k} \leqslant \lim_{k\to\infty}\bigg(\frac{f(n)}{n}
+\frac{f(r_k)}{q_kn}\bigg)=\frac{f(n)}{n}$.

即$\varlimsup_{n \to \infty}{\frac{f(n)}{n}} \leqslant \frac{f(n)}{n}$,这对任意$n$都成立.

所以$\varlimsup_{n \to \infty}{\frac{f(n)}{n}} \leqslant \inf_{n \in \mathbb{N}_+}{\frac{f(n)}{n}}$.

由上下极限的性质知$\inf_{n \in \mathbb{N}_+}{\frac{f(n)}{n}}\leqslant \varliminf_{n \to \infty}{\frac{f(n)}{n}}\leqslant\varlimsup_{n \to \infty}{\frac{f(n)}{n}}$.

所以$\varlimsup_{n \to \infty}{\frac{f(n)}{n}} =\varliminf_{n \to \infty}{\frac{f(n)}{n}}=\inf_{n \in \mathbb{N}_+}{\frac{f(n)}{n}}$.

即极限存在且等于$\inf_{n \in \mathbb{N}_+}{\frac{f(n)}{n}}$.证毕.

参考文献: Edward R. Scheinerman, Daniel H. Ullman. Fractional Graph Theory.

\Example{
(2020年海淀高一期末)已知函数$f\left(x\right)$的图象在定义域$(0,+\infty)$上连续不断.若存在常数$T>0$,使得对于任意的$x>0$, $f\left(Tx\right)=f\left(x\right)+T$恒成立,称函数$f(x)$满足性质$P(T)$.

(1)若$f(x)$满足性质$P(2)$,且$f(1)=0$,求$f(4)+f\left(\frac{1}{4}\right)$的值;

(2)若$f(x)=\log_{1.2}x$,试说明至少存在两个不等的正数$T_1,T_2$,同时使得函数$f(x)$满足性质$P(T_1)$和$P(T_2)$. (参考数据: $1.2^4=2.0736)$

(3)若函数$f(x)$满足性质$P(T)$,求证:函数$f(x)$存在零点.
}{
What is truth? Can anything be proven?
}

\Example{
This is an example.
}{
What is truth? Can anything be proven?
}

1993-2018年河北省高中数学竞赛试卷及答案集锦
%https://mp.weixin.qq.com/s?__biz=Mzg4MTExODA4MQ==&mid=2247529458&idx=7&sn=32a61a859ef8ba78f3ac5147f2de6c5a&chksm=cf68ed1cf81f640ad0528d0f38053f0a6000f13590d599368c6a0bbe7fcfcebd80fa11a18f53&scene=27
\Example{
(2008年河北预赛)设定义在$[0,2]$上的函数$f(x)$满足下列条件:

\ding{172}对于$x\in [0,2]$,总有$f(2-x)=f(x)$,且$f(x)\geqslant 1$, $f(1)=3$;

\ding{173}对于$x,y\in [1,2]$,若$x+y\geqslant 3$,则$f(x)+f(y)\leqslant f(x+y-2)+1$.

证明: (1) $f\left(\frac{1}{3^n}\right)\leqslant \frac{2}{3^n}+1\ (n\in \mathbf{N}^\ast)$;

(2)当$x\in[1,2]$时, $1\leqslant f(x)\leqslant 13-6x$.
}{
证明:由$f(2-x)=f(x)$知,函数$f(x)$图象关于直线$x=1$对称,则根据\ding{173}可知:对于$x,y\in[0,1]$,若$x+y\leqslant 1$,则$f(x+y)\geqslant f(x)+f(y)-1$.

设$x_1,x_2\in [0,1]$,且$x_1<x_2$,则$x_2-x_1\in [0,1]$.

因为$f(x_{2})-f(x_{1})=f[x_{1}+(x_{2}-x_{1})]-f(x_{1})\geqslant f(x_{1})+f(x_{2}-x_{1})-1-f(x_{1})=f(x_{2}-x_{1})-1\geqslant 0$.

所以$f(x)$在$[0,1]$上是不减函数.

(1) 由于$f\left( \frac{1}{3^{n-1}} \right) =f\left( \frac{1}{3^n}+\frac{1}{3^n}+\frac{1}{3^n} \right) \geqslant f\left( \frac{1}{3^n}+\frac{1}{3^n} \right) +f\left( \frac{1}{3^n} \right) -1\geqslant 3f\left( \frac{1}{3^n} \right) -2$,所以
\begin{align*}
f\left( \frac{1}{3^n} \right) &\leqslant \frac{1}{3}f\left( \frac{1}{3^{n-1}} \right) +\frac{2}{3}\leq \frac{1}{3^2}f\left( \frac{1}{3^{n-2}} \right) +\frac{2}{3^2}+\frac{2}{3}\\
&\leqslant \cdots\leqslant \frac{1}{3^n}f\left( \frac{1}{3^{n-n}} \right) +\frac{2}{3^n}+\cdots+\frac{2}{3}\\
&=\frac{1}{3^{n-1}}+1-\frac{1}{3^n}=\frac{2}{3^n}+1.
\end{align*}

(2)对于任意$x\in (0,1]$,则必存在正整数$n$,使得$\frac{1}{3^n}\leqslant x\leqslant\frac{1}{3^{n-1}}$.

因为$f(x)$在$(0,1)$上是不减函数,所以$f\left( \frac{1}{3^n} \right) \leqslant f\left( x \right) \leqslant f\left( \frac{1}{3^{n-1}} \right)$,

由(1)知$f\left( \frac{1}{3^{n-1}} \right) \leqslant \frac{2}{3^{n-1}}+1=6\frac{1}{3^n}+1\leqslant 6x+1$.由\ding{172}可得$f(2)\geqslant 1$,在\ding{173}中,令$x=y=2$,得$f(2)\leqslant 1$,故 $f(2)=1$.

而$f(2)=f(0)$,所以$f(0)=1$,又$f\left( \frac{1}{3^n} \right) \geqslant f\left( 0 \right)$,则$f\left( \frac{1}{3^n} \right) \geqslant 1$,

所以$x\in[0,1]$时, $1\leqslant f(x)\leqslant 6x+1$.

因为$x\in[1,2]$时, $2-x\in[0,1]$,且$f(x)=f(2-x)$,
所以$1\leqslant f(2-x)\leqslant 6(2-x)+1=13-6x$,

因此, $x\in[1,2]$时, $1\leqslant f(x)\leqslant 13-6x$.
}

上海高中数学竞赛体系

教学内容

六年级(含寒暑假)

有理数、整式的加减乘除，不等式，三角形角度计算，集合，绝对值，方程，分式与根式，因式分解，一元二次方程，全等三角形，二次方程和高次方程，梯形，平行四边形，一次函数，二次函数，直线型，相似三角形，圆，圆幂定理等内容。在正常教学上进行拔高，难度停留在高中联赛二试的水平。

初一(含寒暑假)

几何变换，三角形五心，平面几何著名定理，几何不等式，二次函数综合，正弦余弦，代数式，数论，组合，函数定义与性质，指示函数，对数函数，求和符号，递推数列，数学归纳法，均值不等式，柯西不等式，不等式的证明方法，平面几何综合，解析几何初步，直线和圆的方程，向量和复数，圆锥曲线，极限和导数，立体几何，空间向量等内容。在正常教学上进行拔高，难度停留在高中联赛二试的水平。

初二(含寒暑假)

集合，含绝对值不等式，一元二次不等式，函数与二次函数，幂函数与对数函数，二次函数，函数的最大最小值，等差数列，等比数列，递推数列，向量的加减法，向量的数量积，三角函数的性质以及应用，三角函数求值，三角不等式，正弦定理，余弦定理，构造函数解题，离散量的最大最小值，集合的划分，不等式(针对联赛二试)，平面解析几何，立体几何，向量，排列和组合计数，二项式定理，古典概型，数形结合等内容。在正常教学上进行拔高，难度停留在高中联赛二试水平。

增开思维提升课程，内容分别是:探索法、枚举法、反证、证明方法综合、构造、化归、整除、同余、抽屉原理、数学归纳法、数学竞赛常用方法总结、组合计数、组合恒等式、存在性问题、染色问题和操作问题、组合综合、唯一分解定理、费尔马小定理和阶、不定方程、高斯函数等。

初三(含寒暑假)

针对联赛二试的训练;大学知识点包括数学分析:包括微积分、极限、连续性、导数、积分、级数等内容;线性代数:包括向量空间、矩阵、线性变换、特征值和特征向量等内容;概率论与数理统计:包括概率基本概念、随机变量、概率分布、参数估计、
假设检验等内容;

高等代数:包括群、环、域、向量空间等内容;集合与拓扑学:包括几何图形的性质、拓扑空间的性质、连续映射等内容;微积方程:包括常微分方程和偏微分方程的基本理论和解法等内容。

高中一至三年级:

针对联赛一试、二试代数、数论、几何、组合强化训练。

\begin{zljTheo}{奔驰定理}{benza}
点$O$是$\triangle ABC$内一点,记$\triangle OBC$的面积为$S_A$,$\triangle AOC$的面积为$S_B$,$\triangle ABO$的面积为$S_C$,则
\[S_A\vv{OA}+S_B\vv{OB}+S_C\vv{OC}=\vv{0}\]
\begin{flushleft}
\begin{tikzpicture}
\tkzDefPoints{0/0/O,-2/-1/A,1/-1/B,0/2/C}

\tkzDrawPolygon[cyan,thick](A,B,C)
\tkzDrawSegments[cyan,thick,-stealth](O,A O,B O,C)

\tkzLabelPoints[below](O,A,B)
\tkzLabelPoints[above](C)
\end{tikzpicture}
\end{flushleft}
\end{zljTheo}
{
\begin{minipage}[t]{0.68\linewidth}
记$OB\cap AC=D$,$OC\cap AB=E$,只需证
\[\vv{OA}=-\dfrac{S_B}{S_A}\vv{OB}-\dfrac{S_C}{S_A}\vv{OC}=-\dfrac{AE}{EB}\vv{OB}-\dfrac{AD}{DC}\vv{OC}\]
过$A$作$OC$的平行线交直线$OB$于$F$,则
\[\dfrac{AE}{EB}=\dfrac{FO}{OB}\]
则
\[-\dfrac{AE}{EB}\vv{OB}=-\dfrac{FO}{OB}\vv{OB}=\vv{OF}\]
过$A$作$OB$的平行线交直线$OC$于$G$,同理可知
\[-\dfrac{AD}{DC}\vv{OC}=\vv{OF}\]
故只需证明
\[\vv{OA}=\vv{OF}+\vv{OG}\]
这由$\pxsbx OFAG$可知成立,故原命题得证
\end{minipage}
\begin{minipage}[t]{0.28\linewidth}
\vspace{-\baselineskip}
\hspace*{6pt}
\begin{flushleft}
\begin{tikzpicture}
\tkzDefPoints{0/0/O,-2/-1/A,1/-1/B,0/2/C}
\tkzInterLL(O,B)(A,C)\tkzGetPoint{D}
\tkzInterLL(O,C)(A,B)\tkzGetPoint{E}
\tkzDefLine[parallel=through A](O,C)\tkzGetPoint{A_1}
\tkzInterLL(A,A_1)(O,B)\tkzGetPoint{F}
\tkzDefLine[parallel=through A](O,B)\tkzGetPoint{A_2}
\tkzInterLL(A,A_2)(O,C)\tkzGetPoint{G}

\tkzDrawPolygon[cyan,thick](A,B,C)
\tkzDrawSegments[cyan,thick,-stealth](O,A O,B O,C)
\tkzDrawSegments[red,thick](O,D O,E A,F D,F E,G A,G)

\tkzLabelPoints[below](A,B)
\tkzLabelPoints[above](C)
\tkzLabelPoints[right](O)
\tkzLabelPoints[red,below](G)
\tkzLabelPoints[red,below right](E)
\tkzLabelPoints[red,above](D,F)
\end{tikzpicture}
\end{flushleft}
\end{minipage}
}
%
\begin{zljDef}{有向面积}{yxmj}
对于平面上三个点$A,B,C$,固定视角,如果$A,B,C$三个字母逆时针排列,则规定$S_{\triangle ABC}$是正数,如果$A,B,C$三个字母逆时针排列,则规定$S_{\triangle ABC}$是负数,如果$A,B,C$共线,则规定$S_{\triangle ABC}$是零,称为有向面积
\end{zljDef}
%
\begin{zljTheo}{奔驰定理推广}{benzb}
定理\ref{zljTheo:benza}中,若$O$是平面$ABC$内任意一点,$S_A,S_B,S_C$改为有向面积,则该定理也成立
\end{zljTheo}
{
如图,对于$O$在$\triangle ABC$外点情况,分区域先指明各有向面积符号
\begin{flushleft}
\begin{tblr}{hlines,vlines,colspec={Q[c]Q[c]Q[c]Q[c]}}
区域 & $S_{\triangle OBC}$符号 & $S_{\triangle AOC}$符号 & $S_{\triangle ABO}$符号 \\
$\triangle ABC$内 & $+$ & $+$ & $+$ \\
区域\uppercase\expandafter{\romannumeral1} & $+$ & $-$ & $-$ \\
区域\uppercase\expandafter{\romannumeral2} & $-$ & $+$ & $-$ \\
区域\uppercase\expandafter{\romannumeral3} & $-$ & $-$ & $+$ \\
区域\uppercase\expandafter{\romannumeral4} & $-$ & $+$ & $+$\\
区域\uppercase\expandafter{\romannumeral5} & $+$ & $-$ & $+$ \\
区域\uppercase\expandafter{\romannumeral6} & $+$ & $+$ & $-$ \\
线段$BC$上 & $0$ & $+$ & $+$ \\
线段$CA$上 & $+$ & $0$ & $+$ \\
线段$AB$上 & $+$ & $+$ & $0$ \\
$BC$延长线上 & $0$ & $-$ & $+$ \\
$CB$延长线上 & $0$ & $+$ & $-$ \\
$CA$延长线上 & $+$ & $0$ & $-$ \\
$AC$延长线上 & $-$ & $0$ & $+$ \\
$AB$延长线上 & $-$ & $+$ & $0$ \\
$BA$延长线上 & $+$ & $-$ & $0$ \\
$A$ & $+$ & $0$ & $0$ \\
$B$ & $0$ & $+$ & $0$ \\
$C$ & $0$ & $0$ & $+$ \\
\end{tblr}
\end{flushleft}
除了按照顺逆时针记法,还可以这么记忆,对于$S_{\triangle OBC}$,若$A$与$O$在直线$BC$同侧,则其为正,异侧为负,正负之间为零,以此类推,事实上,这种记忆方式更轻松.下面证明区域\uppercase\expandafter{\romannumeral1}内点$O$的情况.
\begin{flushleft}
\begin{tikzpicture}
\tkzDefPoints{0/0/O,-2/-1/A,1/-1/B,0/2/C}
\coordinate (D) at ($(O)!1.3!(A)$);
\coordinate (E) at ($(O)!1.4!(B)$);
\coordinate (F) at ($(O)!1.4!(C)$);
\coordinate (G) at ($(A)!1.8!(O)$);
\coordinate (H) at ($(B)!2.5!(O)$);
\coordinate (I) at ($(C)!2!(O)$);
\tkzDrawLines[cyan,thick,add=.3 and .3](A,B B,C C,A)
%\tkzDrawSegments[cyan,thick,-stealth](O,A O,B O,C)

\tkzLabelPoints[below](A)
\tkzLabelPoints[below left](B)
\tkzLabelPoints[right](C)
\node at (D){\color{red}\uppercase\expandafter{\romannumeral1}};
\node at (E){\color{red}\uppercase\expandafter{\romannumeral2}};
\node at (F){\color{red}\uppercase\expandafter{\romannumeral3}};
\node at (G){\color{red}\uppercase\expandafter{\romannumeral4}};
\node at (H){\color{red}\uppercase\expandafter{\romannumeral5}};
\node at (I){\color{red}\uppercase\expandafter{\romannumeral6}};
\end{tikzpicture}
\end{flushleft}
用红色字体表示正的面积,蓝色字体表示负的面积,为了习惯,我们都加上绝对值取成正面积,对于区域\uppercase\expandafter{\romannumeral1}内的点$O$,即证明
\[|{\color{red}S_A}|\vv{OA}-|{\color{blue}S_B}|\vv{OB}-|{\color{blue}S_C}|\vv{OC}=\vv{0}\]
即证
\[\vv{OA}=\dfrac{|{\color{blue}S_B}|}{|{\color{red}S_A}|}\vv{OB}+\dfrac{|{\color{blue}S_C}|}{|{\color{red}S_A}|}\vv{OC}\]
记$AC\cap OB=D$,记$AB\cap OC=E$
\[\dfrac{|{\color{blue}S_B}|}{|{\color{red}S_A}|}=\dfrac{EA}{EB}\]
过$A$作$OB$平行线交$OC$于$G$,过$A$作$OC$平行线交$OB$于$F$
\[\dfrac{EA}{EB}=\dfrac{GA}{OB}=\dfrac{OF}{OB}\]
所以
\[\dfrac{|{\color{blue}S_B}|}{|{\color{red}S_A}|}\vv{OB}=\dfrac{OF}{OB}\vv{OB}=\vv{OF}\]
同理
\[\dfrac{|{\color{blue}S_B}|}{|{\color{red}S_A}|}\vv{OC}=\vv{OG}\]
再由$\pxsbx OFAG$可知结论成立,再把绝对值取掉即
\[{\color{red}S_A}\vv{OB}+{\color{blue}S_B}\vv{OB}+{\color{blue}S_C}\vv{OC}=\vv{0}\]
\begin{flushleft}
\begin{tikzpicture}
\tkzDefPoints{-5/-3/O,-2/-1/A,1/-1/B,0/2/C}
\tkzInterLL(O,B)(A,C)\tkzGetPoint{D}
\tkzInterLL(O,C)(A,B)\tkzGetPoint{E}
\tkzDefLine[parallel=through A](O,C)\tkzGetPoint{A_1}
\tkzInterLL(A,A_1)(O,B)\tkzGetPoint{F}
\tkzDefLine[parallel=through A](O,B)\tkzGetPoint{A_2}
\tkzInterLL(A,A_2)(O,C)\tkzGetPoint{G}

\tkzDrawPolygon[cyan,thick](A,B,C)
\tkzDrawSegments[cyan,thick,-stealth](O,A O,B O,C)
\tkzDrawSegments[red,thick](A,D A,E A,F D,F E,G A,G)

\tkzLabelPoints[below](A,B)
\tkzLabelPoints[above](C)
\tkzLabelPoints[right](O)
\tkzLabelPoints[red,left](G)
\tkzLabelPoints[red,above left](E)
\tkzLabelPoints[red,below](D,F)
\end{tikzpicture}
\end{flushleft}
对于$O$点在其他区域的情况,可以仿照上面的过程完成,此处不再赘述.
}
\begin{zljTheo}{奔驰定理}{benzc}
$O$是$\triangle ABC$平面内任意一点,则
\[\vv{AO}=\dfrac{S_B\vv{OB}+S_C\vv{OC}}{S_A+S_B+S_C}\]
\end{zljTheo}
{
由前面定理可知
\[S_A\vv{OA}+S_B\vv{OB}+S_C\vv{OC}=\vv{0}\]
将其改写为
\[S_A(-\vv{AO})+S_B(\vv{AB}-\vv{AO})+S_C(\vv{AC}-\vv{AO})=\vv{0}\]
整理得
\[\vv{AO}=\dfrac{S_B\vv{OB}+S_C\vv{OC}}{S_A+S_B+S_C}\]
}
\section{三角形重心的向量表达}
\begin{zljLem}{重心分面积三等分}{zx}
若$G$是$\triangle ABC$的重心,则
\[S_A:S_B:S_C=1:1:1\]
\end{zljLem}
{
由三角形重心是三条中线交点易知
}
\begin{zljTheo}{重心的向量表示}{}
若$G$是$\triangle ABC$的重心,则
\begin{gather*}
\vv{GA}+\vv{GB}+\vv{GC}=\vv{0}\\
\vv{AG}=\dfrac{\vv{AB}+\vv{AC}}{3}
\end{gather*}
\end{zljTheo}
{
由定理\ref{zljTheo:benzb}定理\ref{zljTheo:benzc}以及引理\ref{zljLem:zx}易得
}
\section{三角形内心的向量表达}
\begin{zljLem}{内心分面积之三边比}{nx}
若$I$是$\triangle ABC$的内心,则
\[S_A:S_B:S_C=a:b:c=\sin A:\sin B:\sin C\]
\end{zljLem}
{
由三角心内心到三边距离相等以及正弦定理易知
}
\begin{zljTheo}{内心的向量表示}{}
若$I$是$\triangle ABC$的内心,则
\begin{gather*}
a\vv{IA}+b\vv{IB}+c\vv{IC}=\vv{0}\\
\vv{IA}\sin A+\vv{IB}\sin B+\vv{IC}\sin C=\vv{0}\\
\vv{AI}=\dfrac{b\vv{AB}+c\vv{AC}}{a+b+c}\\
\vv{AI}=\dfrac{\vv{AB}\sin B+\vv{AC}\sin C}{\sin A+\sin B+\sin C}
\end{gather*}
\end{zljTheo}
{
由定理\ref{zljTheo:benzb}定理\ref{zljTheo:benzc}以及引理\ref{zljLem:nx}易得
}
\section{三角心外心的向量表达}
\begin{zljLem}{外心分面积之比}{wx}
若$O$是$\triangle ABC$的外心,则
\[S_A:S_B:S_C=\sin2A:\sin2B:\sin2C\]
\end{zljLem}
{
\[S_A=\dfrac{1}{2}|OB|\cdot|OC|\sin 2A=\dfrac{1}{2}R^2\sin 2A\]
其中$R$为$\triangle ABC$外接圆半径,注意此处$S_A$是有向面积,当$A$为钝角时,其为负,$S_B,S_C$同理,则引理成立
}
\begin{zljTheo}{外心的向量表示}{}
若$O$是$\triangle ABC$的外心,则
\begin{gather*}
\vv{OA}\sin 2A+\vv{OB}\sin 2B+\vv{OC}\sin 2C=\vv{0}\\
\vv{AO}=\dfrac{\vv{AB}\sin 2B+\vv{AC}\sin 2C}{\sin 2A+\sin 2B+\sin 2C}\\
2\vv{AO}\sin A=\dfrac{\cos B}{\sin C}\vv{AB}+\dfrac{\cos C}{\sin B}\vv{AC}
\end{gather*}
\end{zljTheo}
{
前面两个等式由定理\ref{zljTheo:benzb}定理\ref{zljTheo:benzc}以及引理\ref{zljLem:wx}易得,第三个等式由
\[\sin 2A+\sin 2B+\sin 2C=4\sin A\sin B\sin C\]
以及二倍角的正弦公式可得
}
\section{三角形垂心的向量表达}
\begin{zljLem}{垂心分面积之比}{cx}
若$H$是$\triangle ABC$(非直角三角形)的垂心,则
\[S_A:S_B:S_C=\tan A:\tan B:\tan C\]
\end{zljLem}
{
\[S_A=\dfrac{1}{2}|HB|\cdot|HC|\cos\angle BHC=\dfrac{1}{2}\vv{HB}\cdot\vv{HC}\tan\angle BHC=-\dfrac{1}{2}\vv{HB}\cdot\vv{HC}\tan A\]
由垂心性质可知
\[\vv{HB}\cdot\vv{HC}=\vv{HC}\cdot\vv{HA}=\vv{HA}\cdot\vv{HB}\]
可知引理成立,同样注意此处有向面积$S_A,S_B,S_C$可能是负数
}
\begin{zljTheo}{垂心的向量表示}{}
若$H$是$\triangle ABC$(非直角三角形)的垂心,则
\begin{gather*}
\vv{HA}\tan A+\vv{HB}\tan B+\vv{HC}\tan C=\vv{0}\\
\vv{AH}=\dfrac{\vv{AB}\tan B+\vv{AC}\tan C}{\tan A+\tan B+\tan C}\\
\vv{AH}\tan A=\dfrac{\vv{AB}}{\tan C}+\dfrac{\vv{AC}}{\tan B}
\end{gather*}
\end{zljTheo}
{
前面两个等式由定理\ref{zljTheo:benzb}定理\ref{zljTheo:benzc}以及引理\ref{zljLem:cx}易得,第三个等式由
\[\tan A+\tan B+\tan C=\tan A\tan B\tan C\]
可得
}
\end{document}

首发于
MO杂货铺

写文章
点击打开undefined的主页
母函数(一)
母函数(一)
林花谢春红
林花谢春红
关注他
母函数在代数, 数论, 组合中都有极其广泛的应用, 本文略微介绍一二, 愿于读者有益.

本文主要介绍母函数在求数列通项时的应用.

母函数依托于数列, 我们可以将母函数理解为数列的"Mother", 或者另外一种定义数列的方式.

\fbox{定义1.1} 对于无穷数列 \{a_n\}_{n=0}^{\infty} , 我们称f(x)=\sum^{\infty}_{n=0}a_nx^n\\ 为 \{a_n\}_{n=0}^{\infty} 的一般形式幂级数.

事实上, 这里只是一种母函数, 而对于母函数, 还有两种常见的定义, 见下面:

\fbox{定义1.2} 对于无穷数列 \{a_n\}_{n=0}^{\infty} , 我们称 f(x)=\sum^{\infty}_{n=0}\frac{a_n}{n!}x^n\\ 为\{a_n\}_{n=0}^{\infty} 的指数型幂级数.

\fbox{定义1.3} 对于无穷数列 \{a_n\}_{n=0}^{\infty} , 我们称 f(x)=\sum^{\infty}_{s=0}\frac{a_n}{n^s}\\ 为\{a_n\}_{n=0}^{\infty} 的狄利克雷型幂级数.

一般地, 我们说母函数, 不加特别说明, 都是指第一类母函数, 它们最常见, 也最常用.

下面, 我们来看一看第一类母函数(下面不加特别说明, 母函数都是指第一类母函数)的一些运算性质.

\fbox{性质1.4} 这描述了母函数的加法性质: \sum_na_nx^n\pm\sum_nb_nx^n=\sum_n(a_n\pm b_n)x^n\\ \fbox{性质1.5} 这描述了母函数的乘法性质: \sum_na_nx^n\sum_nb_nx^n=\sum_nc_nx^n, c_n=\sum_ka_kb_{n-k}\\ \fbox{性质1.6} 这描述了两个母函数的复合: f(x)=\sum_na_nx^n,g(x)=\sum_nb_nx^n , 那么: f(g(x))=\sum_na_ng(x)^n\\ \fbox{性质1.7} 这描述了母函数求导的法则:对于 f(x)=\sum_na_nx^n , 我们有: f'(x)=\sum_nna_nx^{n-1}\\ 至于高阶导数同理.

下面, 基于这些算术性质, 我们来看一看母函数在求数列通项时的应用.

首先, 我们应该思考, 对于最基础的数列, 我们怎么刻画它的母函数.

\fbox{例1.8} 常数列 \{a_n=c\} , 它的母函数为f(x)=\sum_ncx^n\\ 而这种无穷幂级数的形式不便于我们研究, 我们希望可以把这种形式化简一下, 得到一个更简洁的形式, 以蕴含这个数列, 于是我们可以想到, 当 |x|<1 , 可以用等比数列求和并把分子化简. \begin{align}\sum_ncx^n&=c\sum_nx^n\\&=c\lim_{n\rightarrow\infty}\frac{1-x^{n+1}}{1-x}=\frac{c}{1-x}\end{align}\\ 于是, 我们将一个常数列包装在了一个简单的函数里: \displaystyle\frac{c}{1-x} .

\fbox{例1.9} 等差数列 \{a_n=a_0+nd\} , 它的母函数为 f(x)=\sum_n(a_0+nd)x^n\\我们仿照之前的做法, 依然先对其进行简单的有限项的求和, 然后对|x|<1且 n\rightarrow\infty 时取极限即可. 具体计算留给读者.

但如果我们的数列更复杂一些, 按照这样的方法, 似乎几乎不可能得到一个简洁的结果, 所以我们选择从更本源的角度看问题. 从递推的角度看数列的通项.

为了行文方便, 我们规定一个记号:

\fbox{定义1.10} 符号 f\stackrel{\text{ops}}{\leftrightarrow}\{a_n\}_0^{\infty} 表示 f(x)=\sum_na_nx^n .

于是 \{a_{n+1}\}_0^{\infty}\stackrel{\text{ops}}{\leftrightarrow}\sum_na_{n+1}x^n=(f(x)-a_0)/x 等等.

那么, 我们怎么看等差数列的递推呢?

对于一个等差数列, 我们有 a_{n+1}=a_n+d 以及 a_0=a . 那么这个数列的母函数就满足递推\frac{f-a}{x}=f+\frac{d}{1-x}\\ 于是我们只需要解出这个母函数的解析表达式, 然后对其进行泰勒展开即可.

这个递推的得到似乎很无端, 那我们来具体看看如何得到这样的递推. 事实上, 这样的递推关键在于幂级数的每一项都相等代表两个幂级数相等. \begin{align}\sum_na_nx^n&=a_0+\sum_{n=1}a_nx^n\\&=a_0+\sum_{n=0}a_{n+1}x^{n+1}\\&=a_0+\sum_{n=0}(a_n+d)x^{n+1}\\&=a_0+x\Bigg(\sum_na_nx^n+\frac{d}{1-x}\Bigg)\end{align}\\ 于是我们将 \sum_na_nx^n 解出来, 就得到我们想要的结果了.

对于简单的等差数列我们可以用这种方式来进行翻译, 对于稍微复杂一些的递推, 我们当然也可以采用这种办法. 下面举几个例子具体看看.

\fbox{例1.11} 数列 \{a_n\} 满足递推 a_{n+1}=pa_n+q , 求 \{a_n\} 的通项.

我们考虑这个数列的母函数 \begin{align}\sum_na_nx^n&=a_0+\sum_{n=1}a_nx^n\\&=a_0+\sum_na_{n+1}x^{n+1}\\&=a_0+\sum_n(pa_n+q)x^{n+1}\\&=a_0+x\Bigg(\sum_n(pa_n+q)x^n\Bigg)\\&=a_0+x\Bigg(p\sum_na_nx^n+\frac{q}{1-x}\Bigg)\end{align}\\ 下面解出 \sum_na_nx^n 即可, 然后采用泰勒展开, 就可以得到 a_n 具体的值了.

以上我们讨论的都是一阶的线性递推问题, 但是在实际的问题中, 我们会遇到更加复杂的高阶线性递推, 对于这种问题, 我们又该怎样处理呢? 请看下面的例子.

\fbox{例1.12} 数列 \{a_n\} 满足线性递推 a_{n+1}=\alpha a_n+\beta a_{n-1} , 求 \{a_n\} 的母函数.

还是考虑这个序列的母函数 \begin{align} \sum_na_nx^n&=a_0+a_1x+\sum_{n=2}a_nx^n\\ &=a_0+a_1x+\sum_na_{n+2}x^{n+2}\\ &=a_0+a_1x+\sum_n(\alpha a_{n+1}+\beta a_n)x^{n+2}\\ &=a_0+a_1x+\alpha x\Bigg(\sum_na_nx^n-a_0\Bigg)+\beta x^2\Bigg(\sum_na_nx^n\Bigg) \end{align}\\ 根据这个递推解出 \sum_na_nx^n 即可.

至于更高阶的线性递推, 我们同样可以解得它的母函数, 不过至于母函数的泰勒展开究竟怎么进行, 这是一个相对复杂的问题, 一般情况下是远远困难于求母函数本身, 上面两个例子中求得母函数之后, 泰勒展开是轻松的, 我们不赘述, 下面来看几个求得母函数之后需要一些有技巧的代数变形的例子.

\fbox{例1.13} 数列 \{a_n\} 满足非线性递推: a_0=1 , 以及a_{n+1}=\sum_{i+j=n,0\leq i,j\leq n}a_ia_j\\ 求数列 a_{n} 的通项.

这个问题看上去十分复杂, 首先它的递推就比我们之前看到的问题要复杂得多, 我们首先看怎么去描述它的母函数.这里不要被题面的要求吓到, 我们还是按照之前的思路: \begin{align} \sum_na_nx^n&=a_0+\sum_{n=1}a_nx^n\\ &=a_0+x\Bigg(\sum_{n=1}\sum_{i+j=n-1}a_ia_jx^{n-1}\Bigg)\\ &=a_0+x\Bigg(\sum_{n=1}\sum_{i+j=n-1}a_ix^ia_jx^j\Bigg)\\ &=a_0+x\Bigg(\sum_na_nx^n\Bigg)^2=1+x\Bigg(\sum_na_nx^n\Bigg)^2 \end{align}\\ 然后解这个关于 f(x)=\sum_na_nx^n 的方程, 我们不难发现: f(x)=\frac{1\pm\sqrt{1-4x}}{2x}\\ 由于这里的符号未定, 我们需要确定一下符号, 不难发现, 若我们取 +,\lim_{x\rightarrow0}f(x)=2 , 而我们知道, f(0)=a_0=1 , 这是矛盾的, 所以我们取 - 号. f(x)=\frac{1-\sqrt{1-4x}}{2x}\\ 下面, 关键的难题在于我们怎么通过这个看似无从下手的母函数得到我们想要的数列通项.

这里, 关键的一步应该是想到下面一个牛顿著名的恒等式, 广义二项式定理. (1+x)^\alpha=\sum_n\binom{\alpha}{n}x^n\\ 在这里, 取 \alpha=1/2 , 我们有: \begin{align} \frac{1-\sqrt{1-4x}}{2x}&=\frac{1}{2x}\sum_{n=1}\frac{(-1)^n(2n-3)!!}{2^nn!}(-4x)^n\\ &=\frac{1}{2x}\sum_{n=1}\frac{(-1)^n}{2^nn!}\frac{(2n-2)!}{(2n-2)!!}(-4x)^n\\ &=\sum_{n=1}\frac{1}{n}\binom{2n-2}{n-1}x^{n-1}\\ &=\sum_{n}\frac{1}{n+1}\binom{2n}{n}x^n \end{align}\\ 于是, 我们就得到了 a_n=\frac{1}{n+1}\binom{2n}{n} .

这里的思维过程比较长, 而且涉及的代数变形也相当有难度. 而这里得到的结果也相当有渊源, 这里的 a_n 被称为卡特兰数, 它也有一些组合的推导, 这里不赘述.

下面我们来看一个很有难度的问题, 选自2022年北京大学金秋营, 我们借这个问题来引入一个极其有用的高等的工具.

\fbox{例1.13} 数列 \{a_n\} 满足 a_0=1 , 以及递推 a_{n+1}=\sum_{0\le i,j,k\le n, i+j+k=n}a_ia_ja_k \\ 求 \{a_n\} 的通项.

这里, 我们首先还是先尝试之前的办法, 不难得到其满足方程: \frac{f-1}{x}=f^3\\ 我们发现这是一个三次方程, 下面怎么处理这个三次方程, 就会导致不同的复杂度. 像我当时就选择了直接解出这个三次方程, 然后采用泰勒展开, 尝试解出通项. 不过这里的代数变形过于复杂, 远不是我可以搞定的, 于是就寄了......

至于更加靠谱的办法, 则是采用拉格朗日反演[1]这一工具. 下面, 我们介绍一下拉格朗日反演的具体内容. 这里提供两个证明, 都用到了一些复分析的内容, 请读者根据自身情况选择性阅读. 这里的证明不影响后续的阅读. 其中 \text{res}(\cdot) 表示 \cdot 的留数.

首先, 我们用到一个多项式的基本反演.

\fbox{定理1.14} K 是一个域, 母函数 f(x)=a_1x+a_2x^2+...\in K[x] , 其中 a_1\not =0 , 那么存在唯一的 f\in K[x] 使得 F(f(x))=f(F(x))=x .

设 f(x)=b_1x+b_2x^2+... , 我们考虑 F(f(x))=x , 对边两边的系数, 有 b_1=\frac{1}{a_1} , 以及 a_1b_n+G_n(a_1,b_1,...,a_{n-1},b_{n-1})=0, G_n\in K[x]\\ 我们可以解得相应的 b_n , 于是满足条件的 f(x) 存在.

另一方面, \exists g\in K[x] 使 f(g(x))=x . 那么 F(x)=F(f(g(x)))=g(x)\Rightarrow F(x)=g(x)\\ 证毕!

\fbox{定理1.15} K 为一个满足 \chi(K)=0 的域, 设形式幂级数 e\in K[x] , e(0)\not =0 . 若 f\in K[x] 使 f(x)=xe(f(x)) , 则 \forall g\in K[x],n>0 , 有 [x^n]g(f(x))=\frac{1}{n}[x^{n-1}](g'(x)e(x)^n)\\ 设 F(x)=\frac{x}{e(x)} , 则有 F(0)=0 , 故 \begin{align} f(x)=xe(f(x))&\Leftrightarrow f(x)=x\frac{f(x)}{F(f(x))}\\ &\Leftrightarrow F(f(x))=x \end{align}\\ 对于一个洛朗级数 h(x)=\sum_{n\in \mathbb{Z}}a_nx^n\in K[x][1/x] , 设 \text{res}(h\text{d}x)=a_{-1} , 则有 \text{res}(h'\text{d}x)=0 . 下面考虑一个关键的引理:

\fbox{引理1.16} 若 G\in K[x][1/x] , 那么: \text{res}(G(x)\text{d}x)=\text{res}(G(F(x))F'(x)\text{d}x)\\ 根据线性, 不妨设 G(x)=x^k, k\in \mathbb{Z} .

若 k\not=-1 , 则 \exists g_1, g_2\in K[x][1/x] , 满足 g_1'=G,g_2'=G(F)F'\\ 根据我们之前得到的结果, \text{res}(G(x)\text{d}x)=\text{res}(G(F(x))F'(x)\text{d}x)=0 .

若 k=-1 , \frac{F'(x)}{F(x)}=\frac1 x-\frac{e'(x)}{e(x)}=\frac{1}{x}-\Bigg(\text{ln}\frac{e(x)}{e(0)}\Bigg)'\\ 故 \text{res}\Big(\frac{F'(x)}{F(x)}\text{d}x\Big)=\text{res}\Big(\frac{\text{d}x}{x}\Big) .

回到定理的证明, 由于 (uv)'=uv'+u'v , 于是 \text{res}(u'v)=-\text{res}(uv') , 那么 \begin{align} [x^n]g(F(x))&=\text{res}\Bigg(\frac{g(f(x))}{x^{n+1}}\text{d}x\Bigg)\\ &=\text{res}\Bigg(\frac{g(f(F(x)))}{F(x)^{n+1}}F'(x)\text{d}x\Bigg)\\ &=-\frac{1}{n}\text{res}\Bigg(g(x)\big(F(x)^{-n}\big)'\text{d}x\Bigg)\\ &=\frac{1}{n}\text{res}\Bigg(g'(x)F(x)^{-n}\text{d}x\Bigg)\\ &=\frac{1}{n}\text{res}\Bigg(g'(x)\frac{e(x)^n}{x^n}\text{d}x\Bigg)\\ &=\frac{1}{n}[x^{n-1}]\big(g'(x)e^n(x)\big) \end{align}\\ 这正是我们想要得出的结果! 于是我们证明了拉格朗日反演公式.

根据拉格朗日反演, 这道北大金秋营的压轴题就可以轻易地推出, 我们不采用原来的符号. f(x):=\sum_{n\ge1}a_nx^n,g(x)=(1+x)^3\\ 于是, f(x)=xg\big(f(x)\big) . 根据拉格朗日反演, [x^n]f(x)=\frac{1}n[x^{n-1}]g(x)^n=\frac1 n\binom{3n}{n-1}=\frac{1}{2n+1}\binom{3n}{n}\\ 也就是 a_n=\frac{1}{2n+1}\binom{3n}{n} .

事实上, 我们甚至可以把这个递推变得更加复杂, 相应的母函数满足的方程的次数更高, 甚至可能不可解, 这时拉格朗日反演的强大功能就体现出来了.

下面, 我们再看一个例子, 这个例子要求的结果用一般的方法是极不容易证明的, 但使用拉格朗日反演之后, 几乎没有思维含量.

\fbox{例1.17} 两个数列 \{a_n\},\{b_n\} 满足, 对于 n\ge0 , b_n=\sum_k\binom{k}{n-k}a_k\\ 求证: a_n=\frac{1}{n}\sum_k\binom{2n-k-1}{n-k}(-1)^{n-k}kb_k\\ 设 A(x) 为 \{a_n\} 母函数, B(x) 为 \{b_n\} 的母函数. 经过简单的计算 \begin{align} B(x)&=\sum_nx^n\Bigg(\sum_k\binom{k}{n-k}a_k\Bigg)=\sum_ka_kx^k\sum_n\binom{k}{n-k}x^{n-k}\\ &=\sum_ka_kx^k\sum^k_{n=0}\binom k nx^n=\sum_ka_kx^k(1+x)^k=A(x+x^2) \end{align}\\ 令 y=x^2+x , f(y)=x,f(y)=\frac{y}{1+f(y)} . 根据拉格朗日反演, \begin{align} a_n&=[y^n]A(y)=[y^n]B(x)=[y^n]B(f(y))\\ &=\frac{1}{n}[y^{n-1}]\big(B'(y)(1+y)^{-n}\big)=\sum_k\frac{kb_k}{n}[y^{n-1}]\big(y^{k-1}(1+y)^{-n}\big)\\ &=\sum_k\frac{kb_k}{n}[y^{n-k}](1+y)^{-n}=\sum_k\frac{kb_k}{n}\binom{-n}{n-k}\\ \end{align}\\ 再根据 \binom{-n}{n-k}=(-1)^{n-k}\binom{2n-k-1}{n-k}\\ 立即可以得到原题要求的结果!

事实上, 拉格朗日反演还有一些有趣的变形, 我们看下面的定理.

\fbox{定理1.18} 设 K 是一个满足 \chi(K)=0 的域, e(x)\in K[x] , 满足 e(0)\not=0 , 那么 \forall f\in K[x] , 有 f(x)=f(0)+\sum_{n\ge1}\Bigg(\frac{x}{e(x)}\Bigg)^n\cdot\frac{1}{n}[x^{n-1}]\big(f'(x)e(x)^n\big)\\ 设 F=F(x) , 满足 F=xe(F) (之前的例子已经论证了它的存在性). 根据拉格朗日反演公式, f(F(x))=f(0)+\sum_{n\ge1}[x^n](f(F(x)))x^n=f(0)+\sum_{n\ge1}\frac{1}n[x^{n-1}](f'(x)e(x)^n)x^n\\ 现在, 只要令 x=y/e(y) 即可!

下面我们看这一定理的一个应用, 用直接的计算法是不容易证明下面的恒等式的.

\fbox{例1.19}(\text{Abel}) a,x,y\in \mathbb{C}, n\in\mathbb{Z^+} , 就有 (x+y)^n=\sum^n_{k=0 }\binom{n}{k}x(x+ak)^{k-1}(y-ak)^{n-k}\\ 要证明的式子等价于 \frac{(x+y)^n}{n!}=\sum^n_{k=0}\frac{x(x+ak)^{k-1}}{k!}\cdot\frac{(y-ak)^{n-k}}{(n-k)!}\\ 我们考虑两边的母函数. 左边的式子的母函数为 e^{(x+y)T} . 而右边的母函数相对复杂, 是 \sum_n\sum_{0\le k\le n}\frac{x(x+ak)^{k-1}}{k!}\cdot\frac{(y-ak)^{n-k}}{(n-k)!}T^n=\sum_kT^k\frac{x(x+ak)^{k-1}}{k!}e^{T(y-ak)}\\ 因此, 两边除掉 e^{yT} , 只要证明 e^{xT}=1+\sum_{k\ge1}\frac{1}{k!}x(x+ak)^{k-1}e^{-akT}T^k\\ 而这正是定理 1.18 的直接推论, 在定理 1.18 中, 令 f(T)=e^{xT} , e(T)=e^{aT} 即可!

再看一个问题, 来自 \text{AMM} .

\fbox{例1.20} 对于 n\ge1 , 求证 \sum_{i,j\ge0,i+j=n}\binom n i(i+1)^{i-1}(j+1)^{j-1}=2(n+2)^{n-1}\\ 在之前的定理里, 我们令 a=1, x=1,y=n+1 , 可以得到 \sum_{i+j=n}\binom{n}{i}(i+1)^{i-1}(j+1)^{j}=(n+2)^n\\ 但是这和我们想要的结果还有一定的偏差, 所以我们的想法是, 把 j+1 的指数往下调. 我们对之前定理对 y 进行差分. 再将 a=1,x=1,y=n+1 代入, 我们可以得到: n(n+2)^{n-1}=\sum_{i+j=n}\binom{n}{i}(i+1)^{i-1}j(j+1)^{j-1}\\ 下面只需要将两式做差即可得到想要的结果了.

参考
^Straight From The Book, Titu Andreescu, Gariel Dospinescu, Addendum 8.A p377-p394
编辑于 2023-06-08 15:31・IP 属地江苏
数学
数学竞赛
赞同 25
2 条评论
分享
喜欢
收藏
申请转载

文章被以下专栏收录
MO杂货铺
MO杂货铺

%https://zhuanlan.zhihu.com/p/553418162

首发于
MO杂货铺

写文章
点击打开undefined的主页
稠密性
稠密性
林花谢春红
林花谢春红
关注他
线性相关与稠密性是数学中很重要的概念, 近几年在数学竞赛中也常常有考察. 关于稠密性的定理与结论很多, 但在各种竞赛书中似乎很少有讨论, 故在这里展示一些常见的结论, 以飨读者.

在下文中, 我们默认读者是了解稠密的定义的.

我们会给出一些用于训练或者理解的题目, 请读者先尝试自行证明, 建议当自己已经完成证明或者没有想到方法时, 再看解答.

\fbox{Theorem 1}(\text{Kronecker}) 给定无理数 \theta 以及 \alpha\in(0,1) ,对于 \forall \varepsilon>0 , \exists n\in\mathbb{Z^+} , 满足 \left| \{n\theta\}-\alpha\right|<\varepsilon\\ 证明是很容易的, 运用抽屉原理再加上一点简单的分析就可以了.

\fbox{Proof} 我们考虑 m=\lceil\frac{1}{\varepsilon}\rceil+1 , 以及 \{\theta\},\{2\theta\},...,\{m\theta\} , 根据抽屉原理, \exists 1\le i<j\le m , 使得 \left|\{i\theta\}-\{j\theta\}\right|\le\varepsilon , 那么 \{|i-j|\theta\}\in(0,\varepsilon)\cup(1-\varepsilon,1) . 进一步的, 考虑 \{|i-j|\theta\},\{2|i-j|\theta\},... ,相邻两项之间的距离小于 \varepsilon (我们可以把这个理解为步长), 故 \exists k , (\{k|i-j|\theta\},\{(k+1)|i-j|\theta\})\ni\alpha , 于是我们取 n=k|i-j| 就可以了!

从这一点出发, 我们可以很显然地推出, 对于无理数 \theta , \{n\theta\}_{n\ge1} 在 (0,1) 上是稠密的.

事实上, \{n\theta\} 的稠密性与 \text{Kronecker} 定理是等价的(读者可以自己证明), 因此我们往往也不区分两者.

为了引入下面的例子, 我们先看一个问题:

\fbox{Problem 1} (2007年西部数学奥林匹克P4)设 O 是 \triangle ABC 内部一个点. 求证: 存在正整数 p,q,r , 使得 \left|p\overrightarrow{OA}+q\overrightarrow{OB}+r\overrightarrow{OC}\right|\le\frac1 {2007}\\ \fbox{Proof} 我们用到一个关键的引理:

\fbox{Lemma} 设 \alpha, \beta\in \mathbb{R^+} , N>\max\{\frac{1}{\alpha},\frac{1}{\beta}\}\in\mathbb{Z} , 则存在 p_1,p_2,q\in\mathbb{Z^+} , 满足 \left|q\alpha-p_1\right|\le\frac{1}{N}, |q\beta-p_2|\le\frac1 N.\\ 考虑 T=\{(\{i\alpha\},\{i\beta\})|i=0,1,2,...,N^2\}.\\ 将正方形 \{(x,y)|0\le x,y<1\} 沿平行于坐标轴分割为 N^2 个相同的小正方形, 则有抽屉原理, T 中必有两个点落在同一个小正方形中, \exists0\le j<i\le N^2 , 使得 |\{i\alpha\}-\{j\alpha\}|<\frac{1}{N}, |\{i\beta\}-\{j\beta\}|<\frac{1}{N}.\\ 令 q=i-j,p_1=[i\alpha]-[j\alpha],p_2=[i\beta]-[j\beta] , 即为所要证明的!

回到原题, 因为 O 是 \triangle ABC 内一点, 所以存在正实数 \alpha, \beta , 使得 \alpha\overrightarrow{OA}+\beta\overrightarrow{OB}+\overrightarrow{OC}=\overrightarrow{0} . 对引理中的 N,p_1,p_2,q , 所以 \begin{align} &\left|p_1\overrightarrow{OA}+p_2\overrightarrow{OB}+q\overrightarrow{OC}\right|\\ =&\left|(p_1-q\alpha)\overrightarrow{OA}+(p_2-q\beta)\overrightarrow{OB}\right|\\ \le&|p_1-q\alpha|\left|\overrightarrow{OA}\right|+|p_2-q\beta|\left|\overrightarrow{OB}\right|\\ <&\frac{1}{N}\Big(\left|\overrightarrow{OA}\right|+\left|\overrightarrow{OB}\right|\Big) \end{align}\\ 取 N 充分大即可!

事实上, 这里我们其实证明了二维 \text{Kronecker} 定理的一个弱形式. 我们其实可以证明, 对于在 \mathbb{Q} 上线性无关的 \{\alpha, \beta, 1\} , 我们有 N=\{(n\alpha, n\beta):n\in\mathbb{Z^+}\} 在 (0,1)\times(0,1) 上是稠密的, 而这正是二维的 \text{Kronecker} 定理.

对于二维的 \text{Kronecker} 定理, 我们有多种证明方式, 不同的证明方式对应了不同的看问题的角度.

首先, 有一种比较几何的角度看问题. 事实上, 有 \{\{i\alpha\}+\{i\alpha\}\}=\{(i+j)\alpha\} , 我们可以把这种性质与向量联系起来. 我们之前证明一维情形的 \text{Kronecker} 定理时, 可以从" 步长" 的角度理解. 事实上, 二维的情形也可以用这种方式理解, 不过我们就要相应地将" 步长" 拓展到二维的情形, 比较自然的想法就是将步长拓展到平行四边形. 首先, 还是用我们在 \text{Problem 1} 中的引理, 事实上, 我们其实可以在小正方形 (1,\frac1 N)\times(1,\frac1 N) 中找到无数个集合 N 中的点, 若存在 i\not=j 使得点 (\alpha,\beta) , (\{i\alpha\},\{i\beta\}) , (\{j\alpha\},\{j\beta\}) 共线, 那么有 \begin{bmatrix} \alpha & \beta &1 \\ \{i\alpha\} & \{i\beta\}&1\\ \{j\alpha\}&\{j\beta\}&1\\ \end{bmatrix}=0\\ 根据线性代数的知识, 我们知道 \text{LHS}=\begin{bmatrix} \alpha & \beta &1 \\ \{i\alpha\} & \{i\beta\}&1\\ \{j\alpha\}&\{j\beta\}&1\\ \end{bmatrix}=\begin{bmatrix} \alpha & \beta &1 \\ i\alpha-[i\alpha] & i\beta-[i\beta]&1\\ j\alpha-[j\alpha]&j\beta-[j\beta]&1\\ \end{bmatrix}=\begin{bmatrix} \alpha & \beta &1 \\ [i\alpha] & [i\beta]&i-1\\ [j\alpha]&[j\beta]&j-1\\ \end{bmatrix}=0\\ 于是我们有 [i\beta](j-1)=[j\beta](i-1) . 事实上, 对于固定的 i , 有无穷多个满足条件的 j , 那么 \beta=\lim_{j\rightarrow\infty}\frac{[j\beta]}{j-1}=\frac{[i\beta]}{i-1}\in\mathbb{Q}\\ 矛盾! 于是我们可以找到两个与 (\alpha, \beta) 不共线的向量, 下面的证明是基本的, 留给读者.

于是我们就得到了 \text{Kronecker} 定理的二维形式, 也就是:

\fbox{Theorem 2} 对于在有理数上线性无关的 \{\alpha, \beta ,1\} , 我们有 (\{n\alpha\},\{n\beta\})_{n\in\mathbb{Z^+}} 在 (0,1)\times(0,1) 上稠密.

事实上, 刚才的证明可以推广到 n 维的情形, 而且并没有本质的区别. 只需要想明白如何用行列式表达 n 维空间中如何表达 n+1 个点共 n-1 维平面并了解一些基本的行列式展开的公式并结合上面的技巧就可以了. 证明留给读者.

咕咕咕...

编辑于 2023-03-11 21:46・IP 属地安徽
数学
赞同 7
添加评论
分享
喜欢
收藏
申请转载

文章被以下专栏收录
MO杂货铺
MO杂货铺

%https://zhuanlan.zhihu.com/p/610565426

写文章
点击打开undefined的主页
2022北大金秋营Day2P4——卡特兰数的推广（Fuss-Catalan Number）
2022北大金秋营Day2P4——卡特兰数的推广（Fuss-Catalan Number）
Acuti Calamum
Acuti Calamum
浮生若梦，为欢几何
关注他
笔者有幸参加了2022年北大的金秋营，Day1炸穿Day2翻盘失败，但Day2考完后觉得猜出答案但并未完成的P4颇为有趣，递推的方式相似于Catalan数，不妨可视为Catalan数的三元推广（事实上这题想到Catalan答案很好猜），且看上去具有推广至 n 元的潜质。

I.原题呈现
（2022北大金秋营Day2P4）数列 \{a_n\} 满足： a_0=1, \\a_{n+1}=\sum\limits_{i+j+k=n}a_ia_ja_k\ ,\ \ \forall \ n\geq 0 \ ,\\ 求 {a_n} 的通项.
求助OEIS本题结果即为A001764，结果是 {a_n}=\dfrac{1}{2n+1} \dbinom{3n}{n} .

II.原题推广
熟知Catalan数 C_n 的递推公式为： C_{n+1}=\sum\limits_{i+j=n}C_iC_j ，则不难对 k 元形式做出以下推广：

（2022北大金秋营Day2P4推广）数列 \{a_n\} 满足： a_0=1,\\a_{k+1}=\sum\limits_{i_1+i_2+\cdots+i_n=k}\ \prod\limits_{j=1}^{n}a_{i_j}\ ,\ \ \forall \ n\geq 0 \ ,\\ 求 {a_n} 的通项.
结合Catalan数通项与原题答案，我们有理由猜测答案为 \dfrac{1}{(k-1)n+1} \dbinom{kn}{n} .

III.推广命题的解法
熟悉Catalan数的同学应该知道OI中对Catalan数的一种组合解释：具有 n 个节点的不同二叉树的总数，根据递推式这是显然的，这个解释可以很好地移植到 k 元版本，即具有 n 个节点的不同 k 叉树的总数 H(n,k) .

考虑一个 kn \times n 的方格表，左下角为 (0,0) ，右上角为 (kn,n) ，每步只能向上走 1 格或向右走 1 格，记左下角走到右下角且路线全程位于 x=ky 下方的走法总数为 S(n,k) .

我们先证明 H(n,k)=S(n,k-1) .

我们知道二叉树的中序遍历序列是按照左子树-根-右子树的顺序构建的，后序遍历是按照左子树-右子树-根的顺序构建的，如果同时得知了这两个序列就可以从后序遍历得到根然后基于中序遍历找到根一劈两半分别递归求解而还原出整个二叉树，事实上我们还可以更聪明一点将两个序列合二为一，不妨称为 N 序列：

定义空二叉树的 N 序列为空，有节点的二叉树的 N 序列构造如下：

[左子树的N序列]-\color{red}根-[右子树的N序列]-\color{blue}根

这样任意一个 N 序列的末尾元素必为根，在序列中找到另一个根的位置将之一劈两半同理递归。

在一个 N 序列中每个元素恰好出现两次，将第一次出现的位染红，第二次出现的位置染蓝，有 n 个红色的元素和 n 个蓝色的元素，之后考虑 n\times n 方格表从左下角开始，从头开始遍历这个序列遇到红色向右一格遇到蓝色向上一格，最后正好走到右上角，显然在操作的任意时刻路径不会跑到 x=y 上面去，因为一个蓝色的元素的前面必然有红色的对应元素，已经经历的元素中蓝色不会比红色多，这就把二叉树与 k=1 的路径对应了起来。

反过来的对应读者自证不难，证明这是一个双射自然证明了 H(n,2)=S(n,1) .

对于一般的 k 考虑 k 叉树版本的 N 序列，形为

[子树1]-\color{red}根-[子树2]-\color{red}根-\cdots-[子树k]-\color{blue}根

的版本即可，于此不再赘述。

接下来计算 S(n,k) 即可，这其实是叫一个 \text{K-Dyke} 路的东西，有一个很神奇的做法，我们不再考虑 kn\times n 的方格表，反过来考虑一个 kn+1\times n 的方格表从左下走到右上且一直保持在对角线以下的方案数，用一个 01 序列表示一条路径， 0 代表向右走， 1 代表向上走，kn+1\times n 有一个很好的性质就是其行数与列数互质，从而行列与走的总步数均互质，从而对角线上没有任何除端点以外的整点，这个性质以后会用到。

接下来可能是比较匪夷所思的一步，我们不考虑单独一条路径，而是把 (k+1)n+1 条路径捆绑在一起处理。对于一个序列 P=v_1v_2 \cdots v_N，定义 P_i=v_{i+1}v_{i+2}\cdots v_nv_1\cdots v_i ， P,P_1,P_2,\cdots,P_{(k+1)n} 是互不相同的（想想为什么，原因和互质有关），而 P_{(k+1)n+1}=P ，于是将这些路径捆绑起来看，发现它们之中不多不少恰有一个是满足条件的！

任取一条不合法的路径，取路径上所有在对角线上方的点离对角线最远的点，这样的点必然唯一，否则存在平行且不重合于对角线的直线上有这个方格表的两个顶点，就又和互质矛盾了，这个点拆出两条路，将这两条路反接得到的路径一定是合法的路径，且一条合法路径任取非端点的一点拆成两条路再反接一定不合法（不再详细写了，画画图计算一下应该就出来了）

最后一步对应便是发现 (k+1)n+1 版本第一步一定是向右走到 (1,0) ，故可看作从 (1,0) 出发到右上角，二者连线，对角线，与方格表边缘围成的图形内部没有整点，所以这个问题与 kn\times n 问题本质相同，于是 \\S(n,k)=\dfrac{1}{((k+1)n+1)}\dbinom{(k+1)n+1}{n}=\dfrac{1}{kn+1}\dbinom{kn}{n}\\ 证毕。

IV.一些有关于本题其他做法的猜想
笔者在考场上未作出的原因可能是代数太烂，这题大部分人看到的第一想法应该都是母函数。设 f(x)=\sum\limits_{n=0}^{+\infty}a_nx^n

则显有 \\ x[f(x)]^3=a_1x^1\ (\sum\limits_{i=0}^{+\infty}a_ix^i)\ (\sum\limits_{j=0}^{+\infty}a_jx^j)\ (\sum\limits_{i=0}^{+\infty}a_kx^k)\ \\= \sum\limits_{n=0}^{+\infty}\sum\limits_{i+j+k+1=n+1}a_ia_ja_ka_1x^{i+j+k+1}\\=\sum\limits_{n=0}^{+\infty}\sum\limits_{i+j+k=n}a_ia_ja_kx^{n+1}\\=\sum\limits_{n=0}^{+\infty}a_{n+1}x^{n+1}=f(x)-1\\ 关于 f(x) 的三次方程，将 f(x) 解出有两个正根，其中一个趋近于 1 另一个比较大，不难判断出 f(x) 的表达式就是那个小根，令 g(x)=\sum\limits_{n=0}^{+\infty}\dfrac{1}{2n+1}\dbinom{3n}{n}x^n ，显 g(x) 也是趋近于 1 的， g(x) 只需带入之后满足这个方程就做完了（但是真的想不到怎么算）。

代数做法其实也容易推广到多元形式 x[f(x)]^k-x+1=0 但是笔者目前没有优秀的代数做法，希望代数功底过硬的同学能联系笔者这个思路能不能行得通。

V.补充
其实本文所讲并非Fuss-Catalan数的全部内容，维基上有它更加一般的推广形式（但好像貌似没给证明），鉴于笔者能力有限（仅仅是个中等省份菜省一），感兴趣的同学可以自己研究，反正我已经是写不动了（逃

编辑于 2022-12-11 20:53・IP 属地江苏
北京大学
组合数学（Combinatorics）
计数
赞同 17
7 条评论
分享
喜欢
收藏
申请转载

%https://zhuanlan.zhihu.com/p/585123569

首发于
MO杂货铺

写文章
点击打开undefined的主页
示性函数与交换求和
示性函数与交换求和
林花谢春红
林花谢春红
关注他
更新note: 第三题的解答其实没有问题, 当时我觉得最后一步比较显然就略过了, 现在补了一下()

本文从2018年的一道CTST开始, 主要讨论了一种" 示性函数" 在解决某些与集合相关的不等式中的应用. 并由此出发讨论了一些交换求和问题.

\fbox{Problem 1} 已知有限集 S , 满足 |S|=n , 非空集合 A_1, … , A_m\subset S , 求证: \sum^m_{k=1}\sum^m_{j=1}|A_k||A_k\cap A_j|\ge \frac 1 {mn}\Bigg(\sum^m_{k=1}|A_k|\Bigg)^3\\

\fbox{Proof} 不妨设 S=\{x_1,x_2,...,x_n\} , 对于 \forall 1\le j\le n , 1\le k \le m , 定义示性函数 f : a_{kj}=\begin{cases} 1 & x_j\in A_k \\ 0 & x_j\notin A_k \end{cases}\\

于是, |A_k|=\sum^n_{k=1}a_{ki} , |A_k\cap A_j|=\sum^n_{i=1}a_{ki}a_{kj} , 下面进行一些代数变形: \begin{equation} \begin{split} LHS &=\sum^m_{k=1}|A_k|\Bigg(\sum^m_{j=1}|A_k\cap A_j|\Bigg)\\ &=\sum^m_{k=1}|A_k|\Bigg(\sum^m_{j=1}\sum^n_{i=1}a_{ki}a_{ji}\Bigg)\\ &=\sum^m_{k=1}\Bigg(\sum^n_{i=1}a_{ki}\Bigg)\Bigg(\sum^m_{j=1}\sum^n_{i=1}a_{ki}a_{ji}\Bigg)\\ &\stackrel{\sum^n_{i=1}a_{ki}=x_k,\sum^m_{i=1}a_{ji}=y_j}{=}\sum^m_{k=1}\sum^n_{j=1}a_{kj}x_ky_j \end{split} \end{equation}\\

这里用到较多交换求和, 但是由于均为单标限定, 所以我们不做过多解释.

\Bigg(\sum^m_{k=1}\sum^n_{j=1}a_{kj}x_ky_j\Bigg)\Bigg(\sum^m_{k=1}\sum^n_{j=1}\frac {a_{kj}}{y_j} \Bigg)\Bigg(\sum^m_{k=1}\sum^n_{j=1}\frac{a_{kj}}{x_k} \Bigg)\\ \begin{equation} \begin{split} \stackrel{\text{Carlson}}{\ge}&\Bigg(\sum^m_{k=1}\sum^n_{j=1}a_{kj}\Bigg)^3\\ =&\Bigg(\sum^m_{k=1}|A_k|\Bigg)^3 \end{split} \end{equation}\\ (*)

再根据:

\begin{align} &\sum^m_{k=1}\sum^n_{j=1}\frac{a_{kj}}{x_k}=\sum^m_{k=1}\frac{1}{x_k}\sum^n_{j=1}a_{kj}=\sum^m_{k=1}\frac{1}{x_k}\cdot x_k=m\\ &\sum^m_{k=1}\sum^n_{j=1}\frac{a_{kj}}{y_j}=\sum^n_{j=1}\frac{1}{y_j}\sum^m_{k=1}a_{kj}=\sum^n_{j=1}\frac{1}{y_j}\cdot y_j=n \end{align} \\ (**)

将(**)代入(*)即可证明原不等式.

\fbox{Remark} 其实这道题一点也不轻松, 作为2018年CTST某天考试的最后一道题出现, 但是我们用示性函数的写法使得这道原本有组合性质的题目完全变成了代数题. 事实上, 这就是我们下面要重点介绍的示性函数的最大的用处, 将一些不方便翻译的组合性质代数化, 并用交换求和的技巧解决问题.

在下面的几道题中, 我们用函数的方法书写示性函数, 使其表达更加清晰.

\fbox{Problem 2} 正整数 n\ge2 , S_1,\cdots ,S_n\subset S , S 是有限集, 满足 \sum^n_{k=1}|S_k|\ge |S| , 设 N 为最接近 \sigma 的正整数, 其中 \sigma=\frac{\sum^n_{k=1}|S_k|}{|S|}-\frac{1}{2} , 则 \exist 1\le i< j\le n , 满足 |S_i\cap S_j|\ge\frac{N(2\sigma-N)}{n(n-1)}|S| .

\fbox{Proof} 对 \forall x\in S, 1\le k\le n : f_k(x)=\begin{cases} 1 &x\in S_k\\ 0 &x\notin S_k \end{cases},f(x)=\sum^n_{k=1}f_k(x)\\

则 |S_k|=\sum_{x\in S}f_k(x) , |S_k\cap S_j|=\sum_{x\in S}f_k(x)f_j(x) . 有 \begin{equation} \begin{split} \sum_{1\le k<j\le n }|S_k\cap S_j| &=\sum_{1\le k <j\le n }\sum_{x\in S}f_k(x)f_j(x)\\ &=\sum_{x\in S}\sum_{1\le k< j\le n }f_k(x)f_j(x)\\ &=\frac{1}{2}\sum_{x\in S}\sum^n_{k=1}\sum_{j\not =k}f_k(x)f_j(x)\\ &=\frac{1}{2}\sum_{x\in S}\sum^n_{k=1}f_k(x)(f(x)-f_k(x))\\ &=\frac{1}{2}\sum_{x\in S}(f^2(k)-\sum^n_{k=1}f^2_k(x))\\ &=\frac{1}{2}\sum_{x\in S}f(x)(f(x)-1)\\ &=\sum_{x\in S}\Bigg(\frac{1}{2}(f(x)-k)(f(x)-k-1)+k\Big(f(x)-\frac{k+1}{2}\Big)\Bigg)\\ &\ge\sum_{x\in S}k\Big(f(x)-\frac{k+1}{2}\Big)=k\Big(\sigma-\frac{k}{2}\Big) \end{split} \end{equation}\\

其中, 倒数第三行的等号基于 f_k(x)=f_k^2(x) , 这也是示性函数的比较好的算数性质.

最后, 取 k=N , 有 \sum_{1\le k<j\le n}|S_k\cap S_j|\ge N\Big(\sigma-\frac{N}{2}\Big)|S| , 根据抽屉原理, 原命题得证.

\fbox{Remark} 这道题是2013年罗马尼亚国家队选拔考试的一道组合题的推广, 我们可以发现, 在使用了示性函数之后, 这道题的推理过程一气呵成.

下面的一道题是2018年12月新星问题征解的第三题, 这道题相当困难, 原解答使用了积分和期望, 妙不可言. 笔者的同学给出了一种比较直接的使用示性函数的做法, 其中用到了泰勒展开, 而且计算量较大, 读者可以选择性跳过. 为了避免符号混淆, 影响阅读, 我稍微更改了一下示性函数的写法. 其中 [n] 表示集合 \{1,2,\cdots, n\} .

\fbox{Problem 3$^*$} 对 \forall n\in \mathbb{N^+} 以及 A_k\not =\varnothing(1\le k\le n) , 求证: \sum^n_{k=1}\sum_{1\le i_1<i_2<\cdots<i_k\le n}(-1)^{k-1}\frac{k}{\bigcup^k_{j=1}A_{i_j}}\ge 0\\

\fbox{Proof} 设 A=\bigcup^n_{j=1}A_j=\{x_1,x_2,\cdots,x_m\} , 定义示性函数 f : f(A_i,x)=\begin{cases} 0 &x\in A_i\\ 1 &x\not =A_i \end{cases}\\

\Bigg\lvert \bigcup_{i\in [n]}A_i \Bigg\rvert=m-\sum_{x\in A}\prod_{j\in[n]}f(A_j,x) , LHS=\sum_{S\subset[n]}\frac{(-1)^{k-1}|S|}{m-\sum_{x\in A}\prod_{j\in[n]}f(A_j,x)}

我们单独考虑 \frac{1}{m-\sum_{x\in A}\prod_{j\in[n]}f(A_j,x)} , 规定 g(S,x)=\prod_{j\in S}f(A_j,x)\in\{0,1\} .

有 \frac{1}{m-\sum_{x\in A}\prod_{j\in[n]}f(A_j,x)}=\frac{1}{m-\sum_{x\in A}g(S,x)} , 显然, m-\displaystyle\sum_{x\in A}g(S,x)>0 .

考虑 \phi(x)=\frac{1}{\alpha-x} , 有 \phi^{(n)}(x)=n!(\alpha-x)^{-n-1} , \phi^{(n)}(0)=n!\alpha^{-n-1} , 下面, 我们对 \frac{1}{m-\sum_{x\in A}g(S,x)} 进行泰勒展开(开始高能):

\begin{align} \frac{1}{m-\sum_{x\in A}g(S,x)}&=\frac{1}{m-\sum_{x\not=x_m}g(S,x)}+\sum^{\infin}_{j=1}\frac{\phi^{(j)}(0)g(S,x_m)^j}{j!}\\ &=\sum^{\infin}_{j=0}\Bigg(m-\displaystyle\sum_{x\not=x_m}g(S,x)\Bigg)^{-j-1}g(S,x_m)^{j} \end{align}\\

显然, g(S,x_m) 的系数均大于 0 .

重复上述过程, 对 \frac{1}{m-\sum_{x\not=x_m}g(S,x)},\frac{1}{m-\sum_{x\not=x_m,x_{m-1}}g(S,x)},\cdots 进行泰勒展开:

\begin{align} \frac{1}{m-\sum_{x\in A}g(S,x)}&=\sum_{\alpha_1\in \mathbb{N}}\cdots\sum_{\alpha_m\in\mathbb{N}}c(\alpha_1,\cdots,\alpha_m)\prod^m_{k=1}g(S,x)^{\alpha_k}\\ &=\sum_{(\alpha_1,\cdots,\alpha_m)\in\mathbb{N}^m} c(\alpha_1,\cdots,\alpha_m)\prod^m_{k=1}g(S,x)^{\alpha_k} \end{align}\\

其中, 系数 c(\alpha_1,\cdots,\alpha_m) 仅与 \alpha_1,\cdots,\alpha_m 有关且显然大于 0 . 那么: \begin{align} &\sum_{S\subset[n]}\frac{(-1)^{k-1}|S|}{m-\sum_{x\in A}\prod_{j\in[n]}f(A_j,x)}\\ =&\sum_{S\subset[n]}(-1)^{|S|-1}|S|\sum_{(\alpha_1,\cdots,\alpha_m)\in\mathbb{N}^m} c(\alpha_1,\cdots,\alpha_m)\prod^m_{k=1}\Bigg(\prod_{j\in S}f(A_j,x_k)\Bigg)^{\alpha_k}\\ =&\sum_{S\subset[n]}(-1)^{|S|-1}|S|\sum_{(\alpha_1,\cdots,\alpha_m)\in\mathbb{N}^m} c(\alpha_1,\cdots,\alpha_m)\prod^m_{k=1}\prod_{j\in S}f(A_j,x_k)^{\alpha_k} \end{align}\\

只要证明 (-1)^{|S|-1}|S|\prod^m_{k=1}\prod_{j\in S}f(A_j,x_k)^{\alpha_k}\ge0 即可.

若 (-1)^{|S|-1}|S|\prod^m_{k=1}\prod_{j\in S}f(A_j,x_k)^{\alpha_k}=0 , 证毕.

若 (-1)^{|S|-1}|S|\prod^m_{k=1}\prod_{j\in S}f(A_j,x_k)^{\alpha_k}=1 , 此时, x_1,x_2,\cdots,x_m\notin A_j , 其中 j\in S . 由于 A_j\in A , 则 A_j=\varnothing , 与题设矛盾!

\fbox{Remark} 我的评价是: 仅供欣赏. 有兴趣的读者可以读一下原解答, 也是妙不可言.

下面的一道题难度不大, 选自2021年中等数学增刊A的模拟卷.

\fbox{Problem 4} \sigma(Y)\stackrel{\Delta}{=}\sum_{y\in Y}y . 正整数 m , n , 正实数 x_1<x_2<\cdots<x_m 给定. 设 A_1,A_2,\cdots,A_n(\not =\varnothing)\subset\{x_1,x_2, \cdots,x_m\}=A , 求下式最小值: \sum^n_{i=1}\sum^n_{j=1}\frac{\sigma(A_i\cap A_j)}{\sigma(A_i)\sigma(A_j)}\\

\fbox{Solution} 对 \forall x\in A,1\le k\le n , f_k(x)=\begin{cases} 1&x\in A_k\\ 0&x\not\in A_k \end{cases} , f(x)=\sum^n_{k=1}f_k(x) \\ \begin{align} \sum^n_{i=1}\sum^n_{j=1}\frac{\sigma(A_i\cap A_j)}{\sigma(A_i)\sigma(A_j)}&=\sum^n_{i=1}\sum^n_{j=1}\frac{\sum_{x\in A}f_i(x)f_j(x)x}{\sum_{y\in A}f_i(y)y\sum_{y\in A} f_j(y)y}\\ &=\sum_{x\in A}x\Bigg(\sum^n_{i=1}\sum^n_{j=1}\frac{f_i(x)f_j(x)}{\sum_{y\in A}f_i(y)y\sum_{y\in A}f_j(y)y}\Bigg)\\ &=\sum_{x\in A}x\Bigg(\sum^n_{i=1}\frac{f_i(x)}{\sum_{y\in A}f_i(y)}\Bigg)\Bigg(\sum^n_{j=1}\frac{f_j(x)}{\sum_{y\in A}f_j(y)y}\Bigg)\\ &=\sum_{x\in A}x\Bigg(\sum^n_{i=1}\frac{f_i(x)}{\sum_{y\in A}f_i(y)}\Bigg)^2\\ &=\frac{\Bigg(\sum_{x\in A}x\Bigg(\sum^n_{i=1}\frac{f_i(x)}{\sum_{y\in A}f_i(y)}\Bigg)^2\Bigg)\Bigg(\sum_{x\in A}x\Bigg)}{\sum_{x\in A}x}\\ &\stackrel{\text{Cauchy}}{\ge}\frac{\Bigg(\sum_{x\in A}x\Bigg(\sum^n_{i=1}\frac{f_i(x)}{\sum_{y\in A}f_i(y)}\Bigg)\Bigg)^2}{\sum_{x\in A}x}\\ &=\frac{\Bigg(\sum_{x\in A}\sum^n_{i=1}\frac{f_i(x)x}{\sum_{y\in A}f_i(y)}\Bigg)^2}{\sum_{x\in A}x}\\ &=\frac{\Bigg(\sum^n_{i=1}\sum_{x\in A}\frac{f_i(x)x}{\sum_{y\in A}f_i(y)}\Bigg)^2}{\sum_{x\in A}x}=\frac{n^2}{\sum_{x\in A}x} \end{align}\\

显然, 当 A_1=A_2=\cdots=A_n=A 时可以取等.

\fbox{Remark} 本来没打算选这道题, 但是因为它不仅涉及了示性函数, 还涉及了示性函数与元素之间的运算, 所以选上. 事实上, 这道题完全可以修改对于示性函数的定义, 比如 f_k(x)=\begin{cases} x&x\in A_k\\ 0&x\not\in A_k \end{cases} , 可以让运算得到一定的化简.原解答使用了算两次原理以及构造方格表, 尽管不难想, 但是没有示性函数的写法那么简单明了.

在做了这么多有关示性函数的问题后, 我们看两个简单的交换求和问题. 事实上, 我们之前看到的有关集合的不等式在使用了示性函数后, 都完全变成了代数问题, 而交换求和则是解决这些代数问题中极其重要的工具. 我们之前见到的交换求和问题都是单表限定, 即不同的求和符号中的限制条件两两不交, 没有相互制约. 下面, 我们看一道女子数学奥林匹克的题目, 见识一下双标限定乃至多表限定是如何处理的.

\fbox{Problem 5} 对任意满足 x_1=1 的实数列 \{x_n\} , 以及任意 n\in \mathbb{N^+} , 求证:

\sum_{i|n}\sum_{j|n}\frac{x_ix_j}{[i,j]}\ge \prod_{p|n}\Big(1-\frac{1}{p}\Big)\\

\fbox{Proof} 右端是我们熟知的欧拉函数 \varphi(n) , 原不等式等价于 \sum_{i|n}\sum_{j|n}\frac{n}{[i,j]}x_ix_j\ge \varphi(n)\\

\begin{align} LHS&=\sum_{i|n}\sum_{j|n}\Bigg(\sum_{[i,j]|k,k\le n}1\Bigg)x_ix_j\\ &=\sum_{i|n}\sum_{j|n}x_ix_j\sum_{[i,j]|k,k\le n}1\\ &=\sum_{k\le n}\sum_{i|(n,k)}\sum_{j|(n,k)}x_ix_k\\ &=\sum_{k\le n}\Bigg(\sum_{i|(k,n)}x_i\Bigg)^2\\ &\ge\sum_{k\le n,(k,n)=1}\Bigg(\sum_{i|(k,n)}x_i\Bigg)^2\\ &=\sum_{k\le n,(k,n)=1}1=\varphi(n) \end{align}\\

\fbox{Remark} 这道题的过程中每一步可谓内涵深刻......对于数论水平有较高(mei you)要求, 冯跃峰老师老师有一篇文章专门分析这道题目, 我就不多扯了, 建议移步: 冯跃峰专栏-数学新星网 (nsmath.cn), 第三十三期: 谈谈双标限定.

在数论中, 莫比乌斯反演同样涉及了大量的比较复杂的双标限定求和问题, 建议读者自行翻阅资料学习. 在证明组合恒等式中, 同样有大量的交换求和问题, 我们举一个例子看一看(在一些书中被称为"Snake Oil" Method)

\fbox{Problem 6} 求和:

\sum_{k}\binom{n+k}{2m+k}\binom{2k}{k}\frac{(-1)^k}{k+1}\\

\fbox{Solution}

\begin{align} F(x)&=\sum_{n\ge0}x^n\sum_{k}\binom{n+k}{2m+k}\binom{2k}{k}\frac{(-1)^k}{k+1}\\ &=\sum_{k}\binom{2k}{k}\frac{(-1)^k}{k+1}x^{-k}\sum_{n\ge0}\binom{n+k}{m+2k}x^{n+k}\\ &=\sum_{k}\binom{2k}{k}\frac{(-1)^k}{k+1}x^{-k}\sum_{r\ge k}\binom{r}{m+2k}x^{r}\\ &=\sum_{k}\binom{2k}{k}\frac{(-1)^k}{k+1}x^{-k}\frac{x^{m+2k}}{(1-x)^{m+2k+1}}\\ &=\frac{x^m}{(1-x)^{m+1}}\sum_{k}\binom{2k}{k}\frac{1}{k+1}\Bigg(\frac{-x}{(1-x)^2}\Bigg)^k\\ &=\frac{-x^{m-1}}{2(1-x)^{m+1}}\Bigg(1-\frac{1+x}{1-x}\Bigg)\\ &=\frac{x^m}{(1-x)^m} \end{align}\\

下面只需要用广义二项式定理将最后一个式子展开, 然后找出 n 次项的系数即可.

\fbox{Remark} 这道题当中用到了比较多的组合恒等式中的常用结论, 读者可以自行验证.

事实上, 交换求和有一个统一的公式, 但是符号表述比较晦涩, 为了行文的完整, 就放出来看看吧: \sum_{i\in A}\sum_{j\in B(i)}a_{i,j}=\sum_{j\in\bigcup_{i\in A}B(i)}\sum_{i\in\{i\in A:j\in B(i)\}}a_{i,j}\\

其实想清楚了之后也不难理解(doge.

再来补一道使用积分和示性函数解决的问题.

\fbox{Problem 7} 对于非负实数 a_1,a_2,\cdots, a_n,b_1,b_2,\cdots,b_n , 求证:

\sum_{1\le i<j\le n}(|a_i-a_j|+|b_i-b_j|)\le \sum^n_{i=1}\sum^n_{j=1}|a_i-b_j|\\

\fbox{Proof} 定义示性函数 f_i,g_i:[0,\infin)\rightarrow\mathbb{R} :

f_i(x)=\begin{cases} 1 &t\in[0,a_i]\\ 0 &t>a_i \end{cases}, g_i(x)=\begin{cases} 1 &t\in[0,b_i]\\ 0 &t>b_i \end{cases}\\

同时, 定义:

f(x)=\sum^n_{i=1}f_i(x),g(x)=\sum^n_{i=1}g_i(x)\\

先计算 \int_{0}^{\infin}f(x)g(x)\text{d}x :

\begin{align} \int_{0}^{\infin}f(x)g(x)\text{d}x&=\int_{0}^{\infin}\Bigg(\sum^n_{i=1}\sum^n_{j=1} f_i(x)g_j(x)\Bigg)\text{d} x\\ &=\sum^n_{i=1}\sum^n_{j=1}\int_{0}^{\infin}f_i(x)g_j(x)\text{d} x\\ &=\sum^n_{i=1}\sum^n_{j=1}\min(a_i,b_j) \end{align}\\

类似的, 有:

\int_{0}^{\infin}f^2(x)\text{d}x=\sum^n_{i=1}\sum^n_{j=1}\min(a_i,a_j) \\ \int_{0}^{\infin}g^2(x)\text{d}x=\sum^n_{i=1}\sum^n_{j=1}\min(b_i,b_j)\\

则:

\int_{0}^{\infin}f^2(x)\text{d}x+\int_{0}^{\infin}g^2(x)\text{d}x=\int_{0}^{\infin}\Big(f^2(x)+g^2(x) \Big)\text{d}x\ge2\int_{0}^{\infin}f(x)g(x)\text{d}x\\

于是:

\sum^n_{i=1}\sum^n_{j=1}\min(a_i,a_j)+\sum^n_{i=1}\sum^n_{j=1}\min(b_i,b_j)\ge2\sum^n_{i=1}\sum^n_{j=1}\min(a_i,b_j)\\

我们熟知: 2\min(x,y)=x+y-|x-y| .

\sum^n_{i=1}\sum^n_{j=1}\ |a_i-a_j|+\sum^n_{i=1}\sum^n_{j=1}|b_i-b_j|\ge2\sum^n_{i=1}\sum^n_{j=1}|a_i-b_j|\\

另一方面, 我们有:

\sum^n_{i=1}\sum^n_{j=1}\ |a_i-a_j|=2\sum_{1\le i<j\le n}|a_i-a_j|\\

证毕.

\fbox{Remark} 这道题选自 \text{Problems From The Book} .

留一个小练习, 作为本文的结尾, 2021年女子数学奥林匹克第六题, 除了用到交换求和, 还需要组合当中的一些小技巧, 不过并不难想.

\fbox{Exercise} S 为有限集. P(S)\stackrel{\Delta}{=}\{S':S'\subset S\} , 对 \forall f:P(S)\rightarrow\mathbb{R} , 求证:

\begin{gather*}\sum_{A\in P(S)}\sum_{B\in P(S)}f(A)f(B)2^{|A\cap B|}\ge0 \end{gather*}\\

解答:

编辑于 2023-06-08 16:39・IP 属地江苏
集合论
数学竞赛
赞同 33
8 条评论
分享
喜欢
收藏
申请转载

赞同 33

分享
暂无评论
文章被以下专栏收录
MO杂货铺
MO杂货铺

%https://zhuanlan.zhihu.com/p/541048384

此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。原文来自 — 版权归原作者所有。

推荐订阅源

博客园 - Eufisky