完整版真题免费下载
+答案解析请参考文末
A permutation of the set of positive integers is a sequence such that each element of appears precisely one time as a term of the sequence. For example, is a permutation of . Let be the number of permutations of for which is a perfect square for all . Find with proof the smallest such that is a multiple of .
Let be an integer. Find, with proof, all sequences of positive integers with the following three properties:
;
for all ;
given any two indices and (not necessarily distinct) for which , there is an index such that .
Let be a convex pentagon inscribed in a semicircle of diameter . Denote by the feet of the perpendiculars from onto lines , respectively. Prove that the acute angle formed by lines and is half the size of , where is the midpoint of segment .
A triangle is called a parabolic triangle if its vertices lie on a parabola . Prove that for every nonnegative integer , there is an odd number and a parabolic triangle with vertices at three distinct points with integer coordinates with area .
Two permutations and of the numbers are said to intersect if for some value of in the range . Show that there exist permutations of the numbers such that any other such permutation is guaranteed to intersect at least one of these permutations.
Let be a triangle with . Points and lie on sides and , respectively, such that and . Segments and meet at . Determine whether or not it is possible for segments to all have integer lengths.
We claim that the smallest is .
Let be the set of positive perfect squares. We claim that the relation is an equivalence relation on .
It is reflexive because for all .
It is symmetric because .
It is transitive because if and , then , since is closed under multiplication and a non-square times a square is always a non-square.
We are restricted to permutations for which , in other words to permutations that send each element of into its equivalence class. Suppose there are equivalence classes: . Let be the number of elements of , then .
Now . In order that , we must have for the class with the most elements. This means , since no smaller factorial will have as a factor. This condition is sufficient, since will be divisible by for , and even more so .
The smallest element of the equivalence class is square-free, since if it were divisible by the square of a prime, the quotient would be a smaller element of . Also, each prime that divides divides all the other elements of , since and thus . Therefore for all . The primes that are not in occur an even number of times in each .
Thus the equivalence class . With , we get the largest possible . This is just the set of squares in , of which we need at least , so . This condition is necessary and sufficient.
This proof can also be rephrased as follows, in a longer way, but with fewer highly technical words such as "equivalence relation":
It is possible to write all positive integers in the form , where is the largest perfect square dividing , so is not divisible by the square of any prime. Obviously, one working permutation of is simply ; this is acceptable, as is always in this sequence.
Lemma 1. We can permute any numbers that, when each divided by the largest perfect square that divides it, yield equal quantities .
Proof. Let and be the values of and , respectively, for a given as defined above, such that is not divisible by the square of any prime. We can obviously permute two numbers which have the same , since if where and are 2 values of , then , which is a perfect square. This proves that we can permute any numbers with the same value of .
End Lemma
Lemma 2. We will prove the converse of Lemma 1: Let one number have a value of and another, . and are both perfect squares.
Proof. and are both perfect squares, so for to be a perfect square, if is greater than or equal to , must be a perfect square, too. Thus is times a square, but cannot divide any squares besides , so ; . Similarly, if , then for our rules to keep working.
End Lemma
We can permute numbers with the same in ways. We must have at least 67 numbers with a certain so our product will be divisible by 67. Obviously, then it will also be divisible by 2, 3, and 5, and thus 2010, as well. Toms as , in general, we need numbers all the way up to , so obviously, is the smallest such number such that we can get a term; here 67 terms are 1. Thus we need the integers , so , or , is the answer.
We have to somehow calculate the number of permutations for a given . How in the world do we do this? Because we want squares, why not call a number , where is the largest square that allows to be non-square? is the only square can be, which only happens if is a perfect square.
For example, , therefore in this case .
I will call a permutation of the numbers , while the original I will call .
Note that essentially we are looking at "pairing up" elements between and such that the product of and is a perfect square. How do we do this? Using the representation above.
Each square has to have an even exponent of every prime represented in its prime factorization. Therefore, we can just take all exponents of the primes and if there are any odd numbers, those are the ones we have to match- in effect, they are the numbers mentioned at the beginning.
By listing the values, in my search for "dumb" or "obvious" ideas I am pretty confident that only values with identical s can be matched together. With such a solid idea let me prove it.
If we were to "pair up" numbers with different s, take for example with an of and with an of , note that their product gives a supposed of because the values cancel out. But then, what happens to the extra left? It doesn't make a square, contradiction. To finish up this easy proof, note that if a "pair" has different values, and the smaller one is , in order for the product to leave a square, the larger value has to have not just but another square inside it, which is absurd because we stipulated at the beginning that was square-free except for the trivial multiplication identity, 1.
Now, how many ways are there to do this? If there are numbers with , there are clearly ways of sorting them. The same goes for by this logic. Note that the as stated by the problem requires a thrown in there because , so there has to be a with 67 elements with the same . It is evident that the smallest will occur when , because if is bigger we would have to expand to get the same number of values. Finally, realize that the only numbers with are square numbers! So our smallest , and we are done.
I relied on looking for patterns a lot in this problem. When faced with combo/number theory, it is always good to draw a sketch. Never be scared to try a problem on the USAJMO. It takes about 45 minutes. Well, it's 2010 and a number 1. Cheers!
The sequence is .
We will prove that any sequence , that satisfies the given conditions, is an arithmetic progression with as both the first term and the increment. Once this is proved, condition (b) implies that . Therefore , and the sequence is just the even numbers from to . The sequence of successive even numbers clearly satisfies all three conditions, and we are done.
First a degenerate case. If , there is only one element , and condition (b) gives or . Conditions (a) and (c) are vacuously true.
Otherwise, for , we will prove by induction on that the difference for all , which makes all the differences , i.e. the sequence is an arithmetic progression with as the first term and increment as promised.
So first the case. With , exists and is less than by condition (a). Now since by condition (b) , we conclude that , and therefore by condition (c) for some . Now, since , and can only be . So .
Now for the induction step on all values of . Suppose we have shown that for all , . If we are done, otherwise , and by condition (c) for some . This is larger than , but smaller than by the inductive hypothesis. It then follows that , the only element of the sequence between and . This establishes the result for .
So, by induction for all , which completes the proof.
The claim is that in this sequence, if there are elements where , such that , then the sequence contains every number less than .
Proof: Let and be the numbers less than such that . We take this sequence modulo . This means that if is an element in this sequence then is as well. are all elements in the sequence. Clearly, one of and is less than , which means that are in this sequence modulo . Now we want to show every number is achievable. We have already established that and are relatively prime, so by euclidean algorithm, if we take the positive difference of and every time, we will get that is in our sequence. Then, we can simply add or subtract as many times from as desired to get every single number.
We have proved that there are no two numbers that can be relatively prime in our sequence, implying that no two consecutive numbers can be in this sequence. Because our sequence has terms, our sequence must be one of or , the latter obviously fails, so is our only possible sequence.
Let , . Since is a chord of the circle with diameter , . From the chord , we conclude .
Triangles and are both right-triangles, and share the angle , therefore they are similar, and so the ratio . Now by Thales' theorem the angles are all right-angles. Also, , being the fourth angle in a quadrilateral with 3 right-angles is again a right-angle. Therefore and . Similarly, , and so .
Now is perpendicular to so the direction is counterclockwise from the vertical, and since we see that is clockwise from the vertical. (Draw an actual vertical line segment if necessary.)
Similarly, is perpendicular to so the direction is clockwise from the vertical, and since is we see that is counterclockwise from the vertical.
Therefore the lines and intersect at an angle . Now by the central angle theorem and , and so , and we are done.
Note that is a quadrilateral whose angles sum to 360°; can you find a faster approach using this fact?
We can prove a bit more. Namely, the extensions of the segments and meet at a point on the diameter that is vertically below the point .
Since and is inclined counterclockwise from the vertical, the point is horizontally to the right of .
Now , so is vertically above the diameter . Also, the segment is inclined clockwise from the vertical, so if we extend it down from towards the diameter it will meet the diameter at a point which is horizontally to the left of . This places the intersection point of and vertically below .
Similarly, and by symmetry the intersection point of and is directly below on , so the lines through and meet at a point on the diameter that is vertically below .
The Footnote's claim is more easily proved as follows.
Note that because and are both complementary to , they must be equal. Now, let intersect diameter at . Then is cyclic and so . Hence is cyclic as well, and so we deduce that Hence are collinear and so . This proves the Footnote.
The Footnote's claim can be proved even more easily as follows.
Drop an altitude from to at point . Notice that are collinear because they form the Simson line of from . Also notice that are collinear because they form the Simson line of from . Since is at the diameter , lines and must intersect at the diameter.
There is another, more simpler solution using Simson lines. Can you find it?
Of course, as with any geometry problem, DRAW A HUGE DIAGRAM spanning at least one page. And label all your right angles, noting and . It looks like there are a couple of key angles we need to diagram. Let's take . From there .
Move on to the part about the intersection of and . Call the intersection . Note that by Simson Lines from point to and , is perpendicular to and lies on . Immediately note that we are trying to show that .
It suffices to show that referencing quadrilateral , where represents the intersection of , we have reflex . Note that the reflex angle is , therefore it suffices to show that . To make this proof more accessible, note that via (cyclic) rectangles and , it suffices to prove .
Note . Note , which completes the proof.
For reference/feasibility records: took expiLnCalc ~56 minutes (consecutively). During the problem expiLnCalc realized that the inclusion of was necessary when trying to show that . Don't be afraid to attempt several different strategies, and always be humble!
Let be the projection of onto . Notice that lies on the Simson Line from to , and the Simson Line from to . Hence, , so it suffices to show that .
Since and are cyclic quadrilaterals,as required.
Let the vertices of the triangle be . The area of the triangle is the absolute value of in the equation:
If we choose , and gives the actual area. Furthermore, we clearly see that the area does not change when we subtract the same constant value from each of , and . Thus, all possible areas can be obtained with , in which case .
If a particular choice of and gives an area , with a positive integer and a positive odd integer, then setting , gives an area .
Therefore, if we can find solutions for , and , all other solutions can be generated by repeated multiplication of and by a factor of .
Setting and , we get , which yields the case.
Setting and , we get , which yields the case.
Setting and , we get . Multiplying these values of and by , we get , , , which yields the case. This completes the construction.
We proceed via induction on n. Notice that we prove instead a stronger result: there exists a parabolic triangle with area with two of the vertices sharing the same ordinate (y-coordinate).
Base case: If n = 0, consider the parabolic triangle ABC with A(0, 0), B(1, 1), C(-1, 1) that has area 1/2 * 1 * 2 = 1, so that n = 0 and m = 1. If n = 1, let ABC = A(5, 25), B(4, 16), C(-4, 16). Because ABC has area 1/2 * 8 * 9 = 36, we set n = 1 and m = 3. If n = 2, consider the triangle formed by A(21, 441), B(3, 9), C(-3, 9). It is parabolic and has area 1/2 * 6 * 432 = 1296 = , so n = 2 and m = 9.
Inductive step: If n = k produces parabolic triangle ABC with A(a, ), B(b, ), and C(-b, ), consider A'B'C' with vertices A(4a, ), B(4b, ), and C(-4b, ). If ABC has area , then A'B'C' has area , which is easily verified using the 1/2 * base * height formula for triangle area. This completes the inductive step for k -> k+3.
Hence, for every nonnegative integer n, there exists an odd m and a parabolic triangle with area with two vertices sharing the same ordinate. The problem statement is a direct result of this result.
First, consider triangle with vertices , , . This has area so case is satisfied.
Then, consider triangle with vertices , and set and . The area of this triangle is . We have that We desire , or , and is clearly always odd for positive , completing the proof.
Let be a positive integer. Let be the smallest positive integer with . Since , . Let be the set of positive integers from to . Let , be .
Let be the set of of permutations of .
Let be the set of cyclic permutations of , there are cyclic permutations in all, and acts transitively on , i.e. for every pair of elements , there is an element of that maps to .
Let be the permutations in that leave fixed, and restricted to yield one of the permutations in . There is a natural one-to-one correspondence between and .
We claim that the permutations intersect every permutation in .
Suppose, to the contrary, that there exists a permutation that does not intersect any permutation in . Since acts transitively on the permutation cannot send any element of to any other element of , therefore it must send all the elements of to , but since has elements and , this is impossible by the pigeonhole principle. Therefore such a permutation cannot exist, and the permutations in intersect every permutation in .
For we get , which is the required special case of the general result above.
We know that angle , as the other two angles in triangle add to . Assume that only , and are integers. Using the Law of Cosines on triangle BIC,
. Observing that is an integer and that we have
and therefore,
The LHS () is irrational, while the RHS is the quotient of the division of two integers and thus is rational. Clearly, there is a contradiction. Therefore, it is impossible for , and to all be integers, which invalidates the original claim that all six lengths are integers, and we are done.
The result can be also proved without direct appeal to trigonometry, via just the angle bisector theorem and the structure of Pythagorean triples. (This is a lot more work).
A triangle in which all the required lengths are integers exists if and only if there exists a triangle in which and are relatively-prime integers and the lengths of the segments are all rational (we divide all the lengths by the or conversely multiply all the lengths by the least common multiple of the denominators of the rational lengths).
Suppose there exists a triangle in which the lengths and are relatively-prime integers and the lengths are all rational.
Since is the bisector of , by the angle bisector theorem, the ratio , and since is the bisector of , . Therefore, . Now is by assumption rational, so is rational, but and are assumed integers so must also be rational. Since is the hypotenuse of a right-triangle, its length is the square root of an integer, and thus either an integer or irrational, so must be an integer.
With and relatively-prime, we conclude that the side lengths of must be a Pythagorean triple: , with relatively-prime positive integers and odd.
Without loss of generality, . By the angle bisector theorem,
Since is a right-triangle, we have:
and so is rational if and only if is a perfect square.
Also by the angle bisector theorem,
and therefore, since is a right-triangle, we have:
and so is rational if and only if is a perfect square.
Combining the conditions on and , we see that and must both be perfect squares. If it were so, their ratio, which is , would be the square of a rational number, but is irrational, and so the assumed triangle cannot exist.
© 2024. All Rights Reserved. 沪ICP备2023009024号-1