第一届 TMO 二试

时间:180分钟

总分:220分

1. ($40$ 分) 是否存在正无理数 $a,b(a>1)$, 使得对于所有正整数 $n$, $3\lfloor\dfrac{a^n}{3b}\rfloor-\lfloor\dfrac{a^n}{b}\rfloor=0$? 若存在, 给出一组这样的 $(a,b)$; 若不存在, 请说明理由.

2. ($40$ 分) 求所有的正整数组 $(x,y)$ 使得 $x\mid(y^2+1),y\mid(x^2+1)$ 且 $(x-1)\mid(y^2+y+2)$.

3. ($40$ 分) 给定正整数 $n$, $P(x)$ 是 $n$ 次实系数多项式, 满足 $\forall x\in[0,1]:xP(x)^2\le1$, 求 $P(0)$ 的最大值.

4. ($50$ 分) 在三角形 $ABC$ 中, 内切圆在 $BC,CA,AB$ 上的切点为 $D,E,F$, $K,M,N$ 分别为 $BC,CA,AB$ 中点, $P$ 为 $D$ 关于 $K$ 的对称点, $Q$ 为 $E$ 关于 $M$ 的对称点, $R$ 为 $F$ 关于 $N$ 的对称点. 证明: $\odot DEF,\odot KMN,\odot PQR$ 有一个公共点.

请考生将图作于答题卡上.

5. ($50$ 分) $n$ 维空间中有 $m^n$ 个点 $(a_1,a_2,\cdots,a_n)(a_i\in\{1,2,\cdots,m\})$. 在这些点之间连边构成图 $G$, 其中 $(a_1,a_2,\cdots,a_n)$ 和 $(b_1,b_2,\cdots,b_n)$ 连边, 当且仅当存在唯一的 $i\in\{1,2,\cdots,n\}$, 使得 $|a_i-b_i|=1$, 且 $\forall j\ne i:a_j=b_j$. 求最大的整数 $L=L(n,m)$, 使得对于任意 $G$ 的生成树 $T$, $T$ 中都有一条长为 $L$ 的路径.

注：两个点 $u,v$ 之间的路径是指一个节点序列 $v_0=u,v_1,\cdots,v_{l-1},v_l=v$ 使得 $v_i$ 两两不同且 $v_i$ 与 $v_{i+1}$ 有连边, 此时称 $l$ 为这条路径的长度; $G$ 的一棵生成树是指从 $G$ 中选出一些边, 使得通过这些边，任意两个点之间存在唯一的路径.

解答：

1. 答案: 存在.

   解析: 构造如下: 取$k\in{N^*}$,$k\equiv2 \ (mod\ 3)$,$k>1000$.

   令$\alpha>1>\beta>0$为方程 $x^2-kx+1=0$ 的两根. 二阶线性递推数列${\{x_n}\}_{(n\in{N})} :x_0=x_1=1,x_{n+2}=kx_{n+1}-x_{n}\ (n\in{N)}$.有通项公式:$x_n=A\alpha^n+B\beta^n\ (n\in{N})$ 故$A=\frac{x_1-\beta{x_0}}{\alpha-\beta}>0, B=\frac{\alpha{x_0}-x_1}{\alpha-\beta}>0$.

   由$\beta<1$知: $\exists\ {M}\in{N^*}$使得: 对$\forall\ n\geqslant{M}, 0<B\beta^n<1$. 故对$\forall n\in{N},\lfloor\ A\alpha^{n+M} \rfloor=x_{n+M}-1$

   令$a=\alpha$, $b=\dfrac{1}{A\alpha^M}(若\dfrac{1}{A\alpha^M}为有理数,则取M'=M+1,令b=\dfrac{1}{A\alpha^{M'}})$.

   注意到: $3\lfloor\dfrac{a^n}{3b}\rfloor-\lfloor\dfrac{a^n}{b}\rfloor =\{\dfrac{a^n}{b}\}-3\{\dfrac{a^n}{3b}\}\in\ (-3,1),且3\lfloor\dfrac{a^n}{3b}\rfloor-\lfloor\dfrac{a^n}{b}\rfloor\in{Z}$ .故 $3\lfloor\dfrac{a^{n}}{3b}\rfloor-\lfloor\dfrac{a^{n}}{b}\rfloor=-r_3(\lfloor\dfrac{a^{n}}{b}\rfloor)=-r_3(\lfloor\ A\alpha^{n+M}\rfloor)=-r_3(x_{n+M}-1)$.(这里$r_3(y)表示y\ mod\ 3的余数$). 归纳易知: $x_n\equiv1(mod\ 3)$.于是$r_3(x_{n+M}-1)=0$

   故原命题成立!

   点评: 本题是中等偏困难的代数题.难点在于猜对答案，在猜出答案后构造思路极为清晰,利用二阶线性递推数列通项能很好地计算取整.作为第一题而言是极为困难并且搞心态的！

2. 答案: $(x,y)=(2,1),(2,5),(5,2),(5,13)$

   解析: 设$gcd(x,y)=d$,则: $d\mid1 \Rightarrow{d}=1$.故$x,y$互素.

   又$x\mid(x^2+y^2+1),y\mid(x^2+y^2+1)$. 故$xy\mid(x^2+y^2+1)$.

   设$x^2+y^2+1=kxy$,由$x^2+y^2+1\geqslant2xy+1>2xy知: k\geqslant3$ 下证: $k\geqslant4$时,上述二次方程无正整数解

   若有解,取使得:$x+y$最小的解$(x_0,y_0)$. 若$x_0=y_0$,则: $x_0=y_0=1$, 得到$k=3$, 矛盾!

   不妨设$x_0>y_0$. 设$t$为方程$x^2-ky_0x+y_0^2+1=0$的另一根,由韦达定理:$x_0+t=ky_0, x_0t=y_0^2+1$. 故$t\in{N^*}$.

   由$x_0+y_0$最小性知: $t\geqslant{x_0}$， 于是$ky_0=x_0+t\leqslant2t, 所以t\geqslant\dfrac{ky_0}{2}\geqslant2y_0$.

   故$y_0^2+1=x_0t>y_0\cdot2y_0=2y_0^2,y_0<1$.矛盾! 故$k=3,x^2+y^2+1=3xy$, 所以$y^2=3xy-x^2-1\equiv3y-1-1=3y-2\ (mod\ x-1)$,

   于是得到: $0\equiv\ y^2+y+2\equiv3y-2+y+2=4y\ (mod\ x-1),又4y^2+4y+8\equiv0\ (mod\ x-1)$, 故$x-1\mid8,\ x=2,3,5,9$.

   $x=2\Rightarrow\ y^2-6y+5=0\Rightarrow\ y=1或5$.

   $x=3\Rightarrow\ y^2-9y+10=0\Rightarrow\ y无整数解$.

   $x=5\Rightarrow\ y^2-15y+26=0\Rightarrow\ y=2或13$.

   $x=9\Rightarrow\ y^2-27y+82=0\Rightarrow\ y无整数解$.

   检验知: 上述四解均符合条件.

   综上: $(x,y)=(2,1),(2,5),(5,2),(5,13)$

   点评: 本题是简单的数论题.前两个整除式极其套路,是很标准的无穷递降法,考验基本功.最后一个整除式实际上使得题目更加简单，仅靠前两个整除式能解出所有解为$(F_{2n-1},F_{2n+1})$, 但本身难度已经超出本题。

   3.答案: $2n+1$.

   解析: 取 $P_0(x)=1,P_1(x)=-4x+3,P_{n+2}(x)=2(1-2x)P_{n+1}(x)-P_n(x)$. 则 $P_n(0)=2n+1$, $P_n(sin^2\theta)=\dfrac{\sin(2n+1)\theta}{\sin\theta}(\theta\in(0,\dfrac{\pi}{2}])$.

   另一方面, 对所有满足题意的 $P(x)$, 取 $x_k=\sin^2\dfrac{(2k+1)\pi}{2(2n+1)}(k=0,1,\cdots,n)$,$($于是$x_0<x_1<\cdots<x_n)$, 有 $\sqrt{x_k}P_n(x_k)=(-1)^k$, $(-1)^k\sqrt{x_k}P_n(x_k)=1\ge\sqrt{x_k}|P(x_k)|$, 即 $|P(x_k)|\le(-1)^kP_n(x_k)$.

   由拉格朗日插值, $P(0)=\sum\limits_{k=0}^nP(x_k)\prod\limits_{j\ne k}\dfrac{0-x_j}{x_k-x_j}\le\sum\limits_{k=0}^n|P(x_k)|\prod\limits_{j\ne k}\dfrac{x_j}{|x_k-x_j|}\le\sum\limits_{k=0}^n(-1)^kP_n(x_k)\prod\limits_{j\ne k}\dfrac{x_j}{|x_k-x_j|}=\sum\limits_{k=0}^nP_n(x_k)\prod\limits_{j\ne k}\dfrac{0-x_j}{x_k-x_j}=P_n(0)$.

   综上, $P(0)$ 的最大值为 $2n+1$.

   点评: 本题是较困难的代数题.思路是找到$n+1$个取等的点后使用拉格朗日插值将多项式求出，在带入$P(0)$进行放缩,答案的多项式是难以猜到的，不同于较为熟知的切比雪夫多项式,本题的取等是在$\sin^2\dfrac{(2k+1)\pi}{2(2n+1)}$处取等,猜到取等是困难的一步!

   4.解析:由费尔巴哈定理:$\bigtriangleup(ABC)$九点圆与内切圆切于一点$J$,即$\odot(KMN)$与$\odot(DEF)$切于一点$J$.(不知道怎么把图放上来,这里本人画的图是$\angle C$>$\angle A$>$\angle B$的锐角三角形.)

   设$\bigtriangleup{ABC}$外心与内心分别为$O$,$I$,$I$关于$O$对称点为$I'$.下证:$\bigtriangleup{AOI}\sim\bigtriangleup{JKD}$,于是$I'$与$P$会是相似对应点.

   设$A$在$BC$上的投影为$X$,$I$在$AX$上投影为$Y$,直线$JD$与$\odot(KMN)$交于另一点$L$.

   因为$\odot(DEF)$与$\odot(KMN)$切于$J$,$KX$为$\odot(KMN)$的一条弦且切$\odot(DEF)$.故$L$为$\overset{\frown}{KX}$中点.

   $\angle{XJD}=\angle{KJD}=\frac{1}{2}\angle{KJX}=\frac{1}{2}\angle{KMX}=\frac{1}{2}(\angle{KMC}-\angle{CMX})=\frac{1}{2}(\angle{BAC}-2(\dfrac{\pi}{2}-\angle{BCA}))=\frac{1}{2}(\angle{ACB}-\angle{ABC})=\angle{OAI}=\angle{IAX}$.

   由$\bigtriangleup{JDK}\sim\bigtriangleup{XDL}$得:$\dfrac{JD}{JK}=\dfrac{XD}{XL}=\dfrac{IY}{XL}=\dfrac{AI\sin\angle{IAX}}{AO\sin\angle{XJL}}=\dfrac{AI}{AO}$.(这里用到了九点圆直径等于外接圆半径.)

   故$\bigtriangleup{JKD}\sim\bigtriangleup{AOI}$,$P$与$I'$为相似对应点.

   同理:$\bigtriangleup{JME}(Q)\sim\bigtriangleup{BOI}(I'),\bigtriangleup{JNF}(R)\sim\bigtriangleup{COI}(I')$.

   所以$\angle{JPK}=\angle{AI'O},\angle{JQM}=\angle{BI'O},\angle{JRN}=\angle{CI'O}$.

   设$\bigtriangleup{ABC}$旁心三角形为$\bigtriangleup{I_AI_BI_C}$.

   注意到:$I$为$\bigtriangleup{I_AI_BI_C}$垂心,$O$为$\bigtriangleup{I_AI_BI_C}$九点圆圆心.于是$I'$为$\bigtriangleup{I_AI_BI_C}$外心.故$\bigtriangleup{PQR}$为$I'$关于$\bigtriangleup{ABC}$的垂足三角形.

   故$I',A,Q,R$共圆,$I',B,P,R$共圆,$I',C,P,Q$共圆.

   故$\angle{JPR}=\angle{RPC}-\angle{JPC}=\angle{BI'R}-\angle{AI'O}=\angle{BI'O}-\angle{AI'R}=\angle{JQC}-\angle{RQC}=\angle{JQR}$

   故$J,P,Q,R$四点共圆. 得证!

   点评:本题是困难的几何题.九点圆和内切圆同时出现，使用费尔巴哈定理是自然的.之后难点在于发现关键的相似,从而自然的想到把$P$的相似对应点$I'$作出,再注意到$I'$是一个性质极好的点,从而几乎可将所有角倒到$I'$上,后面就是轻松的倒角步骤.当然,如果学习过垂极点理论,那么证明中的关键相似和费尔巴哈定理则是不必要的过程,只需观察到$\odot(PQR)$为$I'$垂足圆即可.关于费尔巴哈定理和垂极点的证明及性质,可以参考《近代欧氏几何学》.

   5.答案: $L(n,m)=\begin{cases}n(m-1)&,2\nmid m\\nm-1&,2\mid m\end{cases}$

   解析: 设 $D((a_1,a_2,\cdots,a_n),(b_1,b_2,\cdots,b_n))=\sum_{i=1}^n|a_i-b_i|$, 则 $D(u,v)+D(v,w)\ge D(u,w)$.

   对于在 $G$ 中任意两个连边的点 $u,v$, $D(u,v)=1$. 从而对于任意两个点 $u,v$ 与它们之间的路径 $v_0=u,v_1,\cdots,v_{l-1},v_l=v$，都有 $D(u,v)\le\sum_{i=0}^{l-1}D(v_i,v_{i+1})=l$.

   若 $2\nmid m$, 考虑两个点 $u=(1,1,\cdots,1),v=(m,m,\cdots,m)$, 它们在 $T$ 中的路径的长度 $l\ge D(u,v)=n(m-1)$. 故 $T$ 中有一条长为 $L$ 的路径.

   可构造 $T$，其中 $(a_1,a_2,\cdots,a_n),(b_1,b_2,\cdots,b_n)$ 连边当且仅当存在 $i\in\{1,2,\cdots,n\}$ 使得 $a_{i-1}=\dfrac{m+1}{2}$ (我们认为 $a_0=\dfrac{m+1}{2}$ 恒成立), $|a_i-b_i|=1$, 且 $\forall j\ne i:a_j=b_j$. 对 $n$ 归纳证明, $T$ 中的路径长度不会超过 $n(m-1)$, 从而 $L=n(m-1)$.

   $n=1$ 时平凡. 下设 $n\ge2$, $n-1$ 时的情况成立. 对于两个点 $u=(a_1,a_2,\cdots,a_n),v=(b_1,b_2,\cdots,b_n)$, 若 $a_n=b_n$, 由归纳假设知它们之间的路径长度 $l\le(n-1)(m-1)<n(m-1)$; 若 $a_n\ne b_n$, 则它们的路径必然经过 $u'=(\dfrac{m+1}{2},\dfrac{m+1}{2},\cdots,\dfrac{m+1}{2},a_n),v'=(\dfrac{m+1}{2},\dfrac{m+1}{2},\cdots,\dfrac{m+1}{2},b_n)$, 路径长度 $l\le D(u,v)\le D(u,u')+D(u',v')+D(v',v)\le(n-1)\dfrac{m-1}{2}+(m-1)+(n-1)\dfrac{m-1}{2}=n(m-1)$.

   若 $2\mid m$, 设 $f(x)=\begin{cases}x+\frac{m}{2}&,x\le\frac{m}{2}\\x-\frac{m}{2}&,x>\frac{m}{2}\end{cases}$, $f(a_1,a_2,\cdots,a_n)=(f(a_1),f(a_2),\cdots,f(a_n))$.

   考虑两个点 $v,f(v)$, 它们在 $T$ 中的路径 $v_0=v,v_1,\cdots,v_{l-1},v_l=f(v)$ 的长度 $l\ge D(v,f(v))=n\dfrac{m}{2}$. 设 $g(v)=(v_0,v_1)$, 则 $g$ 是一个从 $T$ 的点集合到 $T$ 的边集合的映射.

   因为 $T$ 是树, 所以 $|V(T)|>|E(T)|$. 由抽屉原理, 存在 $u\ne v$ 使得 $g(u)=g(v)$. 设 $u_0=u,u_1=v,\cdots,u_l=f(u)$ 为 $u,f(u)$ 之间的路径, $v_0=v,v_1=u,\cdots,v_{l'}=f(v)$ 为 $v,f(v)$ 之间的路径, 则 $u_l=f(u),u_{l-1},\cdots,u_1=v_0=v,u_0=v_1=u,\cdots,v_{l'}=f(v)$ 为 $f(u),f(v)$ 之间的路径, 它的长度为 $l+l'-1\ge nm-1$.

   可构造 $T$，其中 $(a_1,a_2,\cdots,a_n),(b_1,b_2,\cdots,b_n)$ 连边当且仅当存在 $i\in\{1,2,\cdots,n\}$ 使得 $a_{i-1}=\dfrac{m}{2}$ (我们认为 $a_0=\dfrac{m+1}{2}$ 恒成立), $|a_i-b_i|=1$, 且 $\forall j\ne i:a_j=b_j$. 对 $n$ 归纳证明, $T$ 中的路径长度不会超过 $nm-1$, 从而 $L=nm-1$.

   $n=1$ 时平凡. 下设 $n\ge2$, $n-1$ 时的情况成立. 对于两个点 $u=(a_1,a_2,\cdots,a_n),v=(b_1,b_2,\cdots,b_n)$, 若 $a_n=b_n$, 由归纳假设知它们之间的路径长度 $l\le(n-1)m-1<nm-1$; 若 $a_n\ne b_n$, 则它们的路径必然经过 $u'=(\dfrac{m}{2},\dfrac{m}{2},\cdots,\dfrac{m}{2},a_n),v'=(\dfrac{m}{2},\dfrac{m}{2},\cdots,\dfrac{m}{2},b_n)$, 路径长度 $l\le D(u,v)\le D(u,u')+D(u',v')+D(v',v)\le(n-1)\dfrac{m}{2}+(m-1)+(n-1)\dfrac{m}{2}=nm-1$.

   点评: 本题是极其困难的组合题.在场上初遇难以完整的做出来，入手点在于答案的猜测，在给出二维情形的构造后发现答案应按$m$奇偶分类.奇数部分的证明是较为简单的,运用三角不等式即可放缩得到.偶数部分的证明是本题的精妙所在，完美利用了树的点数大于边数的性质，于是不存在从$V(T)$到$E(T)$的单射，从而找到两条较长的路拼接成了一条更长的路,非常巧妙的想法$!!!$构造部分自然是对$n$归纳,书写好严谨的过程也是本题的一大难点.

二试整体点评:这是一套困难的二试.5道题3h,与正常二试有差异,时间更为紧迫.$T_2$较为简单, $T_1,T_3,T_4,T_5$过于困难,$T_1$极易搞心态,这也让多数同学没有做出$T_2$.$T_3,T_4,T_5$技巧性高(或者说很需要"注意力"),初遇难以做出,也导致了本次考试二试分数极低.