IMO 2014 problems and Solutions
On, Thursday, 12 May 2016. 1 : 48 pm. i'd like to make an solution of math which i copy from the book.
Problem 1. Let a0 < a1 < a2 . . . be an infinite sequence of positive integers. Prove that there exists a unique integer n ≥ 1 such that an < a0 + a1 + a2 + · · · + an n ≤ an+1.
Problem 2. Let n ≥ 2 be an integer. Consider an n × 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 × k square which does not contain a rook on any of its k 2 unit squares.
Problem 3. Convex quadrilateral ABCD has ∠ABC = ∠CDA = 90◦ . 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 ∠CHS − ∠CSB = 90◦ , ∠T HC − ∠DT C = 90◦ . Prove that line BD is tangent to the circumcircle of triangle T SH.
Problem 4. Let P and Q be on segment BC of an acute triangle ABC such that ∠P AB = ∠BCA and ∠CAQ = ∠ABC. Let M and N be the points on AP and AQ, respectively, such that P is the midpoint of AM and Q is the midpoint of AN. Prove that the intersection of BM and CN is on the circumference of triangle ABC.
Problem 5. For every positive integer n, the Bank of Cape Town issues coins of denomination 1 n . Given a finite collection of such coins (of not necessarily different denominations) with total value at most 99 + 1 2 , prove that it is possible to split this collection into 100 or fewer groups, such that each group has total value at most 1.
Problem 6. A set of lines in the plane is in general position if no two are parallel and no three pass through the same point. A set of lines in general position cuts the plane into regions, some of which have finite area; we call these its finite regions. Prove that for all sufficiently large n, in any set of n lines in general position it is possible to colour at least √ n lines blue in such a way that none of its finite regions has a completely blue boundary. Note: Results with √ n replaced by c √ n will be awarded points depending on the value of the constant c.
Hence, the solution is :
Problem 1 Trivial enough that I won’t bother writing it out. Basically if you assume that no such n exists, then you get am < a0+a1+···+am m for all m. But am < a0 + · · · + am m ≤ a0 + a1 + (m − 1)am m which breaks the strictly increasing condition. Then, once you find a minimal working n, just show that no other n work.
Problem 2 The answer is n = √ k − 1 . It’s straightforward to show that if n ≥ m2 + 1 then we can find an empty m × m square; just consider a rook in the uppermost column and m squares below it; there are at most m − 1 other rooks. Now for the construction for n = m2 .Finally, to hit n ≤ m2 , just delete a row/column, and then if necessary place a rook in the unique position that fills the gap
Problem 3 First by angle chasing one can show that ∠AT H = ∠T CH + 90◦ , so the tangent to (CHT) at T is perpendicular to AD. Thus the circumcenter O of 4T CH lies on AD. Let the perpendicular bisector of T H meet AH at P now. It suffices to show that AP P H is symmetric in b = AD and d = AB, because then P will be the circumcenter of 4T SH. To do this, set AH = bd 2R and AC = 2R. Use the Law of Cosines on 4ACO and 4AHO, using variables x = AO and r = HO. We get that r 2 = x 2 + AH2 − 2x · AH · d 2R = x 2 + (2R) 2 − 2bx. By the Angle Bisector Theorem, AP P H = AO HO . Hence we just need to show r 2 x2 is symmetric in b and d. Notice that r 2 − x 2 = h 2 − 2xh · d 2R = (2R) 2 − 2bx where h = AH = bd 2R , whence x = (2R) 2 − h 2 2b − 2h · d 2R . Moreover, 1 2 r 2 x 2 − 1 = 1 x 2 x R 2 − b . Now, if we plug in the x in the right-hand side of the above, we obtain 2b − 2h · d 2R 4R2 − h 2 2b − 2h · d 2R 4R2 − h 2 · 2R 2 − b ! = 2h (4R2 − h 2) 2 b − h · d 2R −2hdR + bh2 . Pulling out a factor of −2Rh from the rightmost term, we get something that is symmetric in b and d, as required.
Problem 4 Since P B = c 2/a we have P = (0 : a 2 − c 2 : c 2 ), so M = (−a 2 : −− : 2c 2 ). Similarly N = (−a 2 : 2b 2 : −−). Thus BM ∩ CN = (−a 2 : 2b 2 : 2c 2 ) which clearly lies on the circumcircle
Problem 5 We’ll prove the result for at most k − 1 2 with k groups. First, perform the following optimizations. • If any coin of size 1 2m appears twice, then replace it with a single coin of size 1 m . • If any coin of size 1 2m+1 appears 2m + 1 times, group it into a single group and induct downwards. Apply this operation repeatedly until it cannot be done anymore. Now construct boxes B0, B1, . . . , Bk−1. In box B0 put any coins of size 1 2 (clearly there is at most one). In the other boxes Bm, put coins of size 1 2m+1 and 1 2m+2 (at most 2m of the former and at most one of the latter). Note that the total weight in the box is less than 1. Finally, place the remaining “light” coins of size at most 1 2k+1 in a pile. Then just toss coins from the pile into the boxes arbitrarily, other than the proviso that no box should have its weight exceed 1. We claim this uses up all coins in the pile. Assume not, and that some coin remains in the pile when all the boxes are saturated. Then all the boxes must have at least 1 − 1 2k+1 , meaning the total amount in the boxes is strictly greater than k 1 − 1 2k + 1 > k − 1 2 which is a contradiction. This gets a stronger bound k − k 2k+1 than the requested k − 1 2 . And dear IMO jury: THIS IS NOT A NUMBER THEORY PROBLEM.
Problem 6 Let c = (6e) − 1 2 . We’ll show the bound c √ n. The main core of the proof is the following lemma. Lemma (Lovasz Local Lemma). Consider several events, each occurring with probability at most p, such that each event is depends on at most d of the others. If epd ≤ 1 then there is a nonzero probability that no events happen. Split the n lines into c √ n groups of size √ n c each, arbitrarily. We are going to select one line from each of the groups at random to be blue. For each of the regions R1, R2, . . . , Rm we will consider an event Ak meaning “three of the lines bounding Rk are blue”; we designate these lines beforehand. We will show there is a nonzero probability that no events occur. The probability of Ak is clearly at most √c n 3 ., we have three groups to consider. Each group consists of √ n c lines. Each line is part of at most 2n − 2 regions. Hence Ak depends on at most 3 · √ n c ·(2n − 2) events. Thus, e c √ n 3 3 · √ n c · (2n − 2) < 6ec2 = 1 and we are done by LLL.
Problem 1. Let a0 < a1 < a2 . . . be an infinite sequence of positive integers. Prove that there exists a unique integer n ≥ 1 such that an < a0 + a1 + a2 + · · · + an n ≤ an+1.
Problem 2. Let n ≥ 2 be an integer. Consider an n × 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 × k square which does not contain a rook on any of its k 2 unit squares.
Problem 3. Convex quadrilateral ABCD has ∠ABC = ∠CDA = 90◦ . 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 ∠CHS − ∠CSB = 90◦ , ∠T HC − ∠DT C = 90◦ . Prove that line BD is tangent to the circumcircle of triangle T SH.
Problem 4. Let P and Q be on segment BC of an acute triangle ABC such that ∠P AB = ∠BCA and ∠CAQ = ∠ABC. Let M and N be the points on AP and AQ, respectively, such that P is the midpoint of AM and Q is the midpoint of AN. Prove that the intersection of BM and CN is on the circumference of triangle ABC.
Problem 5. For every positive integer n, the Bank of Cape Town issues coins of denomination 1 n . Given a finite collection of such coins (of not necessarily different denominations) with total value at most 99 + 1 2 , prove that it is possible to split this collection into 100 or fewer groups, such that each group has total value at most 1.
Problem 6. A set of lines in the plane is in general position if no two are parallel and no three pass through the same point. A set of lines in general position cuts the plane into regions, some of which have finite area; we call these its finite regions. Prove that for all sufficiently large n, in any set of n lines in general position it is possible to colour at least √ n lines blue in such a way that none of its finite regions has a completely blue boundary. Note: Results with √ n replaced by c √ n will be awarded points depending on the value of the constant c.
Hence, the solution is :
Problem 1 Trivial enough that I won’t bother writing it out. Basically if you assume that no such n exists, then you get am < a0+a1+···+am m for all m. But am < a0 + · · · + am m ≤ a0 + a1 + (m − 1)am m which breaks the strictly increasing condition. Then, once you find a minimal working n, just show that no other n work.
Problem 2 The answer is n = √ k − 1 . It’s straightforward to show that if n ≥ m2 + 1 then we can find an empty m × m square; just consider a rook in the uppermost column and m squares below it; there are at most m − 1 other rooks. Now for the construction for n = m2 .Finally, to hit n ≤ m2 , just delete a row/column, and then if necessary place a rook in the unique position that fills the gap
Problem 3 First by angle chasing one can show that ∠AT H = ∠T CH + 90◦ , so the tangent to (CHT) at T is perpendicular to AD. Thus the circumcenter O of 4T CH lies on AD. Let the perpendicular bisector of T H meet AH at P now. It suffices to show that AP P H is symmetric in b = AD and d = AB, because then P will be the circumcenter of 4T SH. To do this, set AH = bd 2R and AC = 2R. Use the Law of Cosines on 4ACO and 4AHO, using variables x = AO and r = HO. We get that r 2 = x 2 + AH2 − 2x · AH · d 2R = x 2 + (2R) 2 − 2bx. By the Angle Bisector Theorem, AP P H = AO HO . Hence we just need to show r 2 x2 is symmetric in b and d. Notice that r 2 − x 2 = h 2 − 2xh · d 2R = (2R) 2 − 2bx where h = AH = bd 2R , whence x = (2R) 2 − h 2 2b − 2h · d 2R . Moreover, 1 2 r 2 x 2 − 1 = 1 x 2 x R 2 − b . Now, if we plug in the x in the right-hand side of the above, we obtain 2b − 2h · d 2R 4R2 − h 2 2b − 2h · d 2R 4R2 − h 2 · 2R 2 − b ! = 2h (4R2 − h 2) 2 b − h · d 2R −2hdR + bh2 . Pulling out a factor of −2Rh from the rightmost term, we get something that is symmetric in b and d, as required.
Problem 4 Since P B = c 2/a we have P = (0 : a 2 − c 2 : c 2 ), so M = (−a 2 : −− : 2c 2 ). Similarly N = (−a 2 : 2b 2 : −−). Thus BM ∩ CN = (−a 2 : 2b 2 : 2c 2 ) which clearly lies on the circumcircle
Problem 5 We’ll prove the result for at most k − 1 2 with k groups. First, perform the following optimizations. • If any coin of size 1 2m appears twice, then replace it with a single coin of size 1 m . • If any coin of size 1 2m+1 appears 2m + 1 times, group it into a single group and induct downwards. Apply this operation repeatedly until it cannot be done anymore. Now construct boxes B0, B1, . . . , Bk−1. In box B0 put any coins of size 1 2 (clearly there is at most one). In the other boxes Bm, put coins of size 1 2m+1 and 1 2m+2 (at most 2m of the former and at most one of the latter). Note that the total weight in the box is less than 1. Finally, place the remaining “light” coins of size at most 1 2k+1 in a pile. Then just toss coins from the pile into the boxes arbitrarily, other than the proviso that no box should have its weight exceed 1. We claim this uses up all coins in the pile. Assume not, and that some coin remains in the pile when all the boxes are saturated. Then all the boxes must have at least 1 − 1 2k+1 , meaning the total amount in the boxes is strictly greater than k 1 − 1 2k + 1 > k − 1 2 which is a contradiction. This gets a stronger bound k − k 2k+1 than the requested k − 1 2 . And dear IMO jury: THIS IS NOT A NUMBER THEORY PROBLEM.
Problem 6 Let c = (6e) − 1 2 . We’ll show the bound c √ n. The main core of the proof is the following lemma. Lemma (Lovasz Local Lemma). Consider several events, each occurring with probability at most p, such that each event is depends on at most d of the others. If epd ≤ 1 then there is a nonzero probability that no events happen. Split the n lines into c √ n groups of size √ n c each, arbitrarily. We are going to select one line from each of the groups at random to be blue. For each of the regions R1, R2, . . . , Rm we will consider an event Ak meaning “three of the lines bounding Rk are blue”; we designate these lines beforehand. We will show there is a nonzero probability that no events occur. The probability of Ak is clearly at most √c n 3 ., we have three groups to consider. Each group consists of √ n c lines. Each line is part of at most 2n − 2 regions. Hence Ak depends on at most 3 · √ n c ·(2n − 2) events. Thus, e c √ n 3 3 · √ n c · (2n − 2) < 6ec2 = 1 and we are done by LLL.
Komentar
Posting Komentar