tceic.com

学霸学习网 这下你爽了

学霸学习网 这下你爽了

1 2010 China Western Mathematical Olympiad Taiyuan Shanxi 28-29 October, 2010 1. Suppose that and are non-negative integers, and = 22 number. Prove that (a) 22 (b) 2

+1

2. As shown in the ?gure below, is a diameter of a circle with center . Let and be two di?erent points on the circle on the same side of , and the + 1 is a prime lines tangent to the circle at points and meet at . Segments and meet at . Lines and meet at . Prove that , , and are concyclic. Proof I. Join , and . It follows from ∠ + ∠ = 90? + 90? =

≡ 1 (mod +1 );

+1

is the smallest positive integer satisfying the congruence equation

+1

2 ≡ 1 (mod +1 ). Proof. We want to prove that 22

= +1 + 1 for some integer not

180? that is cyclic. If = , then is cyclic. We may assume that ∕= in the following. Let be the intersection of and , and 1 be the intersection of and . Let 2 be the foot of perpendicular of to . It follows from ⊥ and ⊥ that is the orthocenter of △, so 2 ⊥ . As ∠2 = ∠ + ∠ = 180? ? 2∠, and ∠ = 180? ? ∠ ? ∠ = 180? ? (180? ? 2∠) ? (180? ? 2∠) = 2(∠ + ∠) ? 180? ? 2∠, then ∠2 = ∠, so , , 2 and are concyclic. It follows from ∠ = ∠ = ∠1 = 90? that , , , 1 and are concyclic. Hence 1 = 2 , i.e. ⊥ and they meet at . Consequently, , , and are concyclic. Proof II. Join , , , , . It follows from ∠ = ∠ that Rt△ ? Rt△, and so

divisible by . We proceed by induction on . When = 0, it follows from 22 = ? 1 that 22 = ( ? 1)2 = ( ? 2) + 1, in this case 0 = ? 2. For inductive step, suppose that 22 then ( ) +1 +1 +1 22 = (22 ) = +1 + 1 ( ) ∑ () ( ? 1) +1 2 ∑ +1 +1 ( ) + (+1 ) . = ( ) = 1 + ? + 2 =3 =0 As ≥ 0, then for any ≥ 2, we have ( + 1) ≥ 2( + 1) = 2 + 2 ≥ + 2, so 22

+1 +1 +1

= +1 + 1 where ≥ 0 and ? ,

= +2 +1 + 1, where +1 ∈ ?+ and ? +1 . It follows from

mathematical induction that (a) holds. Next we prove (b). Write 2+1 = ? + , where ?, ∈ ? and 0 ≤ < . Then it follows from (a) that 1 ≡ 22

+1

≡ 2?+ ≡ (2 )? ? 2 ≡ 2 (mod +1 ).

As 0 ≤ < , it follow from the de?nition of that = 0, i.e. ∣ 2+1 . By the fundamental theorem of arithmetic, = 2 . If ≤ , then 22 = ( )2? ( ) 22 ≡ 1 (mod ). On the other hand, 22 = 22 ≡ (?1) ≡ ?1 (mod ), which is a contradiction, and hence = + 1, i.e. = 2+1 .

=

.

As ∠ = 90? ? ∠ = ∠,

so △ ? Δ, and hence ∠ = ∠. As ∠ = ∠ , so ∠ + ∠ = ∠ + ∠ = 90? . Hence ⊥ , it follows that , , , , are concyclic.

2 3. Determine all possible values of positive integer , such that there are di?erent 3-element subsets 1 , 2 , ? ? ? , of the set {1, 2, ? ? ? , }, with ∣ ∩ ∣ ∕= 1 for all ∕= . Solution. The set of positive integers satisfying the given condition consists of all positive multiples of 4. We ?rst prove that = 4 ( ∈ ?+ ) satisfying the condition. De?ne 1 , 2 , ? ? ? , 4 as follows 4? = { 4 ? 3, 4 ? 2, 4 ? 1, 4 } ? {4 ? }, for all 1 ≤ ≤ and 0 ≤ ≤ 3. Second, we want to prove that if 4 ? , then such subsets do not exist. Suppose contrary, assume that 1 , ? ? ? , be di?erent 3-element subsets ful?lling the condition stated in the problem. Let 1 = {, , }, consider all the given 3-element subsets with non-empty intersection, we may assume that they are 2 , ? ? ? , after relabeling. Let = 1 ∪ 2 ∪ ? ? ? ∪ . We divide into di?erent cases: ? If ∣ ∣ = 3, then = 1 < ∣ ∣; () ? If ∣ ∣ = 4, then ≤ 4 = 4 = ∣ ∣; 3 ? If ∣ ∣ ≥ 5, then we prove that < ∣ ∣ as follows. Suppose that ≥ ∣ ∣, then for any 2 ≤ , ≤ , we have ∣1 ∩ ∣ = 2, ∣1 ∩ ∣ = 2. As ∣1 ∣ = 3, we have ∩ ∕= ?. And it follows from ∣ ∩ ∣ ∕= 1 that ∣ ∩ ∣ = 2. It means that any two distinct subsets of 1 , ? ? ? , have only 2 common elements. Consider the 4 intersections 1 ∩2 , 1 ∩3 , 1 ∩4 , 1 ∩5 , it follows from pigeon-hole principle that there are 2 intersections are equal, by relabeling again we may assume that they are 2 = {, , }, 3 = {, , }. Then for any 4 ≤ ≤ , we have , ∈ ; otherwise contains at least one of or , and the other 3 elements , and , in this case, ∣ ∣ ≥ 4, which is impossible. Hence ∣ ∣ = + 2, which contradicts to ∣ ∣ = . From the argument above, one can divide the subsets 1 , ? ? ? , into several groups, and any 2 subsets in the same group has non-empty intersections. Moreover, the number of subsets in the same group is not more than the number of elements appeared in this group. As the number of subsets is , which is equal the number of elements in {1, 2, ? ? ? , }, so each group has exactly 4 subsets. It follows that 4 ∣ , which is contrary to the original assumption 4 ? . It follows from that ≤ follows. = ≤ = 4. Let 1 , 2 , ? ? ? , , 1 , 2 , ? ? ? , be non-negative numbers satisfying the following conditions simultaneously: ∑ (1) =1 ( + ) = 1; ∑ (2) =1 ( ? ) = 0; ∑ (3) =1 2 ( + ) = 10. Prove that max{ , } ≤ inequality that ( )

2

10 for all 1 ≤ ≤ . 10 + 2 Proof. For any 1 ≤ ≤ , it follows from the given conditions and Cauchy’s ( ∑ ( ∑

=1 ( ∑ =1

)2 )2 ) ( ) ∑ 2

=1 ∑ =1 2

≤

(

=1 2

)( 1?

10 ?

∑ =1

)

≤ (10 ? )(1 ? ) = 10 ? (10 + 2 ) + 2 2 .

10 10 . Similarly, ≤ , and hence the result 2 10 + 10 + 2

3 5. Let be an integer and > 1. De?ne a sequence { } as follows: 0 = 0, 1 = 1 and +1 = + ?1 for = 1, 2, ? ? ? . Determine, with proof, all possible for which there exist non-negative integers ?, (? ∕= ) and positive integers , such that ? + = + . Solution. The answer is = 2. If = 2, then 0 = 0, 1 = 1, 2 = 2, so 0 + 22 = 2 + 21 = 4. Hence (?, ) = (0, 2) and (, ) = (2, 1). For ≥ 3, it follows from the recurrent relation that the sequence { } is strictly increasing, and ∣ +1 ? ?1 for all ≥ 1. In particular, for ≥ 0, we have 2 ≡ 0 ≡ 0 (mod ), 2+1 ≡ 1 ≡ 1 (mod ). (?) Then by increasing property of { } and (4), we have = ?1 , so inequalities (1)-(3) turn into equalities. It follows from (2) that = , and from (3) that = 2. Hence = ?1 = 1 = 1. And it follows from (1) that ? = 0. From ? + = + , we have 2 = + = 2, so = 2, which is impossible. So = 2 is the only solution. 6. As shown in the ?gure below, △ is a rightangled triangle, ∠ = 90? . Draw a circle centered at with radius . Let be a point on the side , and is tangent to the circle at . The line through perpendicular to meets line at point . Line meets at point . The line through parallel to meets at . Prove that = . Proof. Let be the intersection of and , and be the intersection of and . Join , and . In △, it follows from ⊥ that ? = 2 = 2 , so △ ? △, and △ = ∠.

Suppose there exist ?, ∈ ?, and , ∈ ?+ such that ? ∕= and ? + = + . We may assume that ? < , and divide into the following cases. (a) < ? < : Then ? + ≤ ? + ??1 < ? + ??1 = ?+1 ≤ < + , which contradicts to the original assumption. (b) ? = < : If ? = = ?1, then we have + = ? + = (+1)?1 , and modulo we have ≡ ?1 mod , which contradicts to (?). If = < ? 1, then ? + < ?2 + ?2 = < + , which contradicts to the original assumption. (c) ? < < : In this case, since we have > 0, then ? + ≤ +?1 = +1 ≤ < + , which contradicts to the original assumption. (d) ? < ≤ : Then >

? + ?

= . It follows from (1) As ∠ = ∠ = 90? , so is cyclic, and ∠ = ∠ . It follows from ∠ = ∠ = ∠ , so ∥, and hence (2) = , i.e. ? = 1.

+ = + ? ≥ that ≥ ? Note that = ?1 + ?2 ≥ ? , hence

? 1 ≥ ? = . (3)

(1)

As the line intersect △, we have As ∥, we have (4) From (1)-(3), we have

?

?

=1

(2).

=

,

so

=

.

(3)

? 1 > ≥ ≥ ( ? 1)?1 ≥ ?1 .

= 1, and so = .

4 7. There are ( ≥ 3) players in a table tennis tournament, in which any two players have a match. Player is called not out-performed by player , if at least one of player ’s losers is not a ’s loser. Determine, with proof, all possible values of , such that the following case could happen: after ?nishing all the matches, every player is not out-performed by any other player. Solution. The answer is = 3 or ≥ 5. (1) For = 3, suppose , and are 3 players, and the result of 3 matches are: wins , wins , and wins . These results obviously satisfy the condition. (2) If = 4, suppose that the condition holds, i.e. in view of the results of all matches, every player is not out-performed by any other player. It is obvious that none of these 4 players wins in his 3 games, otherwise, the other 3 players will be not out-performed by this player. Similarly, none of these 3 players loses in his 3 games. It follows each player wins 1 or 2 matches. For the player , assume that wins and , but loses to , then both and win ; otherwise they would not out-performed . For the loser in the match vs , he only wins , and so the loser is impossible to be not out-performed by the winner. Consequently, for = 4 the given condition could not happen. (3) For = 6, one can construct the tournament results by means of the following directed graph, in which each black dot represents a player, and ? ?→ ? represent a match with the result that player ? wins player ?. One can check that each of these 3 players , , is not out-performed by any one of the other two players. Hence the tournament result of these + 2 players satis?es the required condition. In particular, it follows from (1) and induction step of (4) that the required condition holds for any odd with ≥ 3. Moreover, it follows from (3) and induction step of (4) that the required condition holds for any even with ≥ 6, and it completes the proof. . (4) If there exist tournament results so that each of players (1 ≤ ≤ ) is not out-performed by any other player, we will prove that the same holds for + 2 players as follows. Suppose that and are the additional players to the original players. Construct the game results of and as follows: ?→ , ?→ , ?→ for all = 1, 2, ? ? ? , , and the game results among ’s are still the original ones. Now we want to check that these + 2 players satisfy the given condition. For any player ∈ { 1 , 2 , ? ? ? , }, then it su?ces to consider the players , , , and it reduces to the case = 3.

5 8. Determine all possible values of integer k for which there exist positive integers + 1 + 1 + = . and such that Solution. The answer is that = 3 or 4. Fix a possible value , among all the pairs (, ) of positive integers satisfying + 1 + 1 + = , choose any (, ) such that is the smallest. Then the quadratic equation 2 + (1 ? ) + 2 + = 0 has an integral root = . Let = ′ be the second root, it follows from + ′ = ? 1 that ′ ∈ ?, and from ? ′ = ( + 1) that ′ > 0. Hence we have + 1 ′ + 1 + = . ′ And it follows from the assumption on that ≥ , ′ ≥ .

So one of and ′ is equal to . Without loss of generality, we may assume = , so = 2 + 2 , and so ∣ 2 i.e. = 1 or 2, and = 3 or 4 respectively. If = = 1, then = 4; if = = 2, then = 3. Consequently = 3 or 4 are the only solution.