Home » 国际竞赛 » 数学国际竞赛 » AMC美国数学竞赛 » Details

2010 USAJMO Problems真题及答案

Category: AMC美国数学竞赛, 国际竞赛 Date: 2019年8月13日下午12:22

2010 USAJMO Problems真题及答案

完整版真题免费下载

+答案解析请参考文末

Day 1

Problem 1

A permutation of the set of positive integers? $[n] = {1, 2, ldots, n}$ ?is a sequence? $(a_1, a_2, ldots, a_n)$ ?such that each element of? $[n]$ ?appears precisely one time as a term of the sequence. For example,? $(3, 5, 1, 2, 4)$ ?is a permutation of? $[5]$ . Let? $P(n)$ ?be the number of permutations of? $[n]$ ?for which? $ka_k$ ?is a perfect square for all? $1leq kleq n$ . Find with proof the smallest? $n$ ?such that? $P(n)$ ?is a multiple of? $2010$ .

Problem 2

Let? $n > 1$ ?be an integer. Find, with proof, all sequences? $x_1, x_2, ldots, x_{n-1}$ ?of positive integers with the following three properties:

$x_1 < x_2 < cdots < x_{n-1}$ ;

$x_i + x_{n-i} = 2n$ ?for all? $i = 1, 2, ldots, n - 1$ ;

given any two indices? $i$ ?and? $j$ ?(not necessarily distinct) for which? $x_i + x_j < 2n$ , there is an index? $k$ ?such that? $x_i + x_j = x_k$ .

Problem 3

Let? $AXYZB$ ?be a convex pentagon inscribed in a semicircle of diameter? $AB$ . Denote by? $P, Q, R, S$ ?the feet of the perpendiculars from? $Y$ onto lines? $AX, BX, AZ, BZ$ , respectively. Prove that the acute angle formed by lines? $PQ$ ?and? $RS$ ?is half the size of? $angle XOZ$ , where? $O$ ?is the midpoint of segment? $AB$ .

Day 2

Problem 4

A triangle is called a?parabolic triangle?if its vertices lie on a parabola? $y = x^2$ . Prove that for every nonnegative integer? $n$ , there is an odd number? $m$ ?and a parabolic triangle with vertices at three distinct points with integer coordinates with area? $(2^nm)^2$ .

Problem 5

Two permutations? $a_1, a_2, ldots, a_{2010}$ ?and? $b_1, b_2, ldots, b_{2010}$ ?of the numbers? $1, 2, ldots, 2010$ ?are said to intersect if? $a_k = b_k$ ?for some value of? $k$ in the range? $1leq kleq 2010$ . Show that there exist? $1006$ ?permutations of the numbers? $1, 2, ldots, 2010$ ?such that any other such permutation is guaranteed to intersect at least one of these? $1006$ ?permutations.

Problem 6

Let? $ABC$ ?be a triangle with? $angle A = 90^{circ}$ . Points? $D$ ?and? $E$ ?lie on sides? $AC$ ?and? $AB$ , respectively, such that? $angle ABD = angle DBC$ ?and? $angle ACE = angle ECB$ . Segments? $BD$ ?and? $CE$ ?meet at? $I$ . Determine whether or not it is possible for segments? $AB, AC, BI, ID, CI, IE$ ?to all have integer lengths.

Problem 1

Solutions

We claim that the smallest? $n$ ?is? $67^2 = boxed{4489}$ .

Solution 1

Let? $S = {1, 4, 9, ldots}$ ?be the set of positive perfect squares. We claim that the relation? $R = {(j, k)in [n]times[n]mid jkin S}$ ?is an equivalence relation on? $[n]$ .

It is reflexive because? $k^2in S$ ?for all? $kin [n]$ .

It is symmetric because? $jkin Simplies kj = jkin S$ .

It is transitive because if? $jkin S$ ?and? $klin S$ , then? $jkcdot kl = jlk^2in Simplies jlin S$ , since? $S$ ?is closed under multiplication and a non-square times a square is always a non-square.

We are restricted to permutations for which? $ka_k in S$ , in other words to permutations that send each element of? $[n]$ ?into its equivalence class. Suppose there are? $N$ ?equivalence classes:? $C_1, ldots, C_N$ . Let? $n_i$ ?be the number of elements of? $C_i$ , then? $P(n) = prod_{i=1}^{N} n_i!$ .

Now? $2010 = 2cdot 3cdot 5cdot 67$ . In order that? $2010mid P(n)$ , we must have? $67mid n_m!$ ?for the class? $C_m$ ?with the most elements. This means? $n_mgeq 67$ , since no smaller factorial will have? $67$ ?as a factor. This condition is sufficient, since? $n_m!$ ?will be divisible by? $30$ ?for? $n_mgeq 5$ , and even more so? $n_mgeq 67$ .

The smallest element? $g_m$ ?of the equivalence class? $C_m$ ?is square-free, since if it were divisible by the square of a prime, the quotient would be a smaller element of? $C_m$ . Also, each prime? $p$ ?that divides? $g_m$ ?divides all the other elements? $k$ ?of? $C_m$ , since? $p^2mid kg_m$ ?and thus? $pmid k$ . Therefore? $g_mmid k$ ?for all? $kin C_m$ . The primes that are not in? $g_m$ ?occur an even number of times in each? $kin C_m$ .

Thus the equivalence class? $C_m = {g_mk^2leq n}$ . With? $g_m = 1$ , we get the largest possible? $n_m$ . This is just the set of squares in? $[n]$ , of which we need at least? $67$ , so? $ngeq 67^2$ . This condition is necessary and sufficient.

Solution 2

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? $n$ ?in the form? $pcdot m^2$ , where? $m^2$ ?is the largest perfect square dividing? $n$ , so? $p$ ?is not divisible by the square of any prime. Obviously, one working permutation of? $[n]$ ?is simply? $(1, 2, ldots, n)$ ; this is acceptable, as? $ka_k$ ?is always? $k^2$ ?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? $p$ .

Proof.?Let? $p_k$ ?and? $m_k$ ?be the values of? $p$ ?and? $m$ , respectively, for a given? $k$ ?as defined above, such that? $p$ ?is not divisible by the square of any prime. We can obviously permute two numbers which have the same? $p$ , since if? $p_j = p_w$ ?where? $j$ ?and? $w$ ?are 2 values of? $k$ , then? $jcdot w = p_j^2cdot m_j^2cdot m_w^2$ , which is a perfect square. This proves that we can permute any numbers with the same value of? $p$ .

End Lemma

Lemma 2.?We will prove the converse of Lemma 1: Let one number have a? $p$ ?value of? $phi$ ?and another,? $gamma$ .? $phicdot f$ ?and? $gammacdot g$ ?are both perfect squares.

Proof.? $phicdot f$ ?and? $gammacdot g$ ?are both perfect squares, so for? $phicdot gamma$ ?to be a perfect square, if? $g$ ?is greater than or equal to? $f$ ,? $g/f$ ?must be a perfect square, too. Thus? $g$ ?is? $f$ ?times a square, but? $g$ ?cannot divide any squares besides? $1$ , so? $g = 1f$ ;? $g = f$ . Similarly, if? $fgeq g$ , then? $f = g$ ?for our rules to keep working.

End Lemma

We can permute? $l$ ?numbers with the same? $p$ ?in? $l!$ ?ways. We must have at least 67 numbers with a certain? $p$ ?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? $h$ , in general, we need numbers all the way up to? $hcdot 67^2$ , so obviously,? $67^2$ ?is the smallest such number such that we can get a? $67!$ ?term; here 67? $p$ ?terms are 1. Thus we need the integers? $1, 2, ldots, 67^2$ , so? $67^2$ , or? $boxed{4489}$ , is the answer.

Solution Number Sense

We have to somehow calculate the number of permutations for a given? $n$ . How in the world do we do this? Because we want squares, why not call a number? $k=m*s^2$ , where? $s$ ?is the largest square that allows? $m$ ?to be non-square?? $m=1$ ?is the only square? $m$ ?can be, which only happens if? $k$ ?is a perfect square.

For example,? $126 = 14 * 3^2$ , therefore in this case? $k=126, m = 14, s = 3$ .

I will call a permutation of the numbers? $P$ , while the original? $1, 2, 3, 4, ...$ ?I will call? $S$ .

Note that essentially we are looking at "pairing up" elements between? $P$ ?and? $S$ ?such that the product of? $P_k$ ?and? $S_k$ ?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? $mod 2$ ?and if there are any odd numbers, those are the ones we have to match- in effect, they are the? $m$ ?numbers mentioned at the beginning.

By listing the? $m$ ?values, in my search for "dumb" or "obvious" ideas I am pretty confident that only values with identical? $m$ s can be matched together. With such a solid idea let me prove it.

If we were to "pair up" numbers with different? $m$ s, take for example? $S_{18}$ ?with an? $m$ ?of? $2$ ?and? $P_{18}=26$ ?with an? $m$ ?of? $26$ , note that their product gives a supposed? $m$ ?of? $13$ ?because the? $2$ ?values cancel out. But then, what happens to the extra? $13$ ?left? It doesn't make a square, contradiction. To finish up this easy proof, note that if a "pair" has different? $m$ ?values, and the smaller one is? $m_1$ , in order for the product to leave a square, the larger? $m$ ?value has to have not just? $m_1$ ?but another square inside it, which is absurd because we stipulated at the beginning that? $m$ ?was square-free except for the trivial multiplication identity, 1.

Now, how many ways are there to do this? If there are? $c_1$ ?numbers with? $m=1$ , there are clearly? $(c_1)!$ ?ways of sorting them. The same goes for? $m=2, 3, etc.$ ?by this logic. Note that the? $P(n)$ ?as stated by the problem requires a? $67$ ?thrown in there because? $2010=2*3*5*67$ , so there has to be a? $S_n$ ?with 67 elements with the same? $m$ . It is evident that the smallest? $n$ ?will occur when? $m=1$ , because if? $m$ ?is bigger we would have to expand? $n$ ?to get the same number of? $m$ ?values. Finally, realize that the only numbers with? $m=1$ ?are square numbers! So our smallest? $n=67^2=4489$ , 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!

Problem 2

Solution

The sequence is? $2, 4, 6, ldots, 2n-2$ .

Proof

We will prove that any sequence? $x_1, ldots, x_{n-1}$ , that satisfies the given conditions, is an arithmetic progression with? $x_1$ ?as both the first term and the increment. Once this is proved, condition (b) implies that? $x_1 + x_{n-1} = x_1 + (n-1)x_1 = nx_1 = 2n$ . Therefore? $x_1 = 2$ , and the sequence is just the even numbers from? $2$ ?to? $2n-2$ . The sequence of successive even numbers clearly satisfies all three conditions, and we are done.

First a degenerate case. If? $n = 2$ , there is only one element? $x_1$ , and condition (b) gives? $x_1 + x_1 = 4$ ?or? $x_1 = 2$ . Conditions (a) and (c) are vacuously true.

Otherwise, for? $n > 2$ , we will prove by induction on? $m$ ?that the difference? $x_{n-m} - x_{n-1-m} = x_1$ ?for all? $m in [1, n-2]$ , which makes all the differences? $x_{n-1} - x_{n-2} = ldots = x_2 - x_1 = x_1$ , i.e. the sequence is an arithmetic progression with? $x_1$ ?as the first term and increment as promised.

So first the? $m=1$ ?case. With? $n > 2$ ,? $x_{n-2}$ ?exists and is less than? $x_{n-1}$ ?by condition (a). Now since by condition (b)? $x_1 + x_{n-1} = 2n$ , we conclude that? $x_1 + x_{n-2} < 2n$ , and therefore by condition (c)? $x_1 + x_{n-2} = x_k$ ?for some? $k$ . Now, since? $x_1 > 0$ ,? $x_k > x_{n-2}$ ?and can only be? $x_{n-1}$ . So? $x_1 + x_{n-2} = x_{n-1}$ .

Now for the induction step on all values of? $m$ . Suppose we have shown that for all? $i le m$ ,? $x_1 + x_{n-1-i} = x_{n-i}$ . If? $m = n-2$ ?we are done, otherwise? $m < n-2$ , and by condition (c)? $x_1 + x_{n-2-m} = x_k$ ?for some? $k$ . This? $x_k$ ?is larger than? $x_{n-2-m}$ , but smaller than? $x_1 + x_{n-1-m} = x_{n-m}$ ?by the inductive hypothesis. It then follows that? $x_1 + x_{n-2-m} = x_{n-1-m}$ , the only element of the sequence between? $x_{n-2-m}$ ?and? $x_{n-m}$ . This establishes the result for? $i=m+1$ .

So, by induction? $x_1 + x_{n-1-m} = x_{n-m}$ ?for all? $m in [1, n-2]$ , which completes the proof.

Solution 2

The claim is that in this sequence, if there are? $2$ ?elements? $a,b$ ?where? $a,b<n$ , such that? $gcd(a,b)=1$ , then the sequence contains every number less than? $2n$ .

Proof: Let? $a$ ?and? $b$ ?be the numbers less than? $n$ ?such that? $gcd(a,b)=1$ . We take this sequence modulo? $n$ . This means that if? $x_i$ ?is an element in this sequence then? $-x_i$ ?is as well.? $a,b,2n-a,2n-b$ ?are all elements in the sequence. Clearly, one of? $2n-a+b$ ?and? $2n-b+a$ ?is less than? $2n$ , which means that? $pm (a-b)$ ?are in this sequence modulo? $n$ . Now we want to show every number is achievable. We have already established that? $a$ ?and? $b$ ?are relatively prime, so by euclidean algorithm, if we take the positive difference of? $a'$ ?and? $b'$ ?every time, we will get that? $1$ ?is in our sequence. Then, we can simply add or subtract? $1$ ?as many times from? $a$ ?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? $n-1$ ?terms, our sequence must be one of? $2,4,6,..,2(n-1)$ ?or? $1,3,5,...$ , the latter obviously fails, so? $2,4,6...2(n-1)$ ?is our only possible sequence.

Problem 3

Solution 1

Let? $alpha = angle BAZ$ ,? $beta = angle ABX$ . Since? $XY$ ?is a chord of the circle with diameter? $AB$ ,? $angle XAY = angle XBY = gamma$ . From the chord? $YZ$ , we conclude? $angle YAZ = angle YBZ = delta$ .

$[asy] import olympiad; // Scale unitsize(1inch); real r = 1.75; // Semi-circle: centre O, radius r, diameter A--B. pair O = (0,0); dot(O); label("$O$", O, plain.S); pair A = r * plain.W; dot(A); label("$A$", A, unit(A)); pair B = r * plain.E; dot(B); label("$B$", B, unit(B)); draw(arc(O, r, 0, 180)--cycle); // points X, Y, Z real alpha = 22.5; real beta = 15; real delta = 30; pair X = r * dir(180 - 2*beta); dot(X); label("$X$", X, unit(X)); pair Y = r * dir(2*(alpha + delta)); dot(Y); label("$Y$", Y, unit(Y)); pair Z = r * dir(2*alpha); dot(Z); label("$Z$", Z, unit(Z)); // Feet of perpendiculars from Y pair P = foot(Y, A, X); dot(P); label("$P$", P, unit(P-Y)); dot(P); pair Q = foot(Y, B, X); dot(P); label("$Q$", Q, unit(A-Q)); dot(Q); pair R = foot(Y, B, Z); dot(R); label("$S$", R, unit(R-Y)); dot(R); pair S = foot(Y, A, Z); dot(S); label("$R$", S, unit(B-S)); dot(S); pair T = foot(Y, A, B); dot(T); label("$T$", T, unit(T-Y)); dot(T); // Segments draw(B--X); draw(B--Y); draw(B--R); draw(A--Z); draw(A--Y); draw(A--P); draw(Y--P); draw(Y--Q); draw(Y--R); draw(Y--S); draw(R--T); draw(P--T); // Right angles draw(rightanglemark(A, X, B, 3)); draw(rightanglemark(A, Y, B, 3)); draw(rightanglemark(A, Z, B, 3)); draw(rightanglemark(A, P, Y, 3)); draw(rightanglemark(Y, R, B, 3)); draw(rightanglemark(Y, S, A, 3)); draw(rightanglemark(B, Q, Y, 3)); // Acute angles import markers; void langle(pair A, pair B, pair C, string l="", real r=40, int n=1, int nm = 0) { string sl = "$scriptstyle{" + l + "}$"; marker m = (nm > 0)?? marker(markinterval(stickframe(n=nm, 2mm), true))?: nomarker; markangle(Label(sl), radius=r, n=n, A, B, C, m); } langle(B, A, Z, "alpha" ); langle(X, B, A, "beta", n=2); langle(Y, A, X, "gamma", nm=1); langle(Y, B, X, "gamma", nm=1); langle(Z, A, Y, "delta", nm=2); langle(Z, B, Y, "delta", nm=2); langle(R, S, Y, "alpha+delta", r=23); langle(Y, Q, P, "beta+gamma", r=23); langle(R, T, P, "chi", r=15); [/asy]$ Triangles? $BQY$ ?and? $APY$ ?are both right-triangles, and share the angle? $gamma$ , therefore they are similar, and so the ratio? $PY?: YQ = AY?: YB$ . Now by?Thales' theorem?the angles? $2010 USAJMO Problems真题及答案$ ?are all right-angles. Also,? $angle PYQ$ , being the fourth angle in a quadrilateral with 3 right-angles is again a right-angle. Therefore? $triangle PYQ sim triangle AYB$ ?and? $angle YQP = angle YBA = gamma + beta$ . Similarly,? $RY?: YS = AY?: YB$ , and so? $angle YRS = angle YAB = alpha + delta$ .

Now? $RY$ ?is perpendicular to? $AZ$ ?so the direction? $RY$ ?is? $alpha$ ?counterclockwise from the vertical, and since? $angle YRS = alpha + delta$ ?we see that? $SR$ ?is? $delta$ ?clockwise from the vertical. (Draw an actual vertical line segment if necessary.)

Similarly,? $QY$ ?is perpendicular to? $BX$ ?so the direction? $QY$ ?is? $beta$ ?clockwise from the vertical, and since? $angle YQP$ ?is? $gamma + beta$ ?we see that? $QY$ ?is? $gamma$ counterclockwise from the vertical.

Therefore the lines? $PQ$ ?and? $RS$ ?intersect at an angle? $chi = gamma + delta$ . Now by the central angle theorem? $2gamma = angle XOY$ ?and? $2delta = angle YOZ$ , and so? $2(gamma + delta) = angle XOZ$ , and we are done.

Note that? $RTQY$ ?is a quadrilateral whose angles sum to 360°; can you find a faster approach using this fact?

Footnote

We can prove a bit more. Namely, the extensions of the segments? $RS$ ?and? $PQ$ ?meet at a point on the diameter? $AB$ ?that is vertically below the point? $Y$ .

Since? $YS = AY sin(delta)$ ?and is inclined? $alpha$ ?counterclockwise from the vertical, the point? $S$ ?is? $AY sin(delta) sin(alpha)$ ?horizontally to the right of? $Y$ .

Now? $AS = AY cos(delta)$ , so? $S$ ?is? $AS sin(alpha) = AY cos(delta)sin(alpha)$ ?vertically above the diameter? $AB$ . Also, the segment? $SR$ ?is inclined? $delta$ clockwise from the vertical, so if we extend it down from? $S$ ?towards the diameter? $AB$ ?it will meet the diameter at a point which is? $AY cos(delta)sin(alpha)tan(delta) = AY sin(delta)sin(alpha)$ ?horizontally to the left of? $S$ . This places the intersection point of? $RS$ ?and? $AB$ ?vertically below? $Y$ .

Similarly, and by symmetry the intersection point of? $PQ$ ?and? $AB$ ?is directly below? $Y$ ?on? $AB$ , so the lines through? $PQ$ ?and? $RS$ ?meet at a point? $T$ ?on the diameter that is vertically below? $Y$ .

Footnote to the Footnote

The Footnote's claim is more easily proved as follows.

Note that because? $angle{QPY}$ ?and? $angle{YAB}$ ?are both complementary to? $beta + gamma$ , they must be equal. Now, let? $PQ$ ?intersect diameter? $AB$ ?at? $T'$ . Then? $PYT'A$ ?is cyclic and so? $angle{YT'A} = 180^circ - angle{APY} = 90^circ$ . Hence? $T'YSB$ ?is cyclic as well, and so we deduce that? $angle{YST'} = angle{YBT'} = 90^circ - alpha - delta = angle{YSR}.$ ?Hence? $S, R, T'$ ?are collinear and so? $T = T'$ . This proves the Footnote.

Footnote to the Footnote to the Footnote

The Footnote's claim can be proved even more easily as follows.

Drop an altitude from? $Y$ ?to? $AB$ ?at point? $T$ . Notice that? $P, Q, T$ ?are collinear because they form the Simson line of? $triangle AXB$ ?from? $Y$ . Also notice that? $P, Q, T$ ?are collinear because they form the Simson line of? $triangle AZB$ ?from? $Y$ . Since? $T$ ?is at the diameter? $AB$ , lines? $PQ$ ?and? $SR$ must intersect at the diameter.

Another footnote

There is another, more simpler solution using Simson lines. Can you find it?

Operation Diagram

Of course, as with any geometry problem, DRAW A HUGE DIAGRAM spanning at least one page. And label all your right angles, noting? $rectangles PXQY$ ?and? $YSZR$ . It looks like there are a couple of key angles we need to diagram. Let's take? $angle{ZAB} = alpha, angle{XBA} = beta, angle{YAZ} = angle{YBZ} = delta$ . From there? $angle{XOZ}=180^circ - angle{XOA}-angle{ZOB}=180-2(beta + alpha)$ .

Move on to the part about the intersection of? $PQ$ ?and? $RS$ . Call the intersection? $J$ . Note that by Simson Lines from point? $Y$ ?to? $triangle{ABX}$ ?and? $triangle{AZB}$ ,? $YJ$ ?is perpendicular to? $AB$ ?and? $J$ ?lies on? $AB$ . Immediately note that we are trying to show that? $angle{PJS} = 90 - beta - alpha$ .

It suffices to show that referencing quadrilateral? $QR~J$ , where? $~$ ?represents the intersection of? $XB, AZ$ , we have reflex? $angle{Q~R} + angle{BQJ} + angle{ARJ} = 270 + alpha + beta$ . Note that the reflex angle is? $180^circ + angle{A~X} = 180^circ + (90^circ - angle{XA*}) = 270^circ - ((90 - beta) - alpha) = 180 ^circ + alpha + beta$ , therefore it suffices to show that? $angle{BQJ} + angle{ARJ} = 90^circ$ . To make this proof more accessible, note that via (cyclic) rectangles? $PXQY$ ?and? $YSZR$ , it suffices to prove? $angle{YPJ} + angle{YSJ} = 90^circ$ .

Note? $angle{YPJ} = angle{YPQ} = angle{YXQ} = angle{YXB} = angle{YAB} = alpha + delta$ . Note? $angle{YSJ} = angle{YSR} = angle{YZR} = angle{YZA} = angle{YBA} = angle{YBX} + angle{XBA} = ((90^circ - alpha) - delta - beta) + beta = 90^circ - alpha - delta$ , which completes the proof.

Footnote to Operation Diagram

For reference/feasibility records: took expiLnCalc ~56 minutes (consecutively). During the problem expiLnCalc realized that the inclusion of? $delta$ was necessary when trying to show that? $angle{YSJ}+angle{YPJ}=90^circ$ . Don't be afraid to attempt several different strategies, and always be humble!

Solution 2

$[asy] currentpicture=new picture; size(12cm); pair O, A, B, X, Y, Z, P, Q, R, SS, T; O=(0, 0); A=(-1, 0); B=(1, 0); X=(Cos(144), Sin(144)); Y=(Cos(105), Sin(105)); Z=(Cos(27), Sin(27)); P=foot(Y, A, X); Q=foot(Y, B, X); R=foot(Y, A, Z); SS=foot(Y, B, Z); T=foot(Y, A, B); dot(O); dot(A); dot(B); dot(X); dot(Y); dot(Z); dot(P); dot(Q); dot(R); dot(SS); dot(T); draw(arc(O, 1, 0, 180)); draw(circumcircle(T, A, Y), dotted); draw(circumcircle(T, B, Y), dotted); draw(A -- B); draw(Z -- O -- X -- A -- Z -- B -- X); draw(A -- Y -- B); draw(P -- T -- SS); draw(P -- Y -- Q); draw(R -- Y -- SS); draw(X -- P); draw(Z -- SS); draw(Y -- T); draw(rightanglemark(Y, T, B, 1.25)); draw(rightanglemark(Y, P, A, 1.25)); draw(rightanglemark(Y, Q, X, 1.25)); draw(rightanglemark(Y, R, Z, 1.25)); draw(rightanglemark(Y, SS, B, 1.25)); draw(rightanglemark(A, X, B, 1.25)); draw(rightanglemark(A, Y, B, 1.25)); draw(rightanglemark(A, Z, B, 1.25)); label("$O$", O, S); label("$A$", A, SW); label("$B$", B, SE); label("$X$", X, (X-B)/length(X-B)); label("$Y$", Y, Y); label("$Z$", Z, (Z-A)/length(Z-A)); label("$P$", P, (P-T)/length(P-T)); label("$Q$", Q, SW); label("$R$", R, SE); label("$S$", SS, (SS-T)/length(SS-T)); label("$T$", T, S); [/asy]$

Let? $T$ ?be the projection of? $Y$ ?onto? $overline{AB}$ . Notice that? $T$ ?lies on the Simson Line? $overline{PQ}$ ?from? $Y$ ?to? $triangle AXB$ , and the Simson Line? $overline{RS}$ ?from? $Y$ ?to? $triangle AZB$ . Hence,? $T=overline{PQ}capoverline{RS}$ , so it suffices to show that? $angle PTS=tfrac{1}{2}angle XOZ$ .

Since? $TAPY$ ?and? $TBSY$ ?are cyclic quadrilaterals, $[angle PTS=angle PTY+angle YTS=angle PAY+angle YBS=angle XAY+angle YBZ=frac{1}{2}angle XOY+frac{1}{2}angle YOZ=frac{1}{2}angle XOZ,]$ as required.

Problem 4

Solution

Let the vertices of the triangle be? $(a, a^2), (b, b^2), (c, c^2)$ . The area of the triangle is the absolute value of? $A$ ?in the equation:

$[A = frac{1}{2}detleftvert begin{array}{c c} b-a & c - a\ b^2 - a^2 & c^2 - a^2 end{array}rightvert = frac{(b-a)(c-a)(c-b)}{2}]$ If we choose? $a < b < c$ ,? $A > 0$ ?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? $a$ ,? $b$ ?and? $c$ . Thus, all possible areas can be obtained with? $a = 0$ , in which case? $A = frac{1}{2}bc(c-b)$ .

If a particular choice of? $b$ ?and? $c$ ?gives an area? $A = (2^nm)^2$ , with? $n$ ?a positive integer and? $m$ ?a positive odd integer, then setting? $b' = 4b$ ,? $c' = 4c$ ?gives an area? $A' = 4^3 A = 8^2 A = (2^{n+3}m)^2$ .

Therefore, if we can find solutions for? $n = 0$ ,? $n = 1$ ?and? $n = 2$ , all other solutions can be generated by repeated multiplication of? $b$ ?and? $c$ ?by a factor of? $4$ .

Setting? $b=1$ ?and? $c=2$ , we get? $A=1 = (2^0cdot1)^2$ , which yields the? $n=0$ ?case.

Setting? $b=1$ ?and? $c=9$ , we get? $A = 9cdot4 = (2^1cdot3)^2$ , which yields the? $n=1$ ?case.

Setting? $b=1$ ?and? $c=5$ , we get? $A=1cdot2cdot5 = 10$ . Multiplying these values of? $b$ ?and? $c$ ?by? $10$ , we get? $b'=10$ ,? $c'=50$ ,? $A'=10cdot20cdot50 = 100^2 = (2^2cdot5^2)^2$ , which yields the? $n=2$ ?case. This completes the construction.

Solution 2

We proceed via induction on n. Notice that we prove instead a stronger result: there exists a parabolic triangle with area? $(2^nm)^2$ ?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 =? $36^2$ , so n = 2 and m = 9.

Inductive step: If n = k produces parabolic triangle ABC with A(a,? $a^2$ ), B(b,? $b^2$ ), and C(-b,? $b^2$ ), consider A'B'C' with vertices A(4a,? $16a^2$ ), B(4b,? $16b^2$ ), and C(-4b,? $16b^2$ ). If ABC has area? $(2^km)^2$ , then A'B'C' has area? $(2^{k+3}m)^2$ , 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? $(2^nm)^2$ ?with two vertices sharing the same ordinate. The problem statement is a direct result of this result.

Solution 3 (without induction)

First, consider triangle with vertices? $(0,0)$ ,? $(1,1)$ ,? $(-1,1)$ . This has area? $1$ ?so? $n=0$ ?case is satisfied.

Then, consider triangle with vertices? $(a,a^2), (-a,a^2), (b,b^2)$ , and set? $a=2^{2n}$ ?and? $b=2^{4n-2}+1$ . The area of this triangle is? $frac{1}{2}bh=a(b^2-a^2)$ . We have that? $b^2-a^2=2^{8n-4}+2^{4n-1}+1-2^{4n}=2^{8n-4}-2^{4n-1}+1=(2^{4n-2}-1)^2$ ?We desire? $A=a(b^2-a^2)=2^{2n}m^2$ , or? $2^{4n-1}-1=m$ , and? $m$ ?is clearly always odd for positive? $n$ , completing the proof.

Problem 5

Solution

Let? $n$ ?be a positive integer. Let? $m$ ?be the smallest positive integer with? $m > n - m$ . Since? $n > n - n = 0$ ,? $m le n$ . Let? $N = {1, ldots, n}$ ?be the set of positive integers from? $1$ ?to? $n$ . Let? $M subset N$ , be? $M = {1, ldots, m}$ .

Let? $P_n$ ?be the set of of permutations of? $N$ .

Let? $C_m$ ?be the set of cyclic permutations of? $M$ , there are? $m$ ?cyclic permutations in all, and? $C_m$ ?acts transitively on? $M$ , i.e. for every pair of elements? $a,b in M$ , there is an element of? $C_m$ ?that maps? $a$ ?to? $b$ .

Let? $C'_m subset P_n$ ?be the permutations in? $P_n$ ?that leave? $Nsetminus M$ ?fixed, and restricted to? $M$ ?yield one of the permutations in? $C_m$ . There is a natural one-to-one correspondence between? $C'_m$ ?and? $C_m$ .

We claim that the? $m$ ?permutations? $C'_m$ ?intersect every permutation in? $P_n$ .

Suppose, to the contrary, that there exists a permutation? $p in P_n$ ?that does not intersect any permutation in? $C'_m$ . Since? $C'_m$ ?acts transitively on? $M subset N$ ?the permutation? $p$ ?cannot send any element of? $M$ ?to any other element of? $M$ , therefore it must send all the elements of? $M$ ?to? $Nsetminus M$ , but since? $Nsetminus M$ ?has? $n - m$ ?elements and? $m > n - m$ , this is impossible by the pigeonhole principle. Therefore such a permutation cannot exist, and the permutations in? $C'_m$ ?intersect every permutation in? $P_n$ .

For? $n = 2010$ ?we get? $m = 1006$ , which is the required special case of the general result above.

Problem 6

Solution

We know that angle? $BIC = 135^{circ}$ , as the other two angles in triangle? $BIC$ ?add to? $45^{circ}$ . Assume that only? $AB, AC, BI$ , and? $CI$ ?are integers. Using the?Law of Cosines?on triangle BIC,

$[asy] import olympiad; // Scale unitsize(1inch); // Shape real h = 1.75; real w = 2.5; // Points void ldot(pair p, string l, pair dir=p) { dot(p); label(l, p, unit(dir)); } pair A = origin; ldot(A, "$A$", plain.SW); pair B = w * plain.E; ldot(B, "$B$", plain.SE); pair C = h * plain.N; ldot(C, "$C$", plain.NW); pair D = extension(B, bisectorpoint(C, B, A), A, C); ldot(D, "$D$", D-B); pair E = extension(C, bisectorpoint(A, C, B), A, B); ldot(E, "$E$", E-C); pair I = extension(B, D, C, E); ldot(I, "$I$", A-I); // Segments draw(A--B); draw(B--C); draw(C--A); draw(C--E); draw(B--D); // Angles import markers; draw(rightanglemark(B, A, C, 4)); markangle(Label("$scriptstyle{frac{theta}{2}}$"), radius=40, I, B, E); markangle(Label("$scriptstyle{frac{theta}{2}}$"), radius=40, C, B, I); markangle(Label("$scriptstyle{frac{pi}{4} - frac{theta}{2}}$"), radius=40, I, C, B); markangle(Label("$scriptstyle{frac{pi}{4} - frac{theta}{2}}$"), radius=40, D, C, I); markangle(Label("$scriptstyle{frac{3pi}{4}}$"), radius=10, B, I, C); [/asy]$ $BC^2 = BI^2 + CI^2 - 2BIcdot CI cdot cos 135^{circ}$ . Observing that? $BC^2 = AB^2 + AC^2$ ?is an integer and that? $cos 135^{circ} = -frac{sqrt{2}}{2},$ ?we have

$[BC^2 - BI^2 - CI^2 = BIcdot CIcdot sqrt{2}]$ and therefore,

$[sqrt{2} = frac{BC^2 - BI^2 - CI^2}{BIcdot CI}]$ The LHS ( $sqrt{2}$ ) 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? $AB, AC, BI$ , and? $CI$ ?to all be integers, which invalidates the original claim that all six lengths are integers, and we are done.

Solution 2

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? $AB$ ?and? $AC$ ?are relatively-prime integers and the lengths of the segments? $BI, ID, CI, IE$ ?are all rational (we divide all the lengths by the? $gcd(AB, AC)$ ?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? $AB$ ?and? $AC$ ?are relatively-prime integers and the lengths? $IB, ID, CI, IE$ ?are all rational.

Since? $CE$ ?is the bisector of? $angle ACB$ , by the angle bisector theorem, the ratio? $IB?: ID = CB?: CD$ , and since? $BD$ ?is the bisector of? $angle ABC$ ,? $CB?: CD = (AB + BC)?: AC$ . Therefore,? $IB?: ID = (AB + BC)?: AC$ . Now? $IB?: ID$ ?is by assumption rational, so? $(AB + BC)?: AC$ ?is rational, but? $AB$ ?and? $AC$ ?are assumed integers so? $BC?: AC$ ?must also be rational. Since? $BC$ ?is the hypotenuse of a right-triangle, its length is the square root of an integer, and thus either an integer or irrational, so? $BC$ ?must be an integer.

With? $AB$ ?and? $AC$ ?relatively-prime, we conclude that the side lengths of? $triangle ABC$ ?must be a Pythagorean triple:? $(2pq, p^2 - q^2, p^2 + q^2)$ , with? $p > q$ ?relatively-prime positive integers and? $p+q$ ?odd.

Without loss of generality,? $AC = 2pq, AB = p^2 - q^2, BC = p^2+q^2$ . By the angle bisector theorem,

$begin{align*} AE &= dfrac{AB cdot AC}{AC + CB} = dfrac{2pq(p^2-q^2)}{p^2 + q^2 + 2pq} = dfrac{2pq(p-q)}{p+q} end{align*}$ Since? $triangle CAE$ ?is a right-triangle, we have:

$begin{align*} CE^2 &= AC^2 + AE^2 = 4p^2q^2 + left(dfrac{2pq(p-q)}{p+q}right)^2 = 4p^2q^2left[1 + left(dfrac{p-q}{p+q}right)^2right] \ &= frac{4p^2q^2}{(p+q)^2}left[(p+q)^2 + (p-q)^2right] = frac{4p^2q^2}{(p+q)^2}(2p^2 + 2q^2) end{align*}$ and so? $CE$ ?is rational if and only if? $2p^2 + 2q^2$ ?is a perfect square.

Also by the angle bisector theorem,

$begin{align*} AD &= dfrac{AB cdot AC}{AB + BC} = dfrac{2pq(p^2-q^2)}{p^2 + q^2 + p^2 - q^2} = dfrac{q(p^2-q^2)}{p} end{align*}$ and therefore, since? $triangle DAB$ ?is a right-triangle, we have:

$begin{align*} BD^2 &= AB^2 + AD^2 = (p^2-q^2)^2 + left(dfrac{q(p^2-q^2)}{p}right)^2 \ &= (p^2-q^2)^2left[1 + frac{q^2}{p^2}right] = frac{(p^2-q^2)^2}{p^2}(p^2 + q^2) end{align*}$ and so? $BD$ ?is rational if and only if? $p^2 + q^2$ ?is a perfect square.

Combining the conditions on? $CE$ ?and? $BD$ , we see that? $2p^2+2q^2$ ?and? $p^2+q^2$ ?must both be perfect squares. If it were so, their ratio, which is? $2$ , would be the square of a rational number, but? $sqrt{2}$ ?is irrational, and so the assumed triangle cannot exist.