[时间复杂度 Time Complexity of Algorithms

（然后把栗子剥开吃掉~ ……

$$T=\frac{n\left ( n-1 \right )}{2}T_{0}+\left ( n-1 \right )T_{1}$$，其中$$T_{0}$$为一次比较需要的时间，$$T_{1}$$为一次交换所需要的时间

（还记得函数在无穷大的极限吗？
n趋向于无穷大时，起作用的将会是n的二次项，也就是$$\frac{n^{2}}{2}T_{0}$$

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

北京数竞 1957

证明：

$$S_{\Delta ABC}=\frac{1}{2}\begin{Vmatrix}\ x_1&y_1 &1 \\ x_2&y_2 &1 \\ x_3&y_3 &1 \ \end{Vmatrix}$$为有理数，而

$$S_{\Delta ABC}=\frac{\sqrt{3}}{4}((x_1-x_2)^2+(y_1-y_2)^2)$$为无理数，矛盾。

49th Moscow MO 1986

$$\left | x \right | < \left | y-z \right | , \left | y \right | < \left | z-x \right |, \left | z \right | < \left | x-y \right |$$

证明：

$\left\{\begin{matrix}x^2<(y-z)^2 \ \\ y^2<(z-x)^2 \\ z^2<(x-y)^2 \ \end{matrix} \right. \ \rightarrow \left\{\begin{matrix}(x-y+z)(x+y-z)<0 \ \\ (y-z+x)(y+z-x)<0 \\ (z-x+y)(z+x-y)<0 \ \end{matrix}\right.$

$$((x+y-z)(y+z-x)(z+x-y))^2<0$$矛盾。

Posted on | 评论

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

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

（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）

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

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

法一： 法六：

$\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}.$证毕。

Posted on | 评论

[Dr.Lib]Note:Math – Iverson bracket

In mathematics, the Iverson bracket, named after Kenneth E. Iverson, is a notation that denotes a number that is 1 if the condition in square brackets is satisfied, and 0 otherwise. More exactly,

$$[P] = \begin{cases} 1 & \text{if } P \text{ is true;} \\ 0 & \text{otherwise.} \end{cases}$$

where P is a statement that can be true or false. This notation was introduced by Kenneth E. Iverson in his programming language APL,while the specific restriction to square brackets was advocated by Donald Knuth to avoid ambiguity in parenthesized logical expressions.

The Iverson bracket converts a Boolean value to an integer value through the natural map $$\textbf{false}\mapsto 0; \textbf{true}\mapsto1$$, which allows counting to be represented as summation. For instance, the Euler phi function that counts the number of positive integers up to n which are coprime to n can be expressed by

$$\phi(n)=\sum_{i=1}^{n}[\gcd(i,n)=1],\qquad\text{for }n\in\mathbb N^+.$$

More generally the notation allows moving boundary conditions of summations (or integrals) as a separate factor into the summand, freeing up space around the summation operator, but more importantly allowing it to be manipulated algebraically. For example

$$\sum_{1\le i \le 10} i^2 = \sum_{i} i^2[1 \le i \le 10].$$

In the first sum, the index $$i$$ is limited to be in the range 1 to 10. The second sum is allowed to range over all integers, but where i is strictly less than 1 or strictly greater than 10, the summand is 0, contributing nothing to the sum. Such use of the Iverson bracket can permit easier manipulation of these expressions.

Another use of the Iverson bracket is to simplify equations with special cases. For example, the formula

$$\sum_{1\le k\le n \atop \gcd(k,n)=1}\!\!k = \frac{1}{2}n\varphi(n)$$

which is valid for n > 1 but which is off by 1/2 for n = 1. To get an identity valid for all positive integers n (i.e., all values for which $$\phi(n)$$ is defined), a correction term involving the Iverson bracket may be added:

$$\sum_{1\le k\le n \atop \gcd(k,n)=1}\!\!k = \frac{1}{2}n(\varphi(n)+[n=1])$$

-By Wikipedia https://en.wikipedia.org/wiki/Iverson_bracket

Posted on | 评论