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.\]
- B chooses \(S_1\) repeatedly. If B get an answer of no \(k+1\) times, then B can exclude the number \(100\ldots0\). Otherwise, A will eventually say yes.
- If A last said yes, B then asks \(S_2,S_3,\dotsc,S_{k+1}\), and guarantees a win.
\[(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\), 甲的回答会出现两种情况:
- 连续 \(k+1\) 次回答 “否”, 则 \(100\ldots0\) 可以排除;
- 在至多 \(k+1\) 次回答中, 一旦出现”是”, 乙接下来的 \(k\) 次提问, 依次选取 \(S_2,S_3,\dotsc,S_{k+1}\), 就取得胜利. 事实上, 若甲最后的 \(k\) 次回答都是”是”, 则 \(x\in T\); 若甲最后的 \(k\) 次回答有一些是”否”, 则 \(x\) 绝对不可能是 \(\overline{a_1a_2\ldots a_{k+1}}\), 这里 \(a_1=0\), \(a_i=0\) 还是 \(1\) 取决于甲对 \(S_i\) 的答案: 若甲的回答是”是”, \(a_i=0\), 否则 \(a_i=1( i=2,3,\dotsc,k+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\) 条性质:
- 令 \(a=b=c=0\), 得 \(f(0)=0\);
- 令 \(b=-a,c=0\), 得 \(f(a)=f(-a)\). 于是只需讨论当 \(a\) 为正整数时的 \(f(a)\) 就行了.
- 若有 \(a\in\Bbb Z\), 使得 \(f(a)=0\), 那么, 对于任意整数 \(b\), 由 \(a+b+(-a-b)=0\) 得 \(f(a+b)=f(b).\)
根据性质 \(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\). 这里给出的”两种”证法, 实质上没有任何差别.