IMO2009试题

石崇的BOSS

4题还是不是很简单吧，毕竟是IMO试题呀

lulijie

来自黄志毅的解答：
------------------------------------------------------
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 步用归纳假设就行了。

lulijie

发现第6题的证明思路、方法与下题的基本相似。
有一个字符串S，由m种字符组成，若这个字符串的任何长度为n的子字符串都不重复，那么这个字符串S就称为m*n型的非重字符串，
    求证：m*n型的非重字符串的最大长度为m^n+n-1 。
都是采用数学归纳法，采取构造的方法，若初始构造不符合，重新进行调整使之符合。
看来很多题目都有共通之处。

石崇的BOSS

请问黄志毅是谁？是你吗？

lulijie

非也，非也。
听网上说他是清华大学计算机系的。

lulijie

据说去年国际奥赛的满分得主韦东奕今年参赛又获得了满分。

superacid

成绩出来了？？？

lulijie

我是网上看到了，有人说韦东奕做对6道题，其他五人都是做对5道，最后一道没做出。

superacid

黄志毅是IMO2004金牌吧！

石崇的BOSS

成绩出来了，韦东奕满分，中国选手最低分35分，中国获得6枚金牌，获团体第一