[Dr.Lib]Note:Math – Elegant Proof I

16th CanadianMO 1984

任给7个实数,求证必有两个数x、y满足:

\[0 \leq\frac{x – y}{1+x y} \leq\frac{\sqrt{3}}{3} \]

拿到题目后第一反应就是和什么公式好像……结果还真是……

证明:

设七个数为\(a_{1}< a_{2}< a_{3}< a_{4}< a_{5}< a_{6}<a_{7}\),令\(\theta _{i}=arctan(a_{i})\)。

有\( \frac{-\pi}{2}<\theta _{1}<\theta _{2}<\theta _{3}<\theta _{4}<\theta _{5}<\theta _{6}<\theta _{7}<\frac{\pi}{2}\)

则必有\( 0<\theta _{i+1}-\theta _{i}\leq \frac{-\pi}{6} i \in \left [ 1,6 \right ] \)

则\( 0<tan(\theta _{i+1}-\theta _{i})= \frac{tan(\theta _{i+1})-tan(\theta _{i})}{1+tan(\theta _{i})tan(\theta _{i+1})}\leq \frac{\sqrt{3}}{3} \)即\[0 \leq \frac{x – y}{1+x y} \leq \frac{\sqrt{3}}{3} \]

练习:

50th Moscow MO 1987 求证:从任意三个正数或四个实数中总能取两个数x,y满足 \[0 \leq \frac{x – y}{1+x y} \leq 1 \]

3th CMO WC 1988

(1)设正数a,b,c满足 \((a^{2}+b^{2}+c^{2})^{2}>2(a^{4}+b^{4}+c^{4})\)

求证:a,b,c是三角形的三边。

(2)设\((a_{1}^{2}+a_{2}^{2}+a_{3}^{2}+ … +a_{n}^{2})^{2}>(n-1)(a_{1}^{4}+a_{2}^{4}+…+a_{n}^{4}) n\geq3\),求证:\({a_{n}}\)中任意三个数是三角形的三边。

看起来就是各种因式分解。。

证明:

(1)

由题意得\(2a^{2}b^{2}+2b^{2}c^{2}+2a^{2}c^{2}-a^{4}-b^{4}-c^{4}>0\)

即\((a+b-c)(a+c-b)(b+c-a)(a+b+c)>0\)

不妨设\(a\geq b \geq\ c\)

有\((b+c-a)>0\)即a,b,c是三角形的三边。

(2)

\(n=3\)时由(1)立即可得。

\(n>3\)时

\[(n-1)(a_{1}^{4}+a_{2}^{4}+…+a_{n}^{4}) \]
\[<(a_{1}^{2}+a_{2}^{2}+a_{3}^{2}+ … +a_{n}^{2})^{2} \]
\[=(\frac{a_{1}^{2}+a_{2}^{2}+a_{3}^{2}}{2}+\frac{a_{1}^{2}+a_{2}^{2}+a_{3}^{2}}{2}+ … +a_{n}^{2})^{2} \]
\[\leq (n-1)(\frac{(a_{1}^{2}+a_{2}^{2}+a_{3}^{2})^{2}}{4}+\frac{(a_{1}^{2}+a_{2}^{2}+a_{3}^{2})^{2}}{4}+a_{4}^{4}+…+a_{n}^{4}) (柯西不等式) \]
\[=(n-1)(\frac{(a_{1}^{2}+a_{2}^{2}+a_{3}^{2})^{2}}{2}+a_{4}^{4}+…+a_{n}^{4})\]

所以

\((a_{1}^{2}+a_{2}^{2}+a_{3}^{2})^{2}>2(a_{1}^{4}+a_{2}^{4}+a_{3}^{4})\)

由(1)知\(a_{1},a_{2},a_{3}\)是三角形的三边。

由对称性可知,\({a_{n}}\)中任意三个数是三角形的三边。

【To be continued】

[Dr.Lib]Note:Math – 小技巧们 I


有一正三棱锥P-ABC,O为底面ABC中心。过O做动平面QRS,交PA或其延长线于Q,交PB或其延长线于R,交PC或其延长线于S。
那么\(\frac{1}{PQ}+\frac{1}{PR}+\frac{1}{PS}\)()
A 为定值
B 有最大值无最小值
C 有最小值无最大值
D 既无最大值也无最小值

看到这题,我的第一反应是想想GB的《颠倒过来的式子》,不过貌似里面没有这题。当时觉得变形之后也无明显的意义。这时老师提示了一 步:小题,先降维看看。

有一等腰三角形PBC,O为底边BC中点。过O做直线QR,交PB于R,交PC于S。考察\(\frac{1}{PR}+\frac{1}{PS}\)。
\(\frac{1}{PR}+\frac{1}{PS}\)=\(\frac{PR+PS}{PR*PS}\)。有什么想法吗?
算两次:等面积法。设等腰三角形顶角为\(  \alpha \)腰与O点距离为\(  d \)

\(  SPQR=\frac{PS*PR*sin\alpha }{2} \)

\(  SPQR=\frac{d(PS+PR) }{2}\)

\(\frac{1}{PR}+\frac{1}{PS}=\frac{sin\alpha}{d}\)

三维的情况就很好推广了~

PS:某颜正熙同学提出可以用梅氏定理证二维的情况, Orz

[Dr.Lib]Note:Algorithm – 莫队算法

莫队算法:对于两个区间的查询[l1,r1] ,[l2,r2]如果每增加一个区间元素或者删除,都能做到O(1)的话
那么从[l1,r1]转移到[l2,r2],暴力可以做到|l1-l2|+|r1-r2|,就是manhattan距离
莫队的论文一直没有找到,所以只是大致的了解下,应该是证明出构造出哈密尔顿路径是最优的。
但是可以用manhattan mst来构造,大约会是两倍,然后莫队证明出这样转移的上限是O(n*sqrt(n))。
所以对于这种无修改的区间查询来说
可以先将所有的区间,看成二维平面上的点,求一次manhattan mst,然后根据mst来进行转移
相邻的两个区间的查询转移,暴力解决。

Via http://blog.csdn.net/huzecong/article/details/8576908

http://blog.csdn.net/acm_cxlove/article/details/8894431

在此感谢

据说这个算法是莫涛提出的(Orz!),但是在网上到处都搜不到相关资料,最后问pty才知道的。这个算法是用于处理一类不带修改的区间查询问题的离线算法,其核心在于利用曼哈顿距离最小生成树算法对区间处理顺序进行处理。比如下面这个例题(清橙A1206《小Z的袜子》,就是莫队出的题):

给定一个长为N的序列,每个元素的值是其颜色。有M次询问,每次询问从一个区间中随机选取两个元素同色的概率。

一次询问[l,r]的答案即,其中是区间中第i中颜色的个数。显然暴力是O(NM)的,而且一般的区间问题的思路似乎不适用。

我们先考虑一个简化的问题:所有的查询区间的左端点都是1。那么我们可以按右端点排序,假设已经处理出了[1,r]的答案,考虑转移到[1,r+k],即添加k个元素,这个可以在O(k)的复杂度内求出。那么处理所有区间的复杂度(不考虑排序)就是O(N)。

那么如果是从[l,r]转移到[l’,r’]呢?复杂度即O(|r’-r|+|l’-l|),也即点(l,r)到点(l’,r’)的曼哈顿距离。那么如果将所有询问转化成二维平面中的点,求曼哈顿距离最小生成树,再按照生成树的顺序做,就可以最小化区间之间转移的复杂度。可以证明(我不会证……似乎莫队的论文里有),这样做的复杂度是O(N1.5)的。问题也就得到了解决。

[Dr.Lib]Note:Algorithm – Kruskal

 

[Dr.Lib]Note:Math – \(\Sigma \frac{1}{n^{2}}\)

转载自http://www.ivy-end.com/archives/1098


今天我们来介绍一个曾经在数列题中做过无数遍的数列\(a_{n}=\frac{1}{n^{2}}\),为了方便下文的讨论,我们记\(S_{n}\)为数列\(a_{n}\)的前\(n\)项和。我们做过最熟悉的题目莫过于证明\(S_{n}<2\),这个证明对于大家来说应该是非常容易的\[S_{n}=\sum_{i=1}^{n}\frac{1}{i^{2}}=1+\sum_{i=2}^{n}\frac{1}{i\cdot\left(i-1 \right )}=2-\frac{1}{n}.\]

那么大家是否考虑过,\(\lim_{n \to \infty }S_{n}\)究竟等于多少?我记得严桂华讲过欧拉曾经计算过这个问题,今天在国外一个数学讨论网站上翻到了一篇关于如何计算\(\lim_{n \to \infty }S_{n}\)的问答(原文地址)。在此仅介绍几种方法。

首先给出结果,再用多种方法进行证明\[\lim_{n \to \infty }S_{n}=\frac{\pi^{2}}{6}.\]不得不说,这一结果是非常不可思议的,因为它居然包含了\(\pi\)。读者如果不相信的话,可以自行计算一下,当\(n\)趋向于正无穷时,答案便越接近\(\frac{\pi^{2}}{6}\)。

好了,废话不说,我们进入证明部分。

法一:

当\(0<x<\frac{\pi}{2}\)时,有\(0<\sin{x}<x<\tan{x}\)。至于这个命题的证明,请参考下图:

Mathematics 003-1-1

这样,我们可以得到\[\frac{1}{\tan^{2}{x}}<\frac{1}{x^{2}}<\frac{1}{\sin^{2}{x}}.\]我们知道,\(\frac{1}{\tan^{2}{x}}=\frac{1}{\sin^{2}{x}}-1\)(很容易由三角恒等式导出)。将区间\(\left(0,\frac{\pi}{2}\right)\)等分成\(2^{n}\)个部分,令\(x_{k}=\frac{\pi}{2}\cdot\frac{k}{2^{n}}\),并将不等式两边对\(x_{k}\)进行求和,可以得到\[\sum_{k=1}^{2^n-1} \frac{1}{\sin^2 x_k} – \sum_{k=1}^{2^n-1} 1 < \sum_{k=1}^{2^n-1} \frac{1}{x_k^2} < \sum_{k=1}^{2^n-1} \frac{1}{\sin^2 x_k}.\]我们不妨将不等式右边的表达式记为\(T_{n}\),那么原不等式可以化简为\[T_{n} – \left(2^n – 1\right) < \sum_{k=1}^{2^n-1} \left( \frac{2 \cdot 2^n}{\pi} \right)^2 \frac{1}{k^2} < T_n.\]接下来我们主要考察\(T_{n}\)。它看起来是一个非常复杂的求和,实际上可以非常简单的计算出来。首先,我们考虑下面的式子\[\frac{1}{\sin^2 x} + \frac{1}{\sin^2 (\frac{\pi}{2}-x)} = \frac{\cos^2 x + \sin^2 x}{\cos^2 x \cdot \sin^2 x} = \frac{4}{\sin^2 2x}.\]因此,如果我们将\(T_{n}\)以\(\frac{\pi}{4}\)为中点进行配对(选取区间\(\left(0,\frac{\pi}{2}\right)\)左边的点\(x_{k}\),与右边的点\(\frac{\pi}{2}-x_{k}\)),考虑递推,再加上中点\(\frac{1}{\sin^{2}{\frac{\pi}{4}}}=2\),则可以得到\[T_{n}=4T_{n-1}+2.\]又\(T_{1}=2\),我们可以很容易的得到\(T_{n}\)的通项公式\[T_n = \frac{2(4^n-1)}{3}.\]于是,我们得到了这样的不等式\[\frac{2(4^n-1)}{3} – (2^n-1) \leq \frac{4^{n+1}}{\pi^2} \sum_{k=1}^{2^n-1} \frac{1}{k^2} \leq \frac{2(4^n-1)}{3}.\]两边同时乘以\(\frac{\pi^{2}}{4^{n+1}}\)使得不等式的中间与我们的目标形式更加相似,这样我们又得到一个不等式\[\frac{\pi^{2}}{4^{n+1}} \cdot \frac{2(4^n-1)}{3} – (2^n-1) \leq \sum_{k=1}^{2^n-1} \frac{1}{k^2} \leq\frac{\pi^{2}}{4^{n+1}} \cdot \frac{2(4^n-1)}{3}.\]当\(n\rightarrow\infty\)时,不等式左右两边同时趋向于\(\frac{\pi^{2}}{6}\),由夹逼准则得\(\lim_{n \to \infty }S_{n}=\frac{\pi^{2}}{6}\)。证毕。

法二:

我们可以借助函数\(f\left(x\right)=x^{2},x\in\left[-\pi,\pi\right]\)来找到它对应的三角傅立叶级数\[\frac{a_{0}}{2}+\sum_{n=1}^{\infty }(a_{n}\cos nx+b_{n}\sin x),\]且它是周期收敛的。

又\(f\left(x\right)\)为偶函数,这足够让我们得到它的系数\[a_{n}=\frac{1}{\pi }\int_{-\pi }^{\pi }f(x)\cos nx\;dx\qquad n=0,1,2,3,\cdots,\]因为\[b_{n}=\frac{1}{\pi }\int_{-\pi }^{\pi }f(x)\sin nx\;dx=0\qquad n=1,2,3,\cdots.\]令\(n=0\)得\[a_{0}=\frac{1}{\pi }\int_{-\pi }^{\pi }x^{2}dx=\frac{2}{\pi }\int_{0}^{\pi}x^{2}dx=\frac{2\pi ^{2}}{3}.\]当\(n=1,2,3,\cdots\)时,我们有\[a_{n}=\frac{1}{\pi }\int_{-\pi }^{\pi }x^{2}\cos nx\;dx\\=\frac{2}{\pi }\int_{0}^{\pi }x^{2}\cos nx\;dx=\frac{2}{\pi }\times \frac{2\pi }{n^{2}}(-1)^{n}=(-1)^{n}\frac{4}{n^{2}},\]因为\[\int x^2\cos nx\;dx=\frac{2x}{n^{2}}\cos nx+\left( \frac{x^{2}}{n}-\frac{2}{n^{3}}\right) \sin nx.\]因此\[f(x)=\frac{\pi ^{2}}{3}+\sum_{n=1}^{\infty }\left( (-1)^{n}\frac{4}{n^{2}}\cos nx\right).\]又\(f\left(\pi\right)=\pi^{2}\),我们可以得到\[\pi ^{2}=\frac{\pi ^{2}}{3}+\sum_{n=1}^{\infty }\left( (-1)^{n}\frac{4}{n^{2}}\cos \left( n\pi \right) \right)\]即\[\pi ^{2}=\frac{\pi ^{2}}{3}+4\sum_{n=1}^{\infty }\left( (-1)^{n}(-1)^{n}\frac{1}{n^{2}}\right)\]进一步化简得\[\pi ^{2}=\frac{\pi ^{2}}{3}+4\sum_{n=1}^{\infty }\frac{1}{n^{2}}.\]因此\[\sum_{n=1}^{\infty }\frac{1}{n^{2}}=\frac{\pi ^{2}}{4}-\frac{\pi ^{2}}{12}=\frac{\pi ^{2}}{6}.\]证毕。

法三:

当\(x=0\)时\(\sin{x}\)可以使用泰勒级数展开\[\sin x = x – \frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\cdots.\]于是我们可以得到\[\frac{x^3}{3!}=x\left(\frac{x^2}{\pi^2} + \frac{x^2}{2^2\pi^2}+ \frac{x^2}{3^2\pi^2}+\cdots\right)=x^3\sum_{n=1}^{\infty}\frac{1}{n^2\pi^2},\]即\[\sum_{n=1}^\infty\frac{1}{n^2}=\frac{\pi^2}{6}.\]证毕。

法四:

设\(z\)为复数,考虑\[\frac{\pi^2}{\sin^2\pi z}=\sum_{n=-\infty}^{\infty}\frac{1}{(z-n)^2}\]由复变函数分析可得\[\frac{\pi^2}{\sin^2\pi z}-\frac{1}{z^2}=\sum_{n=1}^{\infty}\frac{1}{(z-n)^2}+\sum_{n=1}^{\infty}\frac{1}{(z+n)^2}.\]这样,当右边\(z=0\)时,我们就可以得到\[\lim_{z\to 0}\left(\frac{\pi^2}{\sin^2\pi z}-\frac{1}{z^2}\right)=2\sum_{n=1}^{\infty}\frac{1}{n^2}.\]又\[\lim_{z\to 0}\left(\frac{\pi^2}{\sin^2\pi z}-\frac{1}{z^2}\right)=\frac{\pi^2}{3}.\]因此\[\sum_{n=1}^{\infty}\frac{1}{n^2}=\frac{\pi^2}{6}.\]证毕。

法五:

这是欧拉的方法。令\[s=\sin^{-1}{x}.\]那么\[\int_{0}^{\frac{\pi}{2}}sds=\frac{\pi^{2}}{8}.\]但是\[\int\limits_0^1 {\frac{{{{\sin }^{ – 1}}x}}{{\sqrt {1 – {x^2}} }}dx} = \frac{{{\pi ^2}}}{8}.\]又\[{\sin ^{ – 1}}x = \int {\frac{{dx}}{{\sqrt {1 – {x^2}} }}} = x + \frac{1}{2}\frac{{{x^3}}}{3} + \frac{{1 \cdot 3}}{{2 \cdot 4}}\frac{{{x^5}}}{5} + \frac{{1 \cdot 3 \cdot 5}}{{2 \cdot 4 \cdot 6}}\frac{{{x^7}}}{7} + \cdots.\]我们可以得到\[\int\limits_0^1 {\left\{ {\frac{{dx}}{{\sqrt {1 – {x^2}} }}\int {\frac{{dx}}{{\sqrt {1 – {x^2}} }}} } \right\}} = \int\limits_0^1 {\left\{ {x + \frac{1}{2}\frac{{{x^3}}}{3}\frac{{dx}}{{\sqrt {1 – {x^2}} }} + \frac{{1 \cdot 3}}{{2 \cdot 4}}\frac{{{x^5}}}{5}\frac{{dx}}{{\sqrt {1 – {x^2}} }} + \cdots } \right\}}.\]但是\[\int\limits_0^1 {\frac{{{x^{2n + 1}}}}{{\sqrt {1 – {x^2}} }}dx} = \frac{{2n}}{{2n + 1}}\int\limits_0^1 {\frac{{{x^{2n – 1}}}}{{\sqrt {1 – {x^2}} }}dx}.\]这样,可以得到\[\int\limits_0^1 {\frac{{{x^{2n + 1}}}}{{\sqrt {1 – {x^2}} }}dx} = \frac{{\left( {2n} \right)!!}}{{\left( {2n + 1} \right)!!}}.\]又所有的次数都是奇数,所以最终的结果为\[\frac{{{\pi ^2}}}{8} = 1 + \frac{1}{2}\frac{1}{3}\left( {\frac{2}{3}} \right) + \frac{{1 \cdot 3}}{{2 \cdot 4}}\frac{1}{5}\left( {\frac{{2 \cdot 4}}{{3 \cdot 5}}} \right) + \frac{{1 \cdot 3 \cdot 5}}{{2 \cdot 4 \cdot 6}}\frac{1}{7}\left( {\frac{{2 \cdot 4 \cdot 6}}{{3 \cdot 5 \cdot 7}}} \right) \cdots,\]\[\frac{{{\pi ^2}}}{8} = 1 + \frac{1}{{{3^2}}} + \frac{1}{{{5^2}}} + \frac{1}{{{7^2}}} + \cdots.\]令\[1 + \frac{1}{{{2^2}}} + \frac{1}{{{3^2}}} + \frac{1}{{{4^2}}} + \cdots = \omega.\]则\[\frac{1}{{{2^2}}} + \frac{1}{{{4^2}}} + \frac{1}{{{6^2}}} + \frac{1}{{{8^2}}} + \cdots = \frac{\omega }{4}.\]这样,我们可以得到\[\frac{\omega }{4} + \frac{{{\pi ^2}}}{8} = \omega.\]即\[\omega = \frac{{{\pi ^2}}}{6}.\]证毕。

法六:

\[\sum_{i=1}^{n}\frac{1}{i^{2}}=\zeta(2)=\frac{4}{3}\sum_{n=0}^{+\infty}\frac{1}{(2n+1)^2}=\frac{4}{3}\int_{0}^{1}\frac{\log y}{y^2-1}dy\]\[=\frac{2}{3}\int_{0}^{1}\frac{1}{y^2-1}\left[\log\left(\frac{1+x^2 y^2}{1+x^2}\right)\right]_{x=0}^{+\infty}dy=\frac{4}{3}\int_{0}^{1}\int_{0}^{+\infty}\frac{x}{(1+x^2)(1+x^2 y^2)}dx\,dy\]
\[=\frac{4}{3}\int_{0}^{1}\int_{0}^{+\infty}\frac{dx\, dz}{(1+x^2)(1+z^2)}=\frac{4}{3}\cdot\frac{\pi}{4}\cdot\frac{\pi}{2}=\frac{\pi^2}{6}.\]证毕。

就介绍这几种方法吧,大家可以有选择的进行阅读。以后数学作业中再有证明\(S_{n} < 2\)的时候,不妨这样写\(\lim_{n \to \infty }S_{n}=\frac{\pi}{6} < 2\),怕老师不承认,可以顺便证明一下,至于给不给分,就不好说了。