第50届IMO

[alvin]

第50届IMO
2009年7月10至22日在德国的不莱梅进行。
代表中国参赛的6名队员全部获得金牌，蝉联团体总分第一名。
第一天
1.
n 是一个正整数，设 a[1],a[2],...,a[k] (k≥2) 是 k 个不同的属于 {1,2,...,n} 的正整数，满足 n 整除 a(a[i+1]-1) 对任意 i=1,2,...,k-1 成立。
证明：n 不整除 a[k](a[1]-1)。
2.
设三角形 ABC 的外心为 O 。点 P,Q 分别是线段 CA,AB 上的点。设 K,L,M 分别是线段 BP,CQ,PQ 的中点。
如果直线 PQ 与 三角形 KLM 的外接圆相切，证明 OP=OQ 。
3.
设 s[1],s[2],s[3],...... 是一个严格单调递增的正整数数列，满足其子数列 s[s[1]],s[s[2]],s[s[3]],...... 和 s[s[1]+1],s[s[2]+1],s[s[3]+1],...... 都是等差数列。
证明数列s[1],s[2],s[3],......也是一个等差数列。

第二天
4.
在三角形 ABC 中， AB=AC ， ∠CAB 和 ∠CBA 的角平分线分别交 BC,AC 于点 D,E 。
设 K 是三角形 ACD 的内心， ∠BEK=45° ，求 ∠BAC 。
5.
求所有正整数集到正整数集的映射 f ，满足对任意正整数 a,b ，
存在一个非退化的三角形其三边长为 a,f(b),f(b+f(a)-1) 。
6.
设 a[1],...,a[n] 是 n 个互不相同的正整数， M 是一个不包含 s=a[1]+a[2]+...+a[n] 的 n-1 元正整数集。
一只蚱蜢在实轴上跳跃，它从 0 点开始，向右跳跃 n 次，其长度为 a[1],a[2],...,a[n] 的一个排列。
证明：存在一种跳法，使得蚱蜢不落在任何一个 M 中的点上。

[alvin]

1. 证明：反证法，反设 n|a[k](a[1]-1)
引理：n|a(b-1) n|b(c-1) => n|ab(c-1)-(c-1)a(b-1)=a(c-1)
因此，只要考虑k=2的情形就足够了，n|a[1](a[2]-1) n|a[2](a[1]-1) =>n|a[1](a[2]-1)-a[2](a[1]-1)=a[1]-a[2]，这和a[1]，a[2]是不同的属于 {1,2,...,n}的正整数矛盾。
------------------------------------------------------------------------
2. 证明：延长 OP 交 ABC 外接圆于 P1，P2，延长 OQ 交 ABC 外接圆于 Q1，Q2，不失一般性可以假设 P1，Q1 分别是离 P，Q 较近的交点。
PQ于KLM外接圆相切 => 角LKM = 角LMP = 角QPA 和 角KLM = 角KMQ = 角PQA => APQ 与MKL相似 => AP/AQ = MK/ML = QB/PC => AP*PC = AQ*BQ。由于 PP1*PP2 =AP*PC 和 QQ1*QQ2 = AQ*QB，所以 PP1*PP2 = QQ1*QQ2。而 PP1+PP2 与 QQ1+QQ2 都等于ABC 外接圆直径，于是 PP1 = QQ1，从而 OP = OQ
-----------------------------------------------------------------------
3. 证明：首先 s[k+1]-s[k] 是有界的，有下届由 s[k] 严格单调递增显然，加入没有上界，那么 s[s[k+1]]-s[s[k]] >= s[k+1]-s[k] 也无上界，和 s[s[k]] 是等差数列矛盾。
另一方面，s[s[k]] 和 s[s[k]+1]这两个等差数列的公差相等，否则如果前者公差较大，当k足够大可以推出 s[s[k] >s[s[k]+1]，如果后者公差较大，则可以推出 s[s[k]+1] >s[s[k+1]]，与s[k]的严格单调性矛盾。因此，我们进一步可以得到 s[s[k]+1]-s[s[k]] 是常数。
现在假设 s[m+1]-s[m] = a 和 s[n+1]-s[n] = b 分别是 s[k+1]-s[k] 的最大最小值，那么a >= b 而且
s[s[m+1]]-s[s[m]]= (s[s[m+1]] -s[s[m+1]-1]) + (s[s[m+1]-1] - s[s[m+1]-2]) + ... +(s[s[m]+1] - s[s[m]]) >= (a-1)b + (s[s[m]+1] - s[s[m]])
s[s[n+1]]-s[s[n]]= (s[s[n+1]] -s[s[n+1]-1]) + (s[s[n+1]-1] - s[s[n+1]-2]) + ... +(s[s[n]+1] - s[s[n]]) <= (b-1)a + (s[s[m]+1] - s[s[m]])
由s[s[m+1]]-s[s[m]]= s[s[n+1]]-s[s[n]] 和 (s[s[m]+1] - s[s[m]]) = (s[s[n]+1] - s[s[n]])我们可以推出 (b-1)a >= (a-1)b，从而 b >= a，这说明 a = b，也就是s[k]是等差数列
--------------------------------------------------
4. 证明：假如 BE 与 CA 垂直，那么容易得出 ABC 是等边三角形，从而 角CAB = 60度。
假如 BE 与 CA不垂直，那么假设 ABC 的内心为 I（BE 与 AD 的交点），作 IF 垂直于AC。可以得到 F 与 E不重合，而由对称性可知 角IFK = 角IDK = 45度，从而 角IFK = 角IEK，因此 I, K, F, E 四点共圆，因此CK*CI = CF*CE = CD*CE。这等价于 CK/CD = CE/CI。而 CI是角平分线，因此 三角形CKD 与 三角形 CEI相似，所以 角CIE = 角 CDK = 45 度。从而可以得出 三角形ABC 的两个底角等于 45度，而 角CAB 等于90度。
-----------------------------------------------------
5. 证明：存在非退化的三角形三边长为 a, f(b), 和 f(b+f(a)-1) 等价于
a+f(b) >= f(b+f(a)-1)+1 ... (1)
a+f(b+f(a)-1) >= f(b)+1 ... (2)
f(b)+f(b+f(a)-1) >= a+1 ... (3)
在 (1) (2) 中让 a = 1 可以得到 1+f(b) >= f(b+f(1)-1)+1 和 f(b+f(1)-1)+1 >= 1+f(b)，也就是说
f(b) = f(b+f(1)-1) ... (4)
假如 f(1) > 1，那么从这个条件我们可以得出f(n) 是有界的，上界为 f(1), f(2), ... f(f(1)-1) 中的最大值，在 (3) 中让 a 足够大可以得出矛盾。因此f(1)=1。
接下来让 b = 1，和前面类似，从 (1) (3) 可以得到 f(f(a)) = a。进一步，从这个条件我们可以得出 f(n) 是双射以及对于任意 n > 1 都有 f(n) != 1。
由(1) 可以推出 k(a-1)+f(b) >= (k-1)(a-1)+f(b+f(a)-1) >= ... >=f(b+k(f(a)-1))，因此，我们可以推出 对于任意的 n <= (k+1)(f(a)-1)，都有 f(n) <=max{f(1), f(2), ... , f(f(a)-1)} + k(a-1)，假如 f(a) > a的话，会导致k足够大的时候像集比原像集小，和 f 是双射矛盾。从 f(a) <= a 和 f 是双射可以推出 f(a) = a。
--------------------------------------------------------
6. 证明：为了方便我们把M里的点称为陷阱。用归纳法，n = 1, 2的时候显然。
下面假设命题对任意 n < k 成立，我们考虑 n = k 的情形。先考虑所有步长从小到大排列，不妨设 a1 < a2 < ... < an。从原点开始往正方向数，考虑第一次所经过的陷阱个数超过步数的那一步，不妨设为第 i 步。
假如 i = n，那么考虑两种情况，假如 s-an 不在 M 里，那么对于前 n-1 步用归纳假设即可。否则，除了 s-an 以外，还有 n-2陷阱，我们考虑把a1, a2, ... , an-1 中的某一个放在最后一步，而把 an 放在倒数第二步。由于 s-an-aj不可能是大于等于 s-an 的数，而 s-aj 不可能是小于等于 s-an 的数，我们可以得出存在一个 aj，使得 s-aj 和s-an-aj 都不是陷阱。而从我们对于 i 的选取方法我们知道 [s-an, s] 这个区间里至少有两个陷阱，于是这时候再对前 n-2 步在[0, s-an-aj] 区间里用归纳假设即可。
i = 1的情况也是类似的。
下面假设 i < n，我们考虑前 i-1个陷阱，和前面的讨论类似，存在前 i 步的一种排列，使得避开了前 i-1 个陷阱，而且最后两步至少覆盖了这 i-1个陷阱中的两个。因此我们可以知道除了第 i-1 步和第 i 步之外，其他的 i-2 步都不会踩到后面 n-i 个陷阱。
假如第 i-1 步没有踩到陷阱，那么我们可以对最后的 n-i+1 步（也就是包括第 i 步）利用归纳假设，由于调整后第 i 步的步长不可能变小，所以调整后同样不会踩到前面的 i-1 个陷阱。
假如第 i-1 步踩到了陷阱，那么说明前 i-1 个陷阱都在第 i-1 步之前。因此，我们不妨假设第 i-1 步比第 i步长，否则我们可以交换第 i 步和第 i-1 步，这样不影响前面 i-1 个陷阱，而第 i-1 步最坏情况下也只是和原来一样踩到后 n-i个陷阱中的某个。这样一来第 i 步是后 n-i+2 步中最短的，而第 i-2 步次短，由于第 i-1步踩到了陷阱，我们可以和前面类似的讨论，把后n-i-1 个步长中的某个和第 i-1 步交换，使得第 i-1 步不会踩到陷阱，由于原来的 i-1步步长次短，这样调整不会影响前 i-1个陷阱。这时我们再对后面的 n-i 步用归纳假设就行了。

[goon]

似乎数论的题少了，几何题目多了？ 呵呵

[此帖已删]

不错