魔方吧·中文魔方俱乐部

标题: IMO2009试题 [打印本页]

作者: superacid 时间: 2009-7-16 08:10:35 标题: IMO2009试题

第一天
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 中的点上。

毕竟是IMO试题，有相当的难度，只是发上来娱乐一下，做不来就算了。
中文(简体)版试题出炉了！

中国队以团体总分221分获得团体冠军，韦东奕同学获得42分满分！

[ 本帖最后由 superacid 于 2009-7-20 07:57 编辑 ]

附件: [IMO2009] IMO2009.pdf (2009-7-18 22:59:06, 169.7 KB) / 下载次数 22
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NjAwMzN8NmEwZjYxYmN8MTcxNzc2NTczN3wwfDA%3D

作者: ZJY 时间: 2009-7-16 08:24:40

这个是不是国际的数学奥林匹克竞赛试题？好有难度哦

作者: 今夜微凉 时间: 2009-7-16 08:27:29

哇~难题~先看看吧~一天以后如果还是没进展我就放弃~

作者: 小波 时间: 2009-7-16 09:11:19

不是说了不发难题嘛，还发这种…………

作者: 溪风 时间: 2009-7-16 09:34:19

早十年可能会..........晕

作者: superacid 时间: 2009-7-16 11:55:25 标题: 回复 4# 的帖子

这题目是放着看的，不是用来拼命做的，主要是宣传一下IMO。

作者: 123wyx 时间: 2009-7-16 14:18:33

支持LZ宣传IMO
我先试试平几，那俩题就算了

作者: Osullivan 时间: 2009-7-16 21:13:38

IMO=I MUST （BE）OVER！
HAHA ~~~~~~~~~

作者: 铯_猪哥恐鸣 时间: 2009-7-16 21:18:10

= =我是不是也来宣传几道IPHO的题目。。。

作者: 123wyx 时间: 2009-7-16 21:31:55

个人功力相当不够啊

感觉今年冬令营的题出得还不错，尤其是平几，活而不难，挺有意思的

作者: 炀燚 时间: 2009-7-16 21:34:19

这东西丢下快一年了。
往事不堪回首啊。。。。。。。。。。。

作者: xh176233756 时间: 2009-7-16 21:46:45

lz是国家队的？全国就5个吧？

作者: superacid 时间: 2009-7-16 22:04:36 标题: 回复 12# 的帖子

我如果是国家队的怎么现在发帖聊天？
另外IMO每支队伍6个人。

作者: superacid 时间: 2009-7-16 22:05:49

原帖由 铯_猪哥恐鸣 于 2009-7-16 21:18 发表
= =我是不是也来宣传几道IPHO的题目。。。

你先搞一个物理区再说。

作者: 石崇的BOSS 时间: 2009-7-17 10:47:10

如果有时间，请楼主把后3道题也发上来吧，好让大家开开眼界

作者: superacid 时间: 2009-7-17 12:04:22 标题: 回复 15# 的帖子

不是发了嘛。

作者: zhang197695 时间: 2009-7-17 12:08:06

能力有限，实在不能作答，
不过最有希望作出那道几何题。

作者: 石崇的BOSS 时间: 2009-7-17 12:16:19 标题: 回复 16# 的帖子

怎么就只有3道？不是有6道吗？看到了，谢谢！

作者: 石崇的BOSS 时间: 2009-7-17 13:17:42

先解决简单的送分题，我估计第4题是怕有些国家的选手得0分而出的送分题
易证△EFK≌△DFK,所以∠EFK=∠KFD=∠AFE=60°，可得△ABC是等边三角形，故∠BAC=60°.

作者: superacid 时间: 2009-7-17 21:39:25

根据以往惯例，1,4两题非常简单；2,5中等；3,6非常难。

作者: 石崇的BOSS 时间: 2009-7-18 08:24:14

4题还是不是很简单吧，毕竟是IMO试题呀
QQ截图未命名.jpg

附件: QQ截图未命名.jpg (2009-7-18 08:24:14, 60.14 KB) / 下载次数 18
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTk5NjV8ZjZhNGIwM2Z8MTcxNzc2NTczN3wwfDA%3D

附件: QQ截图未命名1.jpg (2009-7-18 08:24:14, 7.54 KB) / 下载次数 10
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTk5NjZ8N2ZkMTJjNGR8MTcxNzc2NTczN3wwfDA%3D

作者: lulijie 时间: 2009-7-18 20:49:41

来自黄志毅的解答：
------------------------------------------------------
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 时间: 2009-7-18 21:45:33

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

作者: 石崇的BOSS 时间: 2009-7-18 21:51:28 标题: 回复 22# 的帖子

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

作者: lulijie 时间: 2009-7-18 21:59:03

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

作者: lulijie 时间: 2009-7-18 22:13:06

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

作者: superacid 时间: 2009-7-18 22:56:19 标题: 回复 26# 的帖子

成绩出来了？？？

作者: lulijie 时间: 2009-7-18 22:59:25

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

作者: superacid 时间: 2009-7-18 23:05:05

黄志毅是IMO2004金牌吧！

作者: 石崇的BOSS 时间: 2009-7-19 22:20:18

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

作者: 123wyx 时间: 2009-7-20 17:16:53

这届中国队很强啊
日本队团体总分就比中国队低9分，比俄罗斯还高，确实出乎意料，看来是准备非常充分。
还有一些国家的代表队这次成绩也很好

[ 本帖最后由 123wyx 于 2009-7-20 17:26 编辑 ]

作者: sokoban 时间: 2009-7-27 00:43:42

IMO 的官方网站信息很全啊，历年获奖详情和题目都找得到：
http://www.imo-official.org/

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)