意大利几何学家 L. Mascherom 于 \(1797\) 年证明了, 凡是能用尺规作出的几何图形都可以仅仅使用圆规来完成. \(1833\) 年, Jakob Steiner 根据 Poncelet 的想法, 指出: 如果给定一个圆和它的中心, 那么, 能用尺规作出的几何图形都能单独用直尺来作出.
我一直很好奇, 这些结论究竟是如何证明的? Ross Honsberger 在他的书, “Ingenuity in Mathematics”, 的第 \(15\) 节提供了一个详尽的证明, 这一节的标题是: Mascheroni and Steiner. \(1994\) 年, Norbert Hungerbuhler 给出了 Mascherom 的结果, 所谓的Mohr–Mascheroni定理, 的一个简单的证明.
Problem 1 (Evangelos Psychas, Greece)
It is obvious that
\[\angle JFL=\angle JBM-\angle FMB=\frac12(\angle BAC+\angle BCA)-\frac12\angle BCA=\frac12\angle BAC,\]
therefore \(J,L,A\) and \(F\) belong to a circle which implies that \(\angle JFS=90^{\circ}\). But \(\angle JMS=90^{\circ}\), so \(J,M,F\) and \(S\) are concyclic, \(\angle JSM=\angle JFM=\frac12\angle BAC\).
Similarly, \(\angle JTM=\frac12\angle BAC\), so \(\angle JSM=\angle JTM\).
Since \(JM\perp ST\), we obtain \(SM=MT\).
Problem 2 (Angelo di Pasquale, the current Australian leader)
It is easy to see that
\[a_k+1=a_k+\frac 1{k-1}+\dotsb+\frac 1{k-1}\geqslant k\sqrt[k]{\frac{a_k}{(k-1)^{k-1}}},\]
so \((a_k+1)^k\geqslant\frac{k^k}{(k-1)^{k-1}} \,a_k,\) the inequality is strict unless \(a_k=\frac1{k-1}\). Multiplying analogous inequalities for \(k=2,3,\dotsc,n\) yields
\[ \prod_{k=2}^n(a_k+1)^k\geqslant n^na_2a_3\dotsm a_n=n^n. \]
the inequality is strict because \(a_k=\frac1{k-1}\) holds for all \(k\in\{2,3,\dotsc,n\}\) is not possible .
Problem 3 (David Arthur, Canada)
The problem was actually written two years ago.
1. We can assume \(n=2^k, N=n+1\).
The binary digits of \(1,2,\dotsc,2^k\) are \(\overline{a_1a_2\ldots a_{k+1}}\), where \(a_i(i=1,2,\dotsc,k+1)\) is \(0\) or \(1\); then, let \(T\) is the set of all the \(2^k\) binary digits. The binary digit of \(2^k+1\) is \(100\ldots01.\) Define
\[S_1=\{100\ldots0\}, S_i=\{\overline{a_1a_2\ldots a_{k+1}}\in T|a_1=0, a_i=1\}, i=2,3,\dotsc,k+1.\]
\[(2-p)p^{k+1}-1.99^k>2.\]
We will prove that if \(N\in\left(1.99^k+1, (2-p)p^{k+1}\right)\), then B cannot specify a set \(X(|X|\leqslant N-1)\) such that \(x\in X\).
\(T=\{1,2,\dotsc, N\}\). \(j\in\Bbb N\), The \( j\)-th question consists of \( B\) choosing a set \( S_j\subset T\) and we define \(P_j\) is \(S_j\) or \(S_j^C\) depend on the answer: if A answer it with yes, \(P_j=S_j\); Otherwise, \(P_j=S_j^C\). Let \(P_0=T\). Define \(q_j\) as follows:
\[q_j=q_j(P_j)=a_0+a_1p+a_2p^2+\dotsb+a_jp^j,\]
where \(a_0=\left|P_j\right|,a_i=\left|P_{j-i}\setminus \left(P_j\cup P_{j-1}\cup\cdots\cup P_{j-i+1} \right)\right|(i=1,2,\dotsc,j).\) It is easy to see that \(\sum\limits_{i=0}^ja_i=N.\) \(q_0=N.\)
The player \( A\) can keep the following relation holds:
\[q_j<\frac N{2-p}, j\geqslant0.\]
In fact, \(q_0=N<\frac N{2-p}.\) We assume that \(q_j<\frac N{2-p}\), then A can choose \( P_{j+1}\in\left\{S_{j+1},S_{j+1}^C\right\}\) such that \(q_{j+1}<\frac N{2-p}\). Let
\[q_{j+1}(S_{j+1})=b_0+b_1p+b_2p^2+\dotsb+b_jp^j+b_{j+1}p^{j+1},\]
\[q_{j+1}(S_{j+1}^C)=c_0+c_1p+c_2p^2+\dotsb+c_jp^j+c_{j+1}p^{j+1}.\]
Notice that \(b_0+c_0=N,b_i+c_i=a_{i-1}(i=1,2,\dotsc,j+1),\) so
\begin{equation*}\begin{split}q_{j+1}(S_{j+1})+q_{j+1}(S_{j+1}^C)&=N+p(a_0+a_1p+a_2p^2+\dotsb+a_jp^j)\\
&<N+p\cdot\frac N{2-p},\end{split}\end{equation*}
hence
\[ \min\left\{q_{j+1}(S_{j+1}),q_{j+1}(S_{j+1}^C)\right\}< \frac{N}2+\frac p2\cdot\frac N{2-p}=\frac N{2-p}.\]
so, A can take \( P_{j+1}\in\left\{S_{j+1},S_{j+1}^C\right\}\).
Since \(q_j<\frac N{2-p}<p^{k+1},\) we get that for \(i\geqslant k+1, a_i=0,\) then B cannot exclude a number in \(T\), and cannot specify a set \(X(|X|\leqslant N-1)\) such that \(x\in X\).
1. 可以认为 \(n=2^k, N=n+1\). 采用二进制.
把 \(1,2,\dotsc,2^k\) 都写成二进制: \(\overline{a_1a_2\ldots a_{k+1}}\), 这里 \(a_i(i=1,2,\dotsc,k+1)\) 是 \(0\) 或者 \(1\); 然后, 记 \(T\) 为这 \(2^k\) 个二进制数组成的集合. \(2^k+1\) 的二进制表示是 \(100\ldots01.\) 令
\[S_1=\{100\ldots0\}, S_i=\{\overline{a_1a_2\ldots a_{k+1}}\in T|a_1=0, a_i=1\}, i=2,3,\dotsc,k+1,\]
也就是说, \(S_i\) 就是 \(T\) 中所有满足 \(a_i=1\) 的元素组成的子集 \(( i=1,2,\dotsc,k+1).\)
乙采用如下问题, 可保证获胜: 第一次提问, 选择 \(S_1\), 并且接下来也一直选取\(S_1\), 甲的回答会出现两种情况:
2. 解答 \(1\) 任取实数 \(p\) 使得 \(1.99<p<2\), 再选取正整数 \(k_0\), 使得当 \(k>k_0\) 时
\[(2-p)p^{k+1}-1.99^k>2.\]
设正整数 \(N\) 使得 \(1.99^k+1<N<(2-p)p^{k+1}\). 如果 \(n=N-1\), 我们来证明甲有办法使乙无法胜利.
\(T=\{1,2,\dotsc, N\}\). \(j\) 是正整数, 记 \(S_j\subset T\) 是乙的第 \(j\) 个问题展示的集合, 设 \(P_j\) 为 \(S_j\) 或者 \(S_j^C\), 取决于甲对 \(S_j\) 的答案: 若甲的回答是”是”, \(P_j=S_j\), 否则 \(P_j=S_j^C\); \(P_0=T\). 定义 \(q_j(j\geqslant0)\) 如下:
\[q_j=q_j(P_j)=a_0+a_1p+a_2p^2+\dotsb+a_jp^j,\]
这里 \(a_0=\left|P_j\right|,a_i=\left|P_{j-i}\setminus \left(P_j\cup P_{j-1}\cup\cdots\cup P_{j-i+1} \right)\right|(i=1,2,\dotsc,j).\) 此时 \(\sum\limits_{i=0}^ja_i=N.\) 注意 \(q_0=N.\)
我们指出, 甲可以使得
\[q_j<\frac N{2-p}, j\geqslant0\]
成为事实.
\(q_0=N<\frac N{2-p}.\) 假设已有 \(q_j<\frac N{2-p}\), 甲可选取 \( P_{j+1}\in\left\{S_{j+1},S_{j+1}^C\right\}\) 使得 \(q_{j+1}<\frac N{2-p}\). 事实上,
\[q_{j+1}(S_{j+1})=b_0+b_1p+b_2p^2+\dotsb+b_jp^j+b_{j+1}p^{j+1},\]
\[q_{j+1}(S_{j+1}^C)=c_0+c_1p+c_2p^2+\dotsb+c_jp^j+c_{j+1}p^{j+1}.\]
注意 \(b_0+c_0=N,b_i+c_i=a_{i-1}(i=1,2,\dotsc,j+1),\) 于是
\begin{equation*}\begin{split}q_{j+1}(S_{j+1})+q_{j+1}(S_{j+1}^C)&=N+p(a_0+a_1p+a_2p^2+\dotsb+a_jp^j)\\
&<N+p\cdot\frac N{2-p},\end{split}\end{equation*}
因之
\[ \min\left\{q_{j+1}(S_{j+1}),q_{j+1}(S_{j+1}^C)\right\}< \frac{N}2+\frac p2\cdot\frac N{2-p}=\frac N{2-p}.\]
于是, 可以选取 \( P_{j+1}\in\left\{S_{j+1},S_{j+1}^C\right\}\) 达到我们的要求.
既然 \(q_j<\frac N{2-p}<p^{k+1},\) 那么, 只要 \(i\geqslant k+1,\) 必定 \(a_i=0,\) 这导致乙无法排除 \(T\) 的任何一个元素, 不能指定一个集合\(X(|X|\leqslant N-1),\) 使得 \(x\in X\), 于是对于 \(n=N-1\), 乙不能取得胜利.
解答 \(2\) 记 \(p,q\) 是满足 \(1.99<p<q<2\) 的实数, 选取正整数 \(k_0\) 使得
\[\left(\frac pq\right)^{k_0}\leqslant 2\left(1-\frac q2\right),\quad p^{k_0}-1.99^{k_0}>2.\]
对任意 \( k\geqslant k_0\), 选取 \( N\in\left(1.99^k+1, p^k\right)\). \( T=\{1,2,\dotsc, N\}\). \(j\) 是正整数, 记 \(S_j\subset T\) 是乙的第 \(j\) 个问题所问的集合, \(P_j\) 是 \(S_j\) 或者 \(S_j^C\), 取决于甲对 \(S_j\) 的答案: 若甲的回答是”是”, \(P_j=S_j\), 否则 \(P_j=S_j^C\); \(P_0=T\). 我们来指出, 甲有策略, 通过回答”是”或者”否”, 使得
\[ P_j\cup P_{j+1}\cup\cdots\cup P_{j+k}=T\]
对所有 \(j\in\Bbb N\) 成立.
定义 \( (\mathbf{x})_{j=0}^\infty=\left(x_1^j, x_2^j, \dotsc, x_N^j\right) \) 如下: \( x_1^0=x_2^0=\cdots =x_N^0=1 \); 在 \(P_{j+1}\) 选定之后, 定义 \( \mathbf x^{j+1} \):
\begin{equation}x_i^{j+1}=\left\{\begin{array}{rl} 1,& i\in P_{j+1},\\ q\, x_i^j, & i\notin P_{j+1}. \end{array}\right.\end{equation}
只要甲使得成立 \(x_i^j\leqslant q^k(1\leqslant i\leqslant N, j\geqslant0)\), 那么乙不能指定一个集合\(X(|X|\leqslant N-1),\) 使得 \(x\in X\), 于是对于 \(n=N-1\), 乙无法取得胜利.
记 \( T(\mathbf x)=\sum\limits_{i=1}^N x_i\), 甲只要使得 \( T\left(\mathbf x^j\right)\leqslant q^k( j\geqslant0)\) 即可. 这是可以做到的:
显而易见的事情是, \( T\left(\mathbf x^0\right)=N\leqslant p^k < q^k\).
假设已有 \( T\left(\mathbf x^j\right)\leqslant q^k\), 甲可以就乙的 \(S_{j+1}\) 选取 \( P_{j+1}\in\left\{S_{j+1},S_{j+1}^C\right\}\) 使得 \( T\left(\mathbf x^{j+1}\right)\leqslant q^k \). 假定甲回答”是”, 此时 \( P_{j+1}=S_{j+1}\), 记 \(\mathbf y\) 是根据 \((1)\) 得到的序列; 相应地, 记 \(\mathbf z\) 是甲回答”否”, \( P_{j+1}=S_{j+1}^C\), 根据 \((1)\) 得到的序列. 于是
\[ T\left(\mathbf y\right)=\sum_{i\in S_{j+1}^C} qx_i^j+\left|S_{j+1}\right|,\]
\[ T\left(\mathbf z\right)=\sum_{i\in S_{j+1}} qx_i^j+\left|S_{j+1}^C\right|.\]
因此
\[ T\left(\mathbf y\right)+T\left(\mathbf z\right)= q\cdot T\left(\mathbf x^j\right)+ N\leqslant q^{k+1}+ p^k, \]
根据选取的 \(k_0\) 的性质, 得
\[ \min\left\{T\left(\mathbf y\right),T\left(\mathbf z\right)\right\}\leqslant \frac{q}2\cdot q^k+\frac{p^k}2\leqslant q^k.\]
Problem 4 (Liam Baker, South Africa)
首先指出 \(f\) 的 \(3\) 条性质:
根据性质 \(3\), 若 \(f(1)=0,\) 则 \(f\) 有周期 \(1\), 故而 \(f(x)=c\) 对所有 \(x\) 成立, 这又迫使 \(f(x)=0\) 对所有 \(x\). 下面假设 \(f(1)\neq0.\)
令 \(a=b=1,c=-2\), 得 \(f(2)=0\) 或者 \(f(2)=4f(1).\)
若 \(f(2)=0\), 由第 \(3\) 条性质, \(f\) 有如下形式:
\begin{equation}f(x)=\left\{\begin{array}{rl}0,& 2\mid n,\\ c, & 2\not\mid n.\end{array}\right.\end{equation}
这里 \(c\) 是任意的整数. 很容易验证, 这样的函数都符合要求.
若 \(f(2)=4f(1)\), 则 \(i=0,1,2\) 时, 已有 \(f(i)=f(1)i^2.\) 假定当 \(k=0,1,2,\dotsc, n\) 时, \(f(i)=f(1)i^2\) 已经成为事实, 由 \(1+n+(-1-n)=0\) 得
\[f(1)^2+n^4f(1)^2+f(n+1)^2=2n^2f(1)^2+2(n^2+1)f(n+1)f(1),\]
这也就是
\[\left(f(n+1)-(n+1)^2f(1)\right)\left(f(n+1)-(n-1)^2f(1)\right)=0.\]
如果 \(f(n+1)=f(1)(n-1)^2\), 由 \((n+1)+(1-n)-2=0\) 得
\[2(n-1)^4f(1)^2+16f(1)^2=2 (n-1)^4f(1)^2+16(n-1)^2f(1)^2,\]
于是 \(n=2,f(3)=f(1)\). 由 \(1+3-4=0\) 得 \(2f(1)^2+f(4)^2=2f(1)^2+4f(1)f(4),\) 从而 \(f(4)=0\) 或者 \(f(4)=4f(1)=f(2)\). 假定 \(f(4)\neq0\), 由 \(2+2-4=0\) 得 \(2f(2)^2+f(4)^2=2f(2)^2+4f(2)f(4),\) 于是 \(f(4)=4f(2).\) 结合已经得到的 \(f(4)=f(2)\) 得\(f(2)=0\). 这不可能! 于是 \(f(4)=0\), \(f\) 有周期 \(4\), 所以
\begin{equation}f(x)=\left\{\begin{array}{rl}0,& 4\mid n,\\ c, & 2\nmid n,\\ 4c, & n\equiv2\pmod4\end{array}\right.\end{equation}
这里 \(c\) 是任意的整数. 很容易验证, 这样的函数都符合要求.
如果 \(f(n)=f(1)n^2\) 对所有的正整数 \(n\) 都成立, 即
\begin{equation}f(n)=cn^2,\end{equation}
这里 \(c\) 是任意的整数. 很容易验证, 这样的函数都符合要求.
综上所述, 所有形如 \((2),(3),(4)\) 的函数就是要求的函数.
Problem 5 (Josef Tkadlec, Czech Republic)
解答 \(1\) 把以 \(A\) 为心, \(AC\) 为半径的圆和以 \(B\) 为心, \(BC\) 为半径的圆分别记为 \(\odot A,\odot B,\) \(CD\) 即是两圆根轴. 分别过 \(A,B\) 作 \(BX,AX\) 的垂线 \(AF,BE\), 垂足为 \(F,E\). 设 \(AF,BE\) 相交于点 \(W\), 则 \(X\) 是 \(\triangle WAB\) 的垂心, 于是 \(W\) 在 \(DC\) 的延长线上.
由 \(AL^2=AC^2=AD\cdot AB=AF\cdot AW\) 得 \(AL\perp WL, WL\) 是\(\odot A\) 的切线. 同理 \(BK\perp WK, WK\) 是\(\odot B\) 的切线. \(W\) 在两圆根轴上, 故而 \(WL=WK\). 结合 \(AL\perp WL, BK\perp WK\) 就推出了 \(ML=MK\).
解答 \(2\) 把以 \(A\) 为心, \(AC\) 为半径的圆和以 \(B\) 为心, \(BC\) 为半径的圆分别记为 \(\odot A,\odot B,\) \(CD\) 即是两圆根轴. 分别延长 \(AX,BX\) 交 \(\odot B,\odot A\) 于 \(P,Q\) 两点. \(X\) 在根轴上, 所以 \(L,P,Q,K\) 四点共圆, 记此圆为 \(\odot O\).
\(AC\) 为 \(\odot B\) 的切线, 所以 \(AL^2=AC^2=AK\cdot AP\), \(AL\) 是 \(\odot O\) 的切线. 同理, \(BK\) 也是 \(\odot O\) 的切线, 故而 \(ML=MK\).
Problem 6 (Dušan Djukić, Serbia)
记 \(M=\max\{a_1,\dotsc, a_n\}\), 那么 \(1\cdot 3^{M-a_1}+ 2\cdot 3^{M-a_2}+\dotsb + n\cdot3^{M-a_n}=3^M\), 于是
\[1+2+\dotsb+n=\frac{n(n+1)}2\equiv1\pmod2,\]
此时必定 \(n\equiv1,2\pmod4\).
下面来证明, 对形如 \(4k+1\) 或者 \(4k+2\) 的 正整数 \(n\), 可以找到符合要求的 \(a_1,a_2,\dotsc,a_n\).
先对 \(n=4k+1(k\geqslant0)\) 找出符合要求的 \(\mathbf a\): 当\(k=0\) 时, \(a_1=0\) 可以. 下面假设 \(k>0\).
设 \(\mathbf g=\left(1, 2, \dotsc, 4k,4k\right)\), 其分量用 \(g_i\) 表示. 记 \(\mathbf a=\left(a_1, a_2, \dotsc, a_{4k+1}\right)\) 为 \((1,2,\dotsc,4k+1)\) 的一个排列, \(\displaystyle S(\mathbf a)=\sum_{i=1}^{4k+1}\frac{a_i}{3^{g_i}}.\) 由于 \(\displaystyle \sum_{i=1}^{4k+1}\frac1{2^{g_i}}=1,\) 因此只要找出一个 \(\mathbf a \) 使得 \(\displaystyle S(\mathbf a)=1\) 即可.
令
\[\mathbf a=\left(2,1,4,3,\dotsc,2k,2k-1,2k+2,2k+1,\dotsc,4k,4k-1,4k+1\right),\]
则 \(\displaystyle S(\mathbf a)=1+\frac{2k}{3^{4k}}.\) 记
\[\mathbf a\prime=\left(2,1,4,3,\dotsc,2k,2k-1,2k+1,\dotsc,4k,4k-1,4k+1,2k+2\right),\]
则 \(\displaystyle S(\mathbf a)-S(\mathbf a\prime)=\frac{2k}{3^{4k}}\), 故而 \(\displaystyle S(\mathbf a\prime)=1.\)
对序列 \(\mathbf a=\left(a_1, a_2, \dotsc, a_n\right)\), 记
\[L(\mathbf a)=\sum_{i=1}^n\frac1{2^{a_i}},R(\mathbf a)=\sum_{i=1}^n\frac i{3^{a_i}}.\]
假定对 \(n=2m+1\) 存在非负整数序列 \(\mathbf a=\left(a_1, a_2, \dotsc, a_n\right)\) 使得 \(L(\mathbf a)=R(\mathbf a)=1\), 考虑序列\(\mathbf a^\prime=(a_1^\prime,\dots, a_{n+1}^\prime)\):
\[a_j^\prime=\left\{\begin{array}{rl} a_j,& j\notin \{m+1,2m+2\},\\
a_{m+1}+1,& j\in \{m+1,2m+2\}.\end{array}\right.\]
可见
\[L\left(\mathbf a^\prime\right)=L(\mathbf a)-\frac1{2^{a_{m+1}}}+2\cdot \frac1{2^{a_{m+1}+1}}=1,\]
\[R\left(\mathbf a^{\prime}\right)=R(\mathbf a)- \frac{m+1}{3^{a_{m+1}}}+\frac{m+1}{3^{a_{m+1}+1}}+\frac{2m+2}{3^{a_{m+1}+1}}=1.\]
我们对 \(n=2m+2\) 找到了合乎要求的非负整数序列.
综上, 满足 \(n\equiv1,2\pmod4\) 的正整数就是所求.
Comments on the problems
可以把本届 IMO 与 \(2000\) 年做一个比较. 这两届IMO的 \(6\) 个问题, 难度相当, 在IMO历史上, 我个人觉得至多中等; 风格也极为相似: 最难的都是第 \(3\) 题, 碰巧都是组合, 都有 \(2\) 个部分, 一个肯定一个否定, 解答策略也不无相似.
关于本届 IMO 的 problem \(3\)
\(1\). 有这么一个趣味的数学游戏, 书上应该不难找到:
把 \(1,2,\dotsc,31\) 都写成二进制: \(\overline{a_5a_4a_3a_2a_1}\), 这里 \(a_i(i=1,2,3,4,5)\) 是 \(0\) 或 \(1\); 然后, 记 \(T\) 为这 \(31\) 个二进制数组成的集合. 令
\[ S_i=\{\overline{a_5a_4a_3a_2a_1}\in T| a_i=1\}, \]
也就是说, \(S_i\) 就是 \(T\) 中所有满足 \(a_i=1\) 的元素组成的子集, \(|S_i|=16( i=1,2,3,4,5).\)
现在取来 \(5\) 张纸, 把 \(S_i\) 中的 \(16\) 个数写在第 \(i\) 张纸上\((i=1,2,3,4,5)\), 就成了一种生日预测卡: 游戏者看到的, 就是这 \(5\) 张卡片. 然后, 利用这套卡片来猜测对方的生日: 你只要告诉我, 哪几张卡片上有你的生日, 我就能知道你的生日是哪一天.
这个游戏背后的玄机, 和我们给出的 \(1\) 的解法, 是一致的. 当然, 并不是说\(1\) 只能这么解决. 乙有别的提问途径, 也可保证获胜, 只不过没有这么轻松.
\(2\). 难度稍大一些, 但我们采取的手段也不新鲜: 考察一个辅助函数, 这个函数有某种性质, 单调性, 有界, 不变量等等, 反映的都是隐藏在游戏中的某个”量”的性质. \(2000\) IMO 的 problem \(3\) 的 \(2\) 是这么解决的, \(1986\) 年 IMO 的 problem \(3\) 仍然是这样的思路.
游戏中出现的量是”离散”而不是”连续”的, 因此, 这种做法屡试不爽!
\(3\). 这里给出的”两种”证法, 实质上没有任何差别.
Tuesday, July 10, 2012 9:00 am-1:30 pm
Problem 1. Given triangle \(ABC\) the point \(J\) is the centre of the excircle opposite the vertex \(A\). This excircle is tangent to the side \(BC\) at \(M\), and to the lines \(AB\) and \(AC\) at \(K\) and \(L\), respectively. The lines \(LM\) and \(BJ\) meet at \(F\), and the lines \(KM\) and \(CJ\) meet at \(G\). Let \(S\) be the point of intersection of the lines \(AF\) and \(BC\), and let \(T\) be the point of intersection of the lines \(AG\) and \(BC\).
Prove that \(M\) is the midpoint of \(ST\).
(The excircle of \(ABC\) opposite the vertex \(A\) is the circle that is tangent to the line segment \(BC\), to the ray \(AB\) beyond \(B\), and to the ray \(AC\) beyond \(C\).)
Problem 2. Let \(n\geqslant 3\) be an integer, and let \(a_2,a_2,\dotsc,a_n\) be positive real numbers such that \(a_2a_3\dotsm a_n=1.\) Prove that
\[ \left(1+a_2\right)^2\left(1+a_3\right)^3\dotsm\left(1+a_n\right)^n>n^n.\]
Problem 3. The liar’s guessing game is a game played between two players \(A\) and \(B\). The rules of the game depend on two positive integers \(k\) and \(n\) which are known to both players.
At the start of the game \(A\) chooses integers \(x\) and \(N\) with \(1\leqslant x \leqslant N\). Player \(A\) keeps \(x\) secret, and truthfully tells \(N\) to player \(B\). Player \(B\) now tries to obtain information about \(x\) by asking player \(A\) questions as follows: each question consists of \(B\) specifying an arbitrary set \(S\) of positive integers (possibly one specified in some previous question), and asking \(A\) whether \(x\) belongs to \(S\). Player \(B\) may ask as many such questions as he wishes. After each question, player \(A\) must immediately answer it with yes or no, but is allowed to lie as many times as she wants; the only restriction is that, among any \(k+1\) consecutive answers, at least one answer must be truthful.
After \(B\) has asked as many questions as he wants, he must specify a set \(X\) of at most \(n\) positive integers. If \(x\) belongs to \(X\), then \(B\) wins; otherwise, he loses. Prove that:
Wednesday, July 11, 2012 9:00 am-1:30 pm
Problem 4. Find all functions \(f:\Bbb Z \rightarrow\Bbb Z\) such that, for all integers \( a,b,c\) that satisfy \(a+b+c=0\), the following equality holds:
\[ f(a)^2+f(b)^2+f(c)^2=2f(a)f(b)+2f(b)f(c)+2f(c)f(a). \]
(Here \(\Bbb Z\) denotes the set of integers.)
Problem 5. Let \( ABC \) be a triangle with \(\angle BCA=90^\circ\), and let \(D\) be the foot of the altitude from \(C\). Let \(X\) be a point in the interior of the segment \(CD\). Let \(K\) be the point on the segment \(AX\) such that \(BK=BC\). Similarly, let \(L\) be the point on the segment \(BX\) such that \(AL=AC\). Let \(M\) be the point of intersection of \(AL\) and \(BK\).
Show that \(MK=ML\).
Problem 6. Find all positive integers \(n\) for which there exist non-negative integers \(a_1,a_2,\dotsc,a_n\) such that
\[\frac1{2^{a_1}}+\frac1{2^{a_2}}+\dotsb+\frac1{2^{a_n}}=\frac1{3^{a_1}}+\frac2{3^{a_2}}+\dotsb+\frac n{3^{a_n}}= 1.\]
2012年7月10日, 星期二
1. 设 \(J\) 为三角形 \(ABC\) 顶点 \(A\) 所对旁切圆的圆心. 该旁切圆与边 \(BC\) 相切于点 \(M\), 与直线 \(AB\) 和 \(AC\) 分别相切于点\(K\) 和 \(L\). 直线 \(LM\) 和 \(BJ\) 相交于点 \(F\), 直线 \(KM\) 与 \(CJ\) 相交于点 \(G\). 设 \(S\) 是直线 \(AF\) 和 \(BC\) 的交点, \(T\) 是直线 \(AG\) 和 \(BC\) 的交点.
证明: \(M\) 是线段 \(ST\) 的中点.
(三角形 \(ABC\) 的顶点 \(A\) 所对的旁切圆是指与边 \(BC\) 相切, 并且与边 \(AB,AC\) 的延长线相切的圆.)
2. 设整数 \(n\geqslant 3\), 正实数\(a_2,a_2,\dotsc,a_n\) 满足 \(a_2a_3\dotsm a_n=1.\) 证明:
\[ \left(1+a_2\right)^2\left(1+a_3\right)^3\dotsm\left(1+a_n\right)^n>n^n.\]
3. “欺诈猜数游戏”在两个玩家甲和乙之间进行, 游戏依赖于两个甲和乙都知道的正整数 \(k\) 和 \(n\).
游戏开始时甲先选定两个整数 \(x\) 和 \(N,1\leqslant x \leqslant N.\) 甲如实告诉乙 \(N\) 的值, 但对 \(x\) 守口如瓶. 乙现在试图通过如下方式的提问来获得关于 \(x\) 的信息: 每次提问, 乙任选一个由若干正整数组成的集合 \(S\) (可以重复使用之前提问中使用过的集合), 问甲”\(x\) 是否属于 \(S\)?”. 乙可以提任意数量的问题. 在乙每次提问之后, 甲必须对乙的提问立刻回答 “是” 或 “否”, 甲可以说谎话, 并且说谎的次数没有限制, 唯一的限制是甲在任意连续 \(k+1\) 次回答中至少有一次回答是真话.
在乙问完所有想问的问题之后, 乙必须指出一个至多包含 \(n\) 个正整数的集合 \(X\), 若 \(x\) 属于 \(X\), 则乙获胜; 否则甲获胜. 证明:
2012年7月11日, 星期三
4. 求所有的函数 \(f:\Bbb Z \rightarrow\Bbb Z\), 使得对所有满足 \(a+b+c=0\) 的整数 \( a,b,c\), 都有
\[ f(a)^2+f(b)^2+f(c)^2=2f(a)f(b)+2f(b)f(c)+2f(c)f(a). \]
(这里 \(\Bbb Z\) 表示整数集.)
5. 已知三角形 \( ABC \) 中, \(\angle BCA=90^\circ\), \(D\) 是过顶点 \(C\) 的高的垂足. 设 \(X\) 是线段 \(CD\) 内部的一点. \(K\) 是线段 \(AX\) 上一点, 使得 \(BK=BC\). \(L\) 是线段 \(BX\) 上一点, 使得 \(AL=AC\). 设 \(M\) 是 \(AL\) 与 \(BK\) 的交点.
证明 : \(MK=ML\).
6. 求所有的正整数 \(n,\) 使得存在非负整数 \(a_1,a_2,\dotsc,a_n,\) 满足
\[\frac1{2^{a_1}}+\frac1{2^{a_2}}+\dotsb+\frac1{2^{a_n}}=\frac1{3^{a_1}}+\frac2{3^{a_2}}+\dotsb+\frac n{3^{a_n}}= 1.\]
线段 \(AB\) 已给, 仅仅用圆规找其中点.
本题也很有意思, 尺规作图. 不过, 这不算神奇, 即便生锈圆规出马, 也就是把圆的半径固定, 例如 \(1\), 也一样可以完成任务.
作法
俺对尺规作图(Compass and straightedge constructions)一直有浓厚的兴趣. 这里有一个有趣的问题:
圆 \(\color{red}O\) 给定, 仅仅使用圆规找出圆心.
下面给出两种作图办法, 没有证明, 但不困难. 图来自网络, 但作图办法不是.
作法 \(1\)
作法 \(2\)
Zsigmondy’s theorem states that if \(a>b>0\) and \(n>1\) are positive integers, then
这就是如今人们常常谈到的 Zsigmondy 定理, \(2\) 实际上更为常见. Zsigmondy 当初其实允许 \(b<0\), 此时的例外当然要稍作修改, 比如 \(2\) 要增加 \(a=2,b=-1,n=3\).
此定理经常在群论(group theory)中大展拳脚, 在数论中当然也有很多应用.
这个定理的完整证明很难找到, 容易搜索到的是 \(b=1\) 时, 使用分圆多项式(cyclotomic polynomial)对\(2\)的证明.
在 Zsigmondy\(1892\)年的论文出现之前, Bang已经在\(1886\) 年证明了\(b=1\) 的情形, 即所谓的 Bang定理. 至于 Bang 当年的文章,是否包括了 Zsigmondy 定理的两种情形, 我无法得知, 因为没有看到原文. 后来, 又有不少人重新发现 Zsigmondy 定理或者 Bang 的结果, 也可能是某种特殊情况下的结论, 当然也有人给出新的证明. Birkhoff 和 Vandiver \(1904\) 年的论文 \([1]\) 用初等的办法证明了 \(2\). 这个证明, 稍后我们会详细谈到.
Carmichael \(1913\) 年的文章 \([2]\) 很值得一看, 他实际上证明了对 Lucas 序列(Lucas sequence)
\begin{equation}U_n=\frac{a^n-b^n}{a-b},\,V_n=a^n+b^n\end{equation}
而言, 结论一样成立. 尽管 \(a^n-b^n\) 与 \(U_n\) 确有许多相似, 但是毕竟差别还是有的, \(U_n\) 的本原质因数并不见得就是 \(a^n-b^n\) 的本原质因数. 例如, 当 \(a=5,\,b=2,\,n=3\) 时, \(U_3=\frac{5^3-2^3}{5-2}\) 的本原质因数 \(3\) 并不是 \(5^3-2^3\) 的本原质因数.
Artin 在研究线性群(linear group)的时候, 用初等办法建立了Zsigmondy定理的 \(2\), 并且允许 \(a,b\) 可以为负, 见 \([3]\).
继续下文之前, 先看几个简单的事实.
引理\(1\) 当 \(a,b\) 互质, 也即 \((a,b)=1\) 之时,
\begin{equation}(a^m-b^m,\,a^n-b^n)=a^{(m,n)}-b^{(m,n)}\end{equation}
成立, 这里 \(m,n\in\Bbb N^+.\)
\((2)\) 虽然简单, 却从未在哪本书上见过. 数论书上只有当 \(b=1\) 时的特殊情形, 所以这里算是一个推广. 至于证明, 可以归纳完成, 也可以选择 Bézout 恒等式(Bézout’s identity), 与 \(b=1\) 没有本质不同.
下面来探讨阶的性质.
设正整数 \(m>1,a\in\Bbb Z,(a,m)=1.\) 记 \(a\) 模 \(m\) 的阶为 \(\delta_m(a).\) 正整数 \(r\) 使得
\begin{equation}a^r\equiv-1\pmod m\end{equation}
成立.
引理\(2\) 设满足 \((3)\) 的最小正整数为 \(r\), 那么
引理\(3\) \(p\) 为质数, \(a,b,n\in\Bbb Z, n>0, p\nmid ab, p^\alpha\parallel n, p^\beta\parallel (a-b), \alpha,\beta\in\Bbb N.\) 如果在 \(p=2\) 时, \(\beta\geqslant2\); 在 \(p\geqslant3\) 时, \(\beta\geqslant1,\) 那么 \(p^{\alpha+\beta}\parallel (a^n-b^n).\)
证 设 \(a=b+tp^\beta, p\nmid t,\) 则
\[a^n-b^n=(b+tp^\beta)^n-b^n=\sum_{i=1}^n{n\choose i}b^{n-i}(tp^\beta)^i.\]
当 \(i\geqslant2\) 时, 由 \({n\choose i}(tp^\beta)^i=\dfrac ni{n-1\choose i-1}(tp^\beta)^i, (p^\beta)^{i-1}\geqslant3^{i-1}>i,\) 可得 \(p^{\alpha+\beta+1}|{n\choose i}b^{n-i}(tp^\beta)^i\); \(p^{\alpha+\beta}\parallel{n\choose1}b^{n-1}(tp^\beta).\) 综合起来, 我们的证明得以完成.
若 \(a^n\pm b^n\) 的某质因数不整除 \(a^k\pm b^k(k=1,\,2,\,\dotsc,\,n-1),\) 我们把这样的质因子叫做本原质因数. 也可以考察 \(a^n\pm b^n\) 的不是质数的因数, 这个时候, 要把整除不整除换成互质不互质: 若 \(a^n\pm b^n\) 的某因数与 \(a^k\pm b^k( k=1,\,2,\,\dotsc,\,n-1)\) 都互质, 我们把这样的因数叫做本原因数.
本原因数要求与 \(a^k\pm b^k, k<n\) 都互质, 所有的 \(n-1\) 个数 \(a\pm b, a^2\pm b^2,\dotsc,a^{n-1}\pm b^{n-1}\) 一个不落下. 能否把这个条件换成表面上更弱，实际上等价的条件, 使得利用这个定义的时候, 更加得心应手?
借助阶的性质以及引理 \(2\), 很容易就得到了第一个定理.
定理 \(1\) 记 \(n\) 的 \(d(n)\)个因数是 \(d_1=1,d_2,\dotsc,d_{d(n)}=n\). 如果 \(a^n\pm b^n\) 的一个因数与 \(a^k\pm b^k( k=d_1,d_2,\dotsc,d_{d(n)-1})\) 都互质, 那么这个因数是 \(a^n\pm b^n\) 的本原因数.
引理 \(1\) 也可以很方便的完成就 \(W_n\) 这种情况的证明, 这里
\begin{equation}W_n=a^n-b^n.\end{equation}
下一条性质出自 Euler.
定理\(2\) \(d\) 是 \(W_n\) 的本原因数, 则 \(d\equiv1\pmod n.\)
参考文献
In 1949, Leo Moser gave a proof of Bertrand’s postulate in the paper “A theorem of the distribution of primes”(American Mathematical Monthly,624-624,1949,vol56). Maybe this proof is the simplest one among all proofs of Bertrand’s postulate.
If \(2^\alpha<2n\leqslant 2^{\alpha+1}\), suppose there is no prime \(p\) with
\begin{equation}n<p<2n,\end{equation}
then
\begin{equation}{2n\choose n}\leqslant{2a_1\choose a_1}{2a_2\choose a_2}\dotsm{2\choose 1}\bigg({2a_k\choose a_k}{2a_{k+1}\choose a_{k+1}}\dotsm{2\choose 1}\bigg)^\alpha,\end{equation}
where \(a_1=\big[\frac{n+1}3\big], k=\big[\frac{\alpha+1}2\big]\), and \(a_i=\big[\frac{a_{i-1}+1}3\big]\), for \(i=2,\,3,\,\dotsc\,.\)
By \(1,\,2,\,3\) and \((1)\), every prime which appears on the left-hand side of \((2)\) appears also on the right; and those primes which appear with multiplicity greater than \(1\) on the left appear on the right with multiplicity at least \(2\alpha+1\), which by \(4\) is at least equal to the multiplicity with which they appear on the left.
On the other hand, It is obvious that
\begin{equation}2n>2a_1+2a_2+\dotsb+ 2+\alpha(2a_k+2a_{k+1}+\dotsb+2)\end{equation}
for \(n>2^{11}.\) Hence the inequality in \((2)\) should be reversed. So for \(n>2^{11}\), we have a contradiction which proves Bertrand’s postulate for these values of \(n\).
Fermat polygonal number theorem is a theorem in additive number theory, it is states that every positive integer is a sum of at most \(n n\)-gonal numbers.
Let \(n\geq 3\), the polygonal numbers of order \(n\) are the integers
\begin{equation}p_n(k)=\frac{n-2}{2}(k^2-k)+k\end{equation}
for \(k=0,1,2,\dotsc.\)