新浪博客

第55届(2014)国际数学奥林匹克试题及其解答（1）

2014-07-08 20:46阅读：

http://blog.sina.cn/dpool/blog/u/1276195074

第55届(2014)国际数学奥林匹克试题及其解答（1）
第55届（2014）国际数学奥林匹克，7月3日-13日，南非，开普敦
The 55th International Mathematical Olympiad (IMO) will be held in Cape Town, South Africa, from 3 to 13 July 2014.
The IMO is a problem-solving contest for high school students, held in a different country in July every year. The first IMO was held in Romania in 1959, with seven countries taking part. Today, more than 100 countries take part, representing over 90% of the world's population. The IMO is the oldest, biggest and most prestigious of all the international science Olympiads.

The 2014 IMO is presented by the South African Mathematics Foundation and will take place at the University of Cape Town. The event is endorsed by the Department of Basic Education and the Department of Science and Technology of the Republic of South Africa.
第55届(2014)国际数学奥林匹克试题及其解答（1）

第55届国际数学奥利匹克（International Mathematical Olympiad，简称IMO ）将于2014年7月3日至13日在南非首都开普敦举行。
中国国家队参赛队员名单（共6人）：
上海中学，高继扬
济南历城二中，齐仁睿
武钢三中，黄一山
湖南师大附中，谌澜天
深圳中学，周韫坤
东北师大附中，浦鸿铭
领队：姚一隽，复旦大学
副领队：李秋生，人大附中
观察员A：冷岗松，上海大学
观察员B：张思汇，上海理工大学
http://www.imo2014.org.za/?AspxAutoDetectCookieSupport=1
数学竞赛俱乐部 2014年IMO第一天试题 第55届(2014)国际数学奥林匹克试题及其解答（1） 第55届(2014)国际数学奥林匹克试题及其解答（1）
第55届(2014)国际数学奥林匹克试题及其解答（1）
Problem 1. Let a_0 < a_1 < a_2 \ldots be an infinite sequence of positive integers. Prove that there exists a unique integer n\geq 1 such that
a_n < \frac{a_0+a_1+a_2+\cdots+a_n}{n} \leq a_{n+1}.


【A】Define the function f: \mathbb{Z}^+ \to \mathbb{Z} by f(k) = a_0 + a_1 + \ldots + a_{k-1} - (k-1)a_k. The condition a_n < \dfrac{a_0 + a_1 + \ldots + a_n}{n} simplifies to 0 < a_0 + a_1 + \ldots + (n-1)a_n = f(n), and the condition \dfrac{a_0 + a_1 + \ldots + a_n}{n} \le a_{n+1} simplifies to a_0 + a_1 + \ldots + a_n - na_{n+1} = f(n+1) \le 0. Thus, we want to show that there is a unique positive integer n so that f(n+1) \le 0 < f(n). We claim that f is strictly decreasing over the positive integers: we have \begin{aligned} &\quad f(k+1) - f(k) \\ &= [a_0 + a_1 + \ldots + a_{k-1} + a_k - ka_{k+1}] - [a_0 + a_1 + \ldots + a_... since a_k < a_{k+1} for all k . Thus, f is strictly decreasing, as claimed. Further, since f(k) is always an integer, we must have f(k+1) \le f(k) - 1 for all k .
Note that f(1) = a_0 . Then, we have f(2) \le f(1) - 1 = a_0 - 1 , f(3) \le f(2) - 1 \le a_0 - 2 , and by a straightforward induction argument, f(k) \le a_0 - (k-1) for all k \in \mathbb{Z}^+. Then f(a_0 + 1) \le a_0 - (a_0 + 1 - 1) = 0, so there is a positive integer m so that f(m) \le 0. Let m_0 be the least positive integer m for which f(m) \le 0 . Since f is strictly decreasing, f(k) \le 0 if and only if k \ge m_0 . Then, we must have f(m_0 - 1) > 0 , so f(m_0) \le 0 < f(m_0 - 1). Thus, n = m_0 - 1 is an integer satisfying the given conditions. Further, there cannot be another integer m_1 eq m_0 satisfying the given conditions. If there was such an m_1 , then f(m_1) \le 0 , so m_1 > m_0 . However, then m_1 - 1 \ge m_0, so f(m_1 - 1) \le 0 , a contradiction. Thus there is a unique positive n satisfying the given conditions. \square
【B】 Observe that the second inequality for a given n is equivalent to the opposite of the first inequality for n + 1 . For n = 1 the first inequality is satisfied, and if the second isn't, then, by what has been just said, the first inequality is satisfied for n = 2 . If no n as wanted exists, then, by continuing in this manner one sees that for any n , the first inequality must always be satisfied. However, a_n \geq \frac{a_1 + a_2 + ... + a_n}{n} + \frac{(n -1) + (n - 2) + ... + 1}{n},
which is larger than \frac{a_0 + a_1 + a_2 + ... + a_n}{n} for n large enough. Hence there must exist at least one n as wanted. For this n we have, in particular (from the second inequality)
na_{n+1} \geq a_0 + a_1 + ... + a_n. Were there an index m > n for which the first inequality held again, that is,
(m-1)a_m < a_0 + a_1 + ... + a_{m-1}, then one can apply the previous inequality for the first n +1 terms of the right hand side and notice that each of the remaining ones is smaller than a_m to obtain a contradiction.
【C】 We rewrite the condition as
na_n < \displaystyle \sum_{i=0}^{n} a_i < na_{n+1} \implies \begin{cases} \displaystyle \sum_{i=1}^{n} (a_n - a_i) <...
Note that for all n,
\left( \displaystyle \sum_{i=1}^{n+1} (a_{n+1} - a_i) \right) - \left( \displaystyle \sum_{i=1}^{n} (a_n - a_i) \right) = n a...
which implies \displaystyle \sum_{i=1}^{n} \left( a_n - a_i \right) is monotonically increasing. Obviously \displaystyle \sum_{i=1}^{n} (a_n-a_i) is unbounded from above. At n=1, it equals zero. Now let n be the largest integer such that \displaystyle \sum_{i=1}^{n} \left( a_n - a_i \right) <a_0. We have that a_{n+1} \geq a_0 by our hypothesis, so this is our desired n which is clearly unique. \blacksquare
【D】 Suppose that for every n we have a_{n+1} < \frac{a_0+...+a_n}{n}
for n=1 , a_2 < a_0+a_1 . For n=2 , 2a_3 <a_0+a_1+a_2<2(a_0+a_1) so a_3<a_0+a_1 and by induction a_n<a_0+a_1 which it is a contradiction because we have an infinite sequence of positive integer and bounded !
Let n_0 be an integer such that a_{n_0+1} \geq \frac{a_0+...+a_{n_0}}{n_0}
we have a_1<a_0+a_1 if a_0+a_1 \leq a_2 we get the existence, if not then a_2 <\frac{a_0+a_1+a_2}{2} and again if \frac{a_0+a_1+a_2}{2} \leq a_3 we have done and if not we have a_3 <\frac{a_0+a_1+a_2+a_3}{3} and we continue until reaching the integer n_0 for which we have
a_{n_0} < \frac{a_0+...+a_{n_0}}{n_0} \leq a_{n_0+1}
The uniqueness is obvious because if \frac{a_0+...+a_n}{n} \leq a_{n+1} then \frac{a_0+...+a_n+a_{n+1}}{n+1} \leq a_{n+1} and since the sequence is strictly increasing we show easily that for any m>n+1 we have \frac{a_0+...+a_m}{m} < a_m so the property can't be satisfied for m> n_0
【E】Key Lemma:If S_i=S_{i-1}+u_i is a cumulative sequence with S_0=0 and u_i>0 for all i , then for every positive integer k , there is a unique positive integer n so that, S_n < k\leq S_{n+1} .
Proof:
Almost obvious. But if you still need one, take n to be the smallest positive integer so that S_{n+1}\geq k . Then, we must have S_{n}<k . If not, it would contradict the minimality of n .
Now, all we have to do is find an appropriate \{u\} and \{S\} . Take, S_n=\sum_{i=1}^na_i , which is clearly increasing. We need, S_n+a_0>na_n and S_{n}+a_0\leq na_{n+1} . Clearly this want us to consider the sequence T_n=na_{n+1}-S_{n} . It can be written as T_n=\sum_{i=1}^nc_i=T_{i-1}+c_i where c_i=a_{n+1}-a_i . Obviously, c_i>0 for all i . Thus, \{T\} is a cumulative sequence, and therefore, such a n always exists no matter what the choice of a_0 is as long as it is a positive integer.
Remark: Something similar can not be said if it is replaced by non-negative integers. Because then the sequence \{S\} would not be strictly increasing. Also, the crucial idea seems kind of trivial to me if someone has ever done 'Binary Search' or something like that in an algorithm course/in CSE, whatever.
【F】 Denote b_n=(a_n-a_{n-1})+\dots+(a_n-a_1) . Then b_1=0 , b_n increases and we are searching for n such that b_n<a_0\leq b_{n+1} . It clearly exists and is unique.
Of course, the fact the sequence (a_n)_{n\geq 1} has integer terms is irrelevant; all that matters is that the sequence (b_n)_{n\geq 1} is unbounded.



Problem 2. Let n \ge 2 be an integer. Consider an n \times n chessboard consisting of n^2 unit squares. A configuration of n rooks on this board is peaceful if every row and every column contains exactly one rook. Find the greatest positive integer k such that, for each peaceful configuration of n rooks, there is a k \times k square which does not contain a rook on any of its k^2 unit squares.

【A】 will show that k = \lceil \sqrt{n} \rceil - 1 .
First we show the upper bound. Take some m^2 \times m^2 square for m \in \mathbb{Z} . The rooks will be in row r , column \lfloor r/m \rfloor + m(r - m\lfloor r/m \rfloor) where r ranges from 0 to m^2-1 and the row/column numbers are taken modulo m^2 . It's hard to visualize but I'm bad at drawing :(
No m \times m subsquares can be found in this arrangement, so k \leq m - 1 .
When n is not a perfect square, taking m^2 such that m^2 > n > (m-1)^2 gives the same upper bound.
Now we show the lower bound. Let p = \lceil \sqrt{n} \rceil Consider some column of p adjacent p \times p subsquares. Only p rooks can be placed in this column, so there either exists an empty subsquare or every subsquare has a rook in it. In the former case, we can find an empty p \times p subsquare. In the latter case, since rooks cannot share rows or columns, one rook must be in the corner of its p \times p subsquare, so we can find an empty p-1 \times p-1 subsquare. Therefore, a p-1 \times p-1 subsquare can be found regardless of configuration and we have the lower bound as well.
【B】Let this maximum be f(n) . It's obvious that f(n) is nondecreasing.
For n=p^2 , we have f(n)<p (I omit my counterexample for redundancy's sake). Now we show that there exists a p-1\times p-1 square in the board. Assume for the sake of contradiction that in each p-1\times p-1 square there is at least one rook. There are (p(p-1)+2)^2 such squares, counting each rook at most (p-1)^2 times. Therefore, there must be at least \frac{(p(p-1)+2)^2}{(p-1)^2}=\left(p+\frac2{p-1}\right)^2>p^2=n rooks, a contradiction. Therefore, f(p^2)=p-1
For n=p^2+1 , we may use the same logic. Since f((p+1)^2)=p , we have f(p^2+1)\le p ; we assert that f(p^2+1)=p . Again, assume for the sake of contradiction that in each p\times p square there is at least one rook. Then there are p^2+2 disjoint sets of squares and p^2+1 rooks, so the pigeonhole principle tells us that there exists an unoccupied square. Therefore, f(p^2+1)=p .
Since f(p^2+1)=f((p+1)^2)=p and f(n) is nondecreasing, we have f(n)=p for all p^2+1\le n\le(p+1)^2 . Therefore, f(n)=\left\lfloor\sqrt{n-1}\right\rfloor .
【C】 Let n=k^2+r where 0< r \le 2k+1 .
We will prove this k will be that one, we want.
Look to a rook in the uppermost row.
Select k consecutive columns which contain the previous rook in the first row.
Now we can divide these columns in k k*k squares and a k*r block above.
Because there are only k-1 rooks yet to place in the k k*k squares, there is such a square empty.
Hence our searched k is at least this value.
Now we prove there can always be a peaceful configuration with equality:
We uses the coordinates of the latices from (0,0) to (n-1,n-1)
Place a rook in the origin and in each next column we place a rook k+1 higher than the column before until we can't do it anymore.
Now, in the next column we place a rook in row with index 1 ( y=1 ) and again going to the right by placing a rook k higher each time.
Each time we have to finish as we can't go k higher, we place it in the smallest row yet attainable and continue the same process.
It is easy to see we made a peaceful configuration.
Assume there is a (k+1)*(k+1) square without a rook.
Looking to the full k+1 columns ( a (k+1)*n block) of the square, we see except once the difference between consecutive rooks is k+1 and hence there isn't a gap of more than k+1 .
As there is a rook in the uppermost and lowermost (k+1)*(k+1) square, the assumption leads to a contradiction.
【D】 If m^2<n\leq (m+1)^2 , then k=m . In other words, k=[\sqrt{n-1}] .
If n=m^2+1 , then without loss of generality there is no rook in right lower corner. We take lower row, right column and m^2 squares m\times m disjoint from them and from each other. Totally m^2+2 sets, by pigeonhole principle one of them does not contain a rook, and it is a square. If n>m^2+1 , remove last row and last column, add a rook if necessary and reduce the problem to n-1 .
If n=m^2 , then enumerate rows and columns from 0 to m^2-1 and put rooks with coordinates (ma+b,mb+a) for 0\leq a,b\leq m-1 . Straightforward check shows that there is no empty m\times m square. Example for n-1 without empty m\times m square is obtained from the example for m\times m as above: remove last row and last column and add rook if necessary.
【E】For n=q^2 the largest such square has side length k(n)\le q for the following configuration:
Place rooks on the following squares:
(1,1) , (2,q+1) , (3,2q+1) , \ldots , (q,(q-1)q+1)
(q+1,2) , (q+2,q+2) , \ldots , (2q,(q-1)q+2)
\ldots
\ldots
((q-1)q+1,q) , ((q-1)q+2,2q) , \ldots (q-1)q+q,q^2)

Problem 3. Convex quadrilateral ABCD has \angle ABC = \angle CDA = 90^{\circ} . Point H is the foot of the perpendicular from A to BD . Points S and T lie on sides AB and AD , respectively, such that H lies inside triangle SCT and \angle CHS - \angle CSB = 90^{\circ}, \quad \angle THC - \angle DTC = 90^{\circ}. Prove that line BD is tangent to the circumcircle of triangle TSH .

【A】Is this a request for more detail? Notice that r^2 - x^2 = h^2 - 2xh \cdot \frac{d}{2R} = (2R)^2 - 2bx where h = AH = \frac{bd}{2R} , whence x = \frac{(2R)^2-h^2}{2b - 2h \cdot \frac{d}{2R}}. Moreover, \frac{1}{2} \left( \frac{r^2}{x^2}-1 \right) = \frac{1}{x} \left( \frac 2x R^2 - b \right).
Now, if we plug in the x in the right-hand side of the above, we obtain
\frac{2b-2h \cdot \frac{d}{2R}}{4R^2-h^2} \left( \frac{2b-2h \cdot \frac{d}{2R}}{4R^2-h^2} \cdot 2R^2 - b\right) = \frac{2h}{...
Pulling out a factor of -2Rh from the rightmost term, we get something that is symmetric in b and d , as required.
【B】Problem. Convex quadrilateral ABCD is cyclic. Point P is a point inside triangle ADB such that \angle PAD=\angle CAB . Points S and T lie on sides AB and AD , respectively, such that P lies inside triangle SCT and \angle CPS - \angle CSB = \angle TPC - \angle DTC = 90^{\circ} . Prove that circumcenter of triangle PST lie on AP .
Solution (It is from idea of leader).
Let M,N be reflection of C through AB,AD . We have CPSM and CPTN are cyclic with center X,Y . We must prove that perpendicular bisector of PS,PT and PA are concurrent. Apply Menelaus theorem for triangle PST,PTA we must prove that \frac{XS}{XA}=\frac{YT}{YA} or \frac{AX}{AY}=\frac{PX}{PY}=\frac{CX}{CY}. Let XY cuts perpendicular bisector of PA at Q and XY cuts AC at R . We see \angle XAQ=\angle PAQ-\angle PAX=(90^\circ-\frac{\angle AQP}{2})-\angle CAD=90^\circ-\angle ACP-\angle CAD=\angle YRC-\angle ...
From this we have QA is tangent of (AXY) but Q is circumcenter of triangle APC so (APC) is Apollonious circle for segment XY . We are done.
【C】Let O_1 and O_2 be the centers of the circles. We need to prove that \frac{AO_2}{O_2H}=\frac{AO_1}{O_1H}. Let N be he midpoint of HC . Then \angle{CNO_2}=\angle{CDA}=\angle{CNO_1}=\angle{CBA}=90^\circ . Thenquadrilaterals O_1BNC and O_2DCN are inscribed. Since that \frac{O_2C}{CO_1}=\frac{\sin{O_2O_1C}}{\sin{O_1O_2C}}=\frac{\sin{NBC}}{\sin{NDC}} . Also \frac{AO_2}{AO_1}=\frac{\sin{AO_1O_2}}{\sin{AO_2O_1}}=\frac{\sin{BCN}}{\sin{DCN}} . As O_2C=O_2H, O_1C=HO_1 it is sufficient to prove that \frac{\sin{NBC}}{\sin{NDC}}=\frac{\sin{BCN}}{\sin{DCN}} or \frac{\sin{NBC}}{\sin{BCN}}=\frac{\sin{NDC}}{DCN} . Finally \frac{\sin{NBC}}{\sin{BCN}}=\frac{NC}{BN}=\frac{NC}{DN}=\frac{\sin{NDC}}{DCN} ( BN=DN because NE \parallel AH ( HN=NC, AE=EC ) so NE \perp BD where E is the center of the circumcircle of ABC .
What do you think about problem? As for me it was really surprisingly to see geometry with angle equalities and without many circles on the 3rd position. And i hope leaders wrote ' H lies inside triangle CST ' in bold - i waste a lot of time finding what is wrong
【D】Reflect C about B and D to get E,F , then ESHC and FTHC are cyclic (this gets rid of the ugly angle condition and makes the diagram better since now A is the circumcenter of ECF ). Furthermore, ES=SC and FT=TC .
Now let M be the midpoint of EF and note that MAH is a straight line and perpendicular to EF . Thus EH=HF . Simple angle chasing gives \angle SHT=\angle MHF=\angle MHE , and HS is the external angle bisector of \angle EHC (same for the other side), useful information for \triangle SHT .
But now what? There is no way to find the other 2 angles of \triangle SHT (indeed, SHT). One very useful way to do this is to construct another triangle where we can find the angles, and show they are similar using length ratios. So you experiment around for a while, and find that it is similar to the triangle formed by sticking the isosceles triangles EHF,ESC,FTC together. Now you are almost done, just need to formalise a bit.
Construct C_p such that \triangle ESC\sim\triangle EHC_p (by spiral similarities \triangle ESH\sim\triangle ECC_p ). Now HC_p=HE=HF and \angle EHF+\angle ESC+\angle FTC=360 (since \angle ESC=\angle EHC and \angle FTC=\angle FHC ). So we also have \triangle FHC_p\sim\triangle FTC . Note that \angle EC_pF=\frac12\angle EHF=\angle SHT , and the length ratio \frac{HS}{HT}=\frac{HS}{HE}\frac{HF}{HT}=\frac{CC_p}{EC_p}\frac{FC_p}{CC_p}=\frac{FC_p}{EC_p} . Thus \triangle SHT\sim\triangle FC_pE , and the rest is just angle chase.
【E】Here was a sketch of my solution. Not very elegant but quite direct.
size(9cm);pair A = dir(110);pair B = dir(200);pair D = dir(340);pair C = -A;pair H = foot(A, B, D);draw(A--B--D--A--C--H--A);...
First by angle chasing one can show that \angle ATH = \angle TCH + 90^{\circ} , so the tangent to (CHT) at T is perpendicular to AD . Thus the circumcenter O of \triangle TCH lies on AD .
Let the perpendicular bisector of TH meet AH at P now. It suffices to show that \frac{AP}{PH} is symmetric in b = AD and d=AB , because then P will be the circumcenter of \triangle TSH . To do this, set AH = \frac{bd}{2R} and AC=2R . Use the Law of Cosines on \triangle ACO and \triangle AHO , using variables x=AO and r=HO . We get that
r^2 = x^2 + AH^2 - 2x \cdot AH \cdot \frac{d}{2R} = x^2 + (2R)^2 - 2bx.
By the Angle Bisector Theorem, \frac{AP}{PH} = \frac{AO}{HO} , so the rest is a ~15 minute computation now.
【A】 First of all let points M,N be symmetric points of C wrt D,B . Now easily get CHTM,CHSN cyclic. And let Y,X be the centers of these circles respectively. Now if you try to prove by Menelaus theorem that the perp bisectors of HS,HT intersect on AH (which is equivalent to the given problem) you will reduce the problem to XS/XA=YT/YA . Now this reduces to XH/HY=XA/AY . Now this can be proven if you prove that AHC is the apollonious circle for segment XY . If you intersect the perp bisector of AH with XY this reduces to TA^2=TX\cdot TY now you can angle chase that TAX\sim TYA which is trivial.

我的更多文章

下载客户端阅读体验更佳

APP专享