2022 AIME I Solutions

Scroll down to view professionally curated solutions from LIVE by Po-Shen Loh, print PDF solutions, view answer key, or take the full timed exam.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

1.

Quadratic polynomials P(x)P(x) and Q(x)Q(x) have leading coefficients of 22 and 2,-2, respectively. The graphs of both polynomials pass through the two points (16,54)(16, 54) and (20,53).(20, 53). Find P(0)+Q(0).P(0) + Q(0).

Concepts:polynomiallinear equation
Difficulty rating: 1890
Small Hint:

Consider R(x)=P(x)+Q(x):R(x) = P(x) + Q(x): the quadratic terms cancel, so RR is linear

Big Hint:

RR passes through (16,108)(16, 108) and (20,106);(20, 106); extend that line back to x=0x = 0

Solution:

Let R(x)=P(x)+Q(x).R(x) = P(x) + Q(x). The leading coefficients 22 and 2-2 cancel, so RR is a linear function. Since both graphs pass through (16,54)(16, 54) and (20,53),(20, 53), we get R(16)=108R(16) = 108 and R(20)=106.R(20) = 106.

The slope of RR is 1061082016=12,\frac{106 - 108}{20 - 16} = -\frac{1}{2}, so P(0)+Q(0)=R(0)=R(16)+1612=108+8=116. \begin{aligned} P(0) + Q(0) &= R(0) \\ &= R(16) + 16 \cdot \frac{1}{2} \\ &= 108 + 8 = 116. \end{aligned}

2.

Find the three-digit positive integer abc\underline{a}\,\underline{b}\,\underline{c} whose representation in base nine is bca,\underline{b}\,\underline{c}\,\underline{a}, where a,a, b,b, and cc are (not necessarily distinct) digits.

Difficulty rating: 1950
Small Hint:

Write the condition as 100a+10b+c=81b+9c+a100a + 10b + c = 81b + 9c + a and simplify

Big Hint:

From 99a=71b+8c,99a = 71b + 8c, reduce modulo 88 to pin down bb in terms of a,a, then test small values of a.a.

Solution:

The condition says 100a+10b+c=81b+9c+a,100a + 10b + c = 81b + 9c + a, which simplifies to 99a=71b+8c.99a = 71b + 8c. Since the digits also appear in a base-nine numeral, each is at most 8.8. Reducing modulo 88 gives 3ab(mod8),3a \equiv -b \pmod 8, so b5a(mod8).b \equiv 5a \pmod 8.

For a=1,a = 1, b=5b = 5 makes 71b71b exceed 99;99; for a=2,a = 2, b=2b = 2 gives 8c=198142=56,8c = 198 - 142 = 56, so c=7.c = 7. For each a3,a \ge 3, the required bb forces 99a71b99a - 71b outside the range [0,64],[0, 64], so there is no other solution.

The number is 227,227, and indeed 227=281+79+2227 = 2 \cdot 81 + 7 \cdot 9 + 2 =2729.= 272_9.

3.

In isosceles trapezoid ABCD,ABCD, parallel bases AB\overline{AB} and CD\overline{CD} have lengths 500500 and 650,650, respectively, and AD=BC=333.AD = BC = 333. The angle bisectors of A\angle A and D\angle D meet at P,P, and the angle bisectors of B\angle B and C\angle C meet at Q.Q. Find PQ.PQ.

Difficulty rating: 2390
Small Hint:

Let the bisector of A\angle A meet CD\overline{CD} at A:A': alternate interior angles make triangle ADAADA' isosceles with DA=333DA' = 333

Big Hint:

In isosceles triangle ADA,ADA', the bisector from DD is also the median, so PP is the midpoint of AA.AA'. Do the same for QQ and use coordinates.

Solution:

Let the bisector of A\angle A meet CD\overline{CD} at A.A'. Since ABCD,\overline{AB} \parallel \overline{CD}, we have DAA=AAB=AAD,\angle DA'A = \angle A'AB = \angle A'AD, so triangle ADAADA' is isosceles with DA=DA=333.DA' = DA = 333. The bisector of D\angle D is then the median from DD in this triangle, so P,P, which lies on both bisectors, is the midpoint of AA.\overline{AA'}. Symmetrically, QQ is the midpoint of BB,\overline{BB'}, where BB' is on CD\overline{CD} with CB=333.CB' = 333.

Place D=(0,0)D = (0, 0) and C=(650,0),C = (650, 0), so A=(75,h)A = (75, h) and B=(575,h)B = (575, h) for the appropriate height h.h. Then A=(333,0)A' = (333, 0) and B=(650333,0)=(317,0),B' = (650 - 333, 0) = (317, 0), so P=(75+3332,h2)=(204,h2), \begin{aligned} P &= \left(\frac{75 + 333}{2}, \frac{h}{2}\right) \\ &= \left(204, \frac{h}{2}\right), \end{aligned} Q=(575+3172,h2)=(446,h2). \begin{aligned} Q &= \left(\frac{575 + 317}{2}, \frac{h}{2}\right) \\ &= \left(446, \frac{h}{2}\right). \end{aligned}

Therefore PQ=446204=242.PQ = 446 - 204 = 242.

4.

Let w=3+i2w = \frac{\sqrt{3} + \mathrm{i}}{2} and z=1+i32,z = \frac{-1 + \mathrm{i}\sqrt{3}}{2}, where i=1.\mathrm{i} = \sqrt{-1}. Find the number of ordered pairs (r,s)(r, s) of positive integers not exceeding 100100 that satisfy the equation iwr=zs.\mathrm{i} \cdot w^r = z^s.

Difficulty rating: 2300
Small Hint:

Both numbers lie on the unit circle: ww has argument 3030^\circ and zz has argument 120,120^\circ, while i\mathrm{i} has argument 9090^\circ

Big Hint:

Matching arguments gives 90+30r120s(mod360),90 + 30r \equiv 120s \pmod{360}, i.e. r+34s(mod12);r + 3 \equiv 4s \pmod{12}; count how many r[1,100]r \in [1, 100] hit each residue

Solution:

Both ww and zz have modulus 1:1: in polar form w=cis30w = \operatorname{cis} 30^\circ and z=cis120,z = \operatorname{cis} 120^\circ, while i=cis90.\mathrm{i} = \operatorname{cis} 90^\circ. The equation iwr=zs\mathrm{i} \cdot w^r = z^s is therefore a statement about arguments: 90+30r120s(mod360),90 + 30r \equiv 120s \pmod{360}, i.e. r+34s(mod12).r + 3 \equiv 4s \pmod{12}.

For each s,s, this determines r(mod12):r \pmod{12}: the residue 4s34s - 3 is 1,1, 5,5, or 99 modulo 1212 according as s1,s \equiv 1, 2,2, or 0(mod3).0 \pmod 3. Among 1r1001 \le r \le 100 there are 99 values with r1(mod12)r \equiv 1 \pmod{12} and 88 values each with r5r \equiv 5 or r9(mod12).r \equiv 9 \pmod{12}. Among 1s1001 \le s \le 100 there are 3434 values with s1(mod3)s \equiv 1 \pmod 3 and 3333 values in each of the other two classes.

The count is 34934 \cdot 9 +338+ 33 \cdot 8 +338+ 33 \cdot 8 =306+264+264=834.= 306 + 264 + 264 = 834.

5.

A straight river that is 264264 meters wide flows from west to east at a rate of 1414 meters per minute. Melanie and Sherry sit on the south bank of the river with Melanie a distance of DD meters downstream from Sherry. Relative to the water, Melanie swims at 8080 meters per minute, and Sherry swims at 6060 meters per minute. At the same time, Melanie and Sherry begin swimming in straight lines to a point on the north bank of the river that is equidistant from their starting positions. The two women arrive at this point simultaneously. Find D.D.

Difficulty rating: 2390
Small Hint:

The meeting point is due north of the midpoint between them. Each swimmer’s velocity relative to the water is her ground velocity minus the current (14,0).(14, 0).

Big Hint:

With u=D2t,u = \frac{D}{2t}, subtracting the two speed equations gives (u+14)2(u14)2(u + 14)^2 - (u - 14)^2 =64003600= 6400 - 3600

Solution:

Put Sherry at the origin and Melanie at (D,0)(D, 0) on the south bank. A point on the north bank equidistant from both is (D2,264).\left(\frac{D}{2}, 264\right). If both arrive at time t,t, then each swimmer’s velocity relative to the water is her ground velocity minus the current (14,0),(14, 0), so (D2t14)2+(264t)2=602, \begin{aligned} &\left(\frac{D}{2t} - 14\right)^2 \\ &\quad {}+ \left(\frac{264}{t}\right)^2 = 60^2, \end{aligned} (D2t14)2+(264t)2=802. \begin{aligned} &\left(-\frac{D}{2t} - 14\right)^2 \\ &\quad {}+ \left(\frac{264}{t}\right)^2 = 80^2. \end{aligned}

Subtracting, with u=D2t:u = \frac{D}{2t}: (u+14)2(u14)2(u + 14)^2 - (u - 14)^2 =56u= 56u =64003600= 6400 - 3600 =2800,= 2800, so u=50.u = 50. Substituting back, (5014)2+(264t)2=3600(50 - 14)^2 + \left(\frac{264}{t}\right)^2 = 3600 gives 264t=48,\frac{264}{t} = 48, so t=112.t = \frac{11}{2}.

Therefore D=2ut=100t=550.D = 2ut = 100t = 550.

6.

Find the number of ordered pairs of integers (a,b)(a, b) such that the sequence 3,4,5,a,b,30,40,503, 4, 5, a, b, 30, 40, 50 is strictly increasing and no set of four (not necessarily consecutive) terms forms an arithmetic progression.

Difficulty rating: 2560
Small Hint:

Count the bad pairs among the (242)\binom{24}{2} choices with 5<a<b<30:5 \lt a \lt b \lt 30: every four-term progression must use aa or bb

Big Hint:

Beyond a=6a = 6 and 20{a,b},20 \in \{a, b\}, exactly three pairs (a,b)(a, b) complete a progression with two of the fixed terms. Watch for double counting.

Solution:

The sequence is increasing exactly when 5<a<b<30,5 \lt a \lt b \lt 30, giving (242)=276\binom{24}{2} = 276 pairs. The six fixed terms contain no four-term arithmetic progression, so every progression must involve aa or b.b. If only one of them is involved, three fixed terms must already be in progression: 3,4,53, 4, 5 extends only by 6,6, and 30,40,5030, 40, 50 extends only by 20.20. So the single-variable violations are a=6a = 6 (2323 pairs) and 20{a,b}20 \in \{a, b\} (2323 pairs), which overlap in the pair (6,20).(6, 20).

If both aa and bb are involved, two fixed terms complete the progression. Checking the possible positions: (4,5,a,b)(4, 5, a, b) gives (6,7);(6, 7); (3,5,a,b)(3, 5, a, b) gives (7,9);(7, 9); (3,a,b,30)(3, a, b, 30) gives (12,21);(12, 21); (4,a,b,40)(4, a, b, 40) gives (16,28);(16, 28); (5,a,b,50)(5, a, b, 50) gives (20,35),(20, 35), out of range; and (a,b,30,40)(a, b, 30, 40) gives (10,20).(10, 20). Of these, (6,7)(6, 7) and (10,20)(10, 20) are already counted, so (7,9),(7, 9), (12,21),(12, 21), and (16,28)(16, 28) are the only new bad pairs.

The number of valid pairs is 276(23+231)276 - (23 + 23 - 1) 3=27648=228.- 3 = 276 - 48 = 228.

7.

Let a,a, b,b, c,c, d,d, e,e, f,f, g,g, h,h, ii be distinct integers from 11 to 9.9. The minimum possible positive value of abcdefghi\frac{a \cdot b \cdot c - d \cdot e \cdot f}{g \cdot h \cdot i} can be written as mn,\frac{m}{n}, where mm and nn are relatively prime positive integers. Find m+n.m + n.

Difficulty rating: 2560
Small Hint:

Aim for a numerator of 1:1: look for two triples of distinct digits whose products differ by exactly 11

Big Hint:

Save the three largest leftover digits for the denominator, then rule out bigger denominators by showing they force a numerator difference of at least 22

Solution:

Try to make the numerator equal to 11 while keeping large digits in the denominator. The products 236=362 \cdot 3 \cdot 6 = 36 and 157=351 \cdot 5 \cdot 7 = 35 differ by 11 and leave 4,8,94, 8, 9 for the denominator, giving the value 3635489=1288.\frac{36 - 35}{4 \cdot 8 \cdot 9} = \frac{1}{288}.

To beat this, a fraction would need numerator 11 with denominator greater than 288.288. The denominators exceeding 288288 are 504,504, 432,432, 360,360, 378,378, 315,315, and 336,336, coming respectively from {7,8,9},\{7,8,9\}, {6,8,9},\{6,8,9\}, {5,8,9},\{5,8,9\}, {6,7,9},\{6,7,9\}, {5,7,9},\{5,7,9\}, and {6,7,8}.\{6,7,8\}. Splitting the remaining six digits into two triples, the smallest positive numerator differences are respectively 6,6, 2,2, 8,8, 2,2, 4,4, and 6.6. The resulting lower bounds 6504,2432,8360,2378,4315,6336\begin{aligned}&\frac{6}{504},\quad \frac{2}{432},\quad \frac{8}{360},\\&\frac{2}{378},\quad \frac{4}{315},\quad \frac{6}{336}\end{aligned} all exceed 1288.\frac{1}{288}.

So the minimum positive value is 1288,\frac{1}{288}, and m+n=1+288=289.m + n = 1 + 288 = 289.

8.

Equilateral triangle ABC\triangle ABC is inscribed in circle ω\omega with radius 18.18. Circle ωA\omega_A is tangent to sides AB\overline{AB} and AC\overline{AC} and is internally tangent to ω.\omega. Circles ωB\omega_B and ωC\omega_C are defined analogously. Circles ωA,\omega_A, ωB,\omega_B, and ωC\omega_C meet in six points — two points for each pair of circles. The three intersection points closest to the vertices of ABC\triangle ABC are the vertices of a large equilateral triangle in the interior of ABC,\triangle ABC, and the other three intersection points are the vertices of a smaller equilateral triangle in the interior of ABC.\triangle ABC. The side length of the smaller equilateral triangle can be written as ab,\sqrt{a} - \sqrt{b}, where aa and bb are positive integers. Find a+b.a + b.

Difficulty rating: 2710
Small Hint:

Find ωA\omega_A first: its center lies on line AO,AO, its radius is half its distance from A,A, and internal tangency to ω\omega fixes everything

Big Hint:

The two intersection points of ωB\omega_B and ωC\omega_C lie on line AO,AO, and each triangle’s circumradius is the distance from that point to the center OO

Solution:

Let OO be the center of ω.\omega. The center of ωA\omega_A lies on line AOAO (the bisector of A\angle A) at some distance dd from A;A; since AB\overline{AB} makes a 3030^\circ angle with AO,AO, the radius is r=dsin30=d2.r = d \sin 30^\circ = \frac{d}{2}. Internal tangency to ω\omega requires the center to be 18r18 - r from O,O, which forces the center past O:O: d18=18d2,d - 18 = 18 - \frac{d}{2}, so d=24,d = 24, r=12,r = 12, and the center is 66 beyond O.O.

Place OO at the origin with A=(0,18).A = (0, 18). Then the three centers are OA=(0,6)O_A = (0, -6) and OB,OC=(±33,3),O_B, O_C = (\pm 3\sqrt{3}, 3), all with radius 12.12. The intersections of ωB\omega_B and ωC\omega_C lie on the yy-axis: 27+(y3)2=14427 + (y - 3)^2 = 144 gives y=3±117.y = 3 \pm \sqrt{117}. The point (0,3+117)(0, 3 + \sqrt{117}) is closer to AA and belongs to the larger triangle, so the smaller triangle has vertex (0,3117),(0, 3 - \sqrt{117}), at distance 1173\sqrt{117} - 3 from O.O.

By symmetry the smaller triangle is equilateral with circumradius 1173,\sqrt{117} - 3, so its side is 3(1173)=35127.\sqrt{3}\left(\sqrt{117} - 3\right) = \sqrt{351} - \sqrt{27}. Thus a+b=351+27=378.a + b = 351 + 27 = 378.

9.

Ellina has twelve blocks, two each of red (R\textbf{R}), blue (B\textbf{B}), yellow (Y\textbf{Y}), green (G\textbf{G}), orange (O\textbf{O}), and purple (P\textbf{P}). Call an arrangement of blocks even if there is an even number of blocks between each pair of blocks of the same color. For example, the arrangement R B B Y G G Y R O P P O\textbf{R B B Y G G Y R O P P O} is even. Ellina arranges her blocks in a row in random order. The probability that her arrangement is even is mn,\frac{m}{n}, where mm and nn are relatively prime positive integers. Find m+n.m + n.

Difficulty rating: 2450
Small Hint:

There is an even number of blocks between positions ii and jj exactly when ii and jj have opposite parity

Big Hint:

So each color must occupy one odd and one even position: the six odd slots hold all six colors once, as do the six even slots

Solution:

If a color occupies positions i<j,i \lt j, the number of blocks between them is ji1,j - i - 1, which is even exactly when ii and jj have opposite parity. So an arrangement is even precisely when every color occupies one odd position and one even position — that is, the six odd slots contain each color exactly once, and so do the six even slots.

Counting arrangements of the twelve blocks (blocks of the same color identical), there are 12!26\frac{12!}{2^6} in total, and 6!6!6! \cdot 6! even ones (a permutation of the six colors in the odd slots and another in the even slots). The probability is 6!6!2612!=16231.\frac{6! \cdot 6! \cdot 2^6}{12!} = \frac{16}{231}.

Since gcd(16,231)=1,\gcd(16, 231) = 1, the answer is m+n=16+231=247.m + n = 16 + 231 = 247.

10.

Three spheres with radii 11,11, 13,13, and 1919 are mutually externally tangent. A plane intersects the spheres in three congruent circles centered at A,A, B,B, and C,C, respectively, and the centers of the spheres all lie on the same side of this plane. Suppose that AB2=560.AB^2 = 560. Find AC2.AC^2.

Difficulty rating: 2560
Small Hint:

If a sphere’s center sits at height hh above the plane, its circle has radius squared r2h2;r^2 - h^2; congruence ties the three heights together

Big Hint:

AA and BB are the feet of the centers, so AB2=242(h2h1)2;AB^2 = 24^2 - (h_2 - h_1)^2; combine with h22h12=132112h_2^2 - h_1^2 = 13^2 - 11^2

Solution:

Let the sphere centers be at heights h1,h2,h3h_1, h_2, h_3 above the plane. Each circle’s center is the foot of the perpendicular from the sphere’s center, and the common circle radius ρ\rho satisfies ρ2=112h12\rho^2 = 11^2 - h_1^2 =132h22= 13^2 - h_2^2 =192h32.= 19^2 - h_3^2.

The first two spheres are tangent, so their centers are 11+13=2411 + 13 = 24 apart, and projecting onto the plane, AB2=242(h2h1)2.AB^2 = 24^2 - (h_2 - h_1)^2. Thus (h2h1)2=576560=16.(h_2 - h_1)^2 = 576 - 560 = 16. Congruence gives h22h12=169121=48,h_2^2 - h_1^2 = 169 - 121 = 48, so h2h1=4h_2 - h_1 = 4 and h2+h1=12h_2 + h_1 = 12 (the other sign gives a negative sum), yielding h1=4,h_1 = 4, h2=8,h_2 = 8, and ρ2=12116=105.\rho^2 = 121 - 16 = 105. Then h32=361105=256,h_3^2 = 361 - 105 = 256, so h3=16.h_3 = 16.

The first and third centers are 11+19=3011 + 19 = 30 apart, so AC2=302(h3h1)2=900144=756. \begin{aligned} AC^2 &= 30^2 - (h_3 - h_1)^2 \\ &= 900 - 144 = 756. \end{aligned}

11.

Let ABCDABCD be a parallelogram with BAD<90.\angle BAD \lt 90^\circ. A circle tangent to sides DA,\overline{DA}, AB,\overline{AB}, and BC\overline{BC} intersects diagonal AC\overline{AC} at points PP and QQ with AP<AQ,AP \lt AQ, as shown. Suppose that AP=3,AP = 3, PQ=9,PQ = 9, and QC=16.QC = 16. Then the area of ABCDABCD can be expressed in the form mn,m\sqrt{n}, where mm and nn are positive integers, and nn is not divisible by the square of any prime. Find m+n.m + n.

Difficulty rating: 3060
Small Hint:

Power of a point: APAQ=36AP \cdot AQ = 36 and CQCP=400CQ \cdot CP = 400 give tangent lengths 66 from AA and 2020 from CC

Big Hint:

Equal tangents force BC=AB+14,BC = AB + 14, and tangency to both parallel lines ADAD and BCBC gives ABcos2 ⁣A2=6;AB \cos^2\!\frac{\angle A}{2} = 6; finish with the law of cosines on AC=28AC = 28

Solution:

By power of a point, APAQ=312=36AP \cdot AQ = 3 \cdot 12 = 36 and CQCP=1625=400,CQ \cdot CP = 16 \cdot 25 = 400, so the tangent lengths from AA and CC are 66 and 20.20. The tangent point on AB\overline{AB} is 66 from A,A, hence AB6AB - 6 from B;B; equal tangents from BB put the tangent point on BC\overline{BC} at that same distance from B,B, so its distance from CC is BC(AB6)=20,BC - (AB - 6) = 20, giving BC=AB+14.BC = AB + 14.

Let BAD=2θ.\angle BAD = 2\theta. The center lies on the bisector of A\angle A with the tangent length from AA equal to 6,6, so the radius is ρ=6tanθ.\rho = 6\tan\theta. The circle is tangent to both parallel lines ADAD and BC,BC, whose distance apart is ABsin2θ,AB \sin 2\theta, so ABsin2θ=2ρ=12tanθ,AB \sin 2\theta = 2\rho = 12 \tan\theta, which simplifies to ABcos2θ=6.AB \cos^2\theta = 6. In triangle ABC,ABC, ABC=1802θ\angle ABC = 180^\circ - 2\theta and AC=3+9+16=28,AC = 3 + 9 + 16 = 28, so the law of cosines gives 784=AB2+BC2+2ABBCcos2θ. \begin{aligned} 784 &= AB^2 + BC^2 \\ &\quad {}+ 2 \cdot AB \cdot BC \cos 2\theta. \end{aligned} Substituting BC=AB+14BC = AB + 14 and cos2θ=2cos2θ1,\cos 2\theta = 2\cos^2\theta - 1, the AB2AB^2 terms cancel and, using ABcos2θ=6,AB\cos^2\theta = 6, the equation collapses to 24AB+336+196=784,24\,AB + 336 + 196 = 784, so AB=212AB = \frac{21}{2} and cos2θ=47.\cos^2\theta = \frac{4}{7}.

Then sin2θ=23747=437,\sin 2\theta = 2\sqrt{\frac{3}{7}}\sqrt{\frac{4}{7}} = \frac{4\sqrt{3}}{7}, and the area is ABBCsin2θ=212492437=1473, \begin{aligned} &AB \cdot BC \sin 2\theta \\ &= \frac{21}{2} \cdot \frac{49}{2} \cdot \frac{4\sqrt{3}}{7} \\ &= 147\sqrt{3}, \end{aligned} so m+n=147+3=150.m + n = 147 + 3 = 150.

12.

For any finite set X,X, let X|X| denote the number of elements in X.X. Define Sn=AB,S_n = \sum |A \cap B|, where the sum is taken over all ordered pairs (A,B)(A, B) such that AA and BB are subsets of {1,2,3,,n}\{1, 2, 3, \ldots, n\} with A=B.|A| = |B|. For example, S2=4S_2 = 4 because the sum is taken over the pairs of subsets (A,B){(,),({1},{1}),({1},{2}),({2},{1}),({2},{2}),({1,2},{1,2})}, \begin{aligned} &(A, B) \in {}\\ &\quad \small\left\{\begin{gathered} (\emptyset, \emptyset), (\{1\}, \{1\}), \\ (\{1\}, \{2\}), (\{2\}, \{1\}), \\ (\{2\}, \{2\}), (\{1, 2\}, \{1, 2\}) \end{gathered}\right\}, \end{aligned} giving S2=0+1+0+0+1+2=4.S_2 = 0 + 1 + 0 + 0 + 1 + 2 = 4. Let S2022S2021=pq,\frac{S_{2022}}{S_{2021}} = \frac{p}{q}, where pp and qq are relatively prime positive integers. Find the remainder when p+qp + q is divided by 1000.1000.

Difficulty rating: 2990
Small Hint:

Swap the order of summation: for each element, count the pairs (A,B)(A, B) with A=B|A| = |B| that contain it in both sets

Big Hint:

k(n1k1)2=(2n2n1),\sum_k \binom{n-1}{k-1}^2 = \binom{2n-2}{n-1}, so Sn=n(2n2n1);S_n = n\binom{2n-2}{n-1}; then simplify the ratio of consecutive terms

Solution:

Count element by element: SnS_n equals the number of triples (x,A,B)(x, A, B) with A=B|A| = |B| and xAB.x \in A \cap B. For a fixed xx and size k,k, there are (n1k1)\binom{n-1}{k-1} choices for each of AA and BB containing x,x, so by the Vandermonde identity Sn=nk=1n(n1k1)2=n(2n2n1). \begin{aligned} S_n &= n \sum_{k=1}^{n} \binom{n-1}{k-1}^2 \\ &= n\binom{2n-2}{n-1}. \end{aligned}

Therefore S2022S2021=2022(40422021)2021(40402020)=202220214042404120212=22022404120212. \begin{aligned} \frac{S_{2022}}{S_{2021}} &= \frac{2022\binom{4042}{2021}}{2021\binom{4040}{2020}} \\ &= \frac{2022}{2021} \cdot \frac{4042 \cdot 4041}{2021^2} \\ &= \frac{2 \cdot 2022 \cdot 4041}{2021^2}. \end{aligned} Since 2021=43472021 = 43 \cdot 47 divides neither 2022,2022, 4041=32449,4041 = 3^2 \cdot 449, nor 2,2, this fraction is in lowest terms: p=220224041=16341804p = 2 \cdot 2022 \cdot 4041 = 16341804 and q=20212=4084441.q = 2021^2 = 4084441.

Then p+q=20426245,p + q = 20426245, whose remainder modulo 10001000 is 245.245.

13.

Let SS be the set of all rational numbers that can be expressed as a repeating decimal in the form 0.abcd,0.\overline{abcd}, where at least one of the digits a,a, b,b, c,c, or dd is nonzero. Let NN be the number of distinct numerators obtained when numbers in SS are written as fractions in lowest terms. For example, both 44 and 410410 are counted among the distinct numerators for numbers in SS because 0.3636=4110.\overline{3636} = \frac{4}{11} and 0.1230=4103333.0.\overline{1230} = \frac{410}{3333}. Find the remainder when NN is divided by 1000.1000.

Difficulty rating: 3160
Small Hint:

Every element of SS is k9999\frac{k}{9999} with 1k99991 \le k \le 9999 and 9999=32111019999 = 3^2 \cdot 11 \cdot 101

Big Hint:

mm is a numerator exactly when mDm \le D and gcd(m,D)=1\gcd(m, D) = 1 for some divisor DD of 9999.9999. Classify mm by which of 3,3, 11,11, or 101101 divide it.

Solution:

Every element of SS equals k9999\frac{k}{9999} for some 1k9999,1 \le k \le 9999, where 9999=3211101.9999 = 3^2 \cdot 11 \cdot 101. In lowest terms this is mD\frac{m}{D} where DD divides 9999,9999, mD,m \le D, and gcd(m,D)=1;\gcd(m, D) = 1; conversely any such mD\frac{m}{D} arises from k=m9999D.k = m \cdot \frac{9999}{D}. So NN counts the integers mm that are at most, and coprime to, some divisor DD of 9999.9999.

Classify mm by which of the primes 3,3, 11,11, or 101101 divide it, always using the largest divisor DD coprime to m.m. If gcd(m,9999)=1,\gcd(m, 9999) = 1, take D=9999:D = 9999: there are φ(9999)=6000\varphi(9999) = 6000 such m.m. If only 33 divides m,m, take D=11101=1111:D = 11 \cdot 101 = 1111: multiples of 33 up to 11111111 avoiding 1111 and 101101 number 370333=334.370 - 33 - 3 = 334. If only 1111 divides m,m, take D=9101=909:D = 9 \cdot 101 = 909: that gives 8227=55.82 - 27 = 55. If only 101101 divides m,m, then D=99<101D = 99 \lt 101 admits none. If mm is divisible by 3333 but not by 101,101, take D=101:D = 101: the values 33,33, 66,66, and 9999 give 33 more, and any mm divisible by 31013 \cdot 101 or 1110111 \cdot 101 would need D11,D \le 11, which is impossible.

Therefore N=6000+334+55+3N = 6000 + 334 + 55 + 3 =6392,= 6392, and the remainder modulo 10001000 is 392.392.

14.

Given ABC\triangle ABC and a point PP on one of its sides, call line \ell the splitting line of ABC\triangle ABC through PP if \ell passes through PP and divides ABC\triangle ABC into two polygons of equal perimeter. Let ABC\triangle ABC be a triangle where BC=219BC = 219 and ABAB and ACAC are positive integers. Let MM and NN be the midpoints of AB\overline{AB} and AC,\overline{AC}, respectively, and suppose that the splitting lines of ABC\triangle ABC through MM and NN intersect at 30.30^\circ. Find the perimeter of ABC.\triangle ABC.

Difficulty rating: 3500
Small Hint:

Show the splitting line through MM is parallel to the angle bisector from C:C: it meets BC\overline{BC} at XX with BX=sc2,BX = s - \frac{c}{2}, and BXM=C2\angle BXM = \frac{C}{2}

Big Hint:

The bisectors from BB and CC cross at 90+A2,90^\circ + \frac{A}{2}, so the 3030^\circ condition forces A=120;\angle A = 120^\circ; then make 421923(b+c)24 \cdot 219^2 - 3(b+c)^2 a perfect square

Solution:

Write a=BC=219,a = BC = 219, b=CA,b = CA, c=AB,c = AB, and ss for the semiperimeter. The splitting line through MM meets BC\overline{BC} at the point X.X. Equating the two piece perimeters and cancelling their common segment MX\overline{MX} gives c2+BX=c2+b+(aBX), \frac{c}{2}+BX=\frac{c}{2}+b+(a-BX), so BX=a+b2=sc2.BX=\frac{a+b}{2}=s-\frac{c}{2}. In triangle BMX,BMX, the law of sines shows BXM=C2:\angle BXM = \frac{C}{2}: this needs csin(B+C2)=(a+b)sinC2,c \sin\left(B + \frac{C}{2}\right) = (a + b)\sin\frac{C}{2}, which reduces via a+b=2R(sinA+sinB)a + b = 2R(\sin A + \sin B) =4RcosC2cosAB2= 4R\cos\frac{C}{2}\cos\frac{A - B}{2} and c=4RsinC2cosC2c = 4R \sin\frac{C}{2}\cos\frac{C}{2} to sin(B+C2)=cosAB2,\sin\left(B + \frac{C}{2}\right) = \cos\frac{A - B}{2}, true because those angles are complementary. Hence the splitting line through MM is parallel to the angle bisector from C,C, and likewise the one through NN is parallel to the bisector from B.B.

The internal bisectors from BB and CC meet at 90+A2>90,90^\circ + \frac{A}{2} \gt 90^\circ, so the acute angle between the two splitting lines is 90A2=30,90^\circ - \frac{A}{2} = 30^\circ, forcing A=120.\angle A = 120^\circ. The law of cosines gives 2192=b2+c2+bc=(b+c)2bc. \begin{aligned} 219^2 &= b^2 + c^2 + bc \\ &= (b + c)^2 - bc. \end{aligned} Set p=b+c,p = b + c, so bc=p22192bc = p^2 - 219^2 and bb and cc are roots of t2pt+(p22192),t^2 - pt + (p^2 - 219^2), requiring 421923p24 \cdot 219^2 - 3p^2 to be a perfect square k2.k^2. Then 33 divides kk and 33 divides p;p; writing p=3rp = 3r and k=3mk = 3m turns the condition into m2+3r2=1462.m^2 + 3r^2 = 146^2. The triangle inequality p>219p \gt 219 and 421923p24 \cdot 219^2 \ge 3p^2 restrict 74r84,74 \le r \le 84, and checking these, only r=80r = 80 works, with m=46.m = 46.

So b+c=240b + c = 240 and bc=240247961=9639,bc = 240^2 - 47961 = 9639, giving {b,c}={51,189}\{b, c\} = \{51, 189\} — a valid triangle. The perimeter is 219+240=459.219 + 240 = 459.

15.

Let x,x, y,y, and zz be positive real numbers satisfying the system of equations 2xxy+2yxy=1\sqrt{2x - xy} + \sqrt{2y - xy} = 1 2yyz+2zyz=2\sqrt{2y - yz} + \sqrt{2z - yz} = \sqrt{2} 2zzx+2xzx=3.\sqrt{2z - zx} + \sqrt{2x - zx} = \sqrt{3}. Then [(1x)(1y)(1z)]2\left[(1 - x)(1 - y)(1 - z)\right]^2 can be written as mn,\frac{m}{n}, where mm and nn are relatively prime positive integers. Find m+n.m + n.

Difficulty rating: 3270
Small Hint:

Factor each radical as x(2y)\sqrt{x(2 - y)} and substitute x=2sin2α,x = 2\sin^2\alpha, y=2sin2β,y = 2\sin^2\beta, z=2sin2γz = 2\sin^2\gamma

Big Hint:

Each equation collapses by the addition formula to 2sin(α+β)=1,2\sin(\alpha + \beta) = 1, etc.; solve the little linear system for the angles and use 12sin2θ=cos2θ1 - 2\sin^2\theta = \cos 2\theta

Solution:

Each radicand factors: 2xxy=x(2y),2x - xy = x(2 - y), and so on, so 0<x,y,z2.0 \lt x, y, z \le 2. Substitute x=2sin2α,x = 2\sin^2\alpha, y=2sin2β,y = 2\sin^2\beta, z=2sin2γz = 2\sin^2\gamma with α,β,γ(0,90].\alpha, \beta, \gamma \in \left(0^\circ, 90^\circ\right]. Then x(2y)=4sin2αcos2β\sqrt{x(2 - y)} = \sqrt{4\sin^2\alpha\cos^2\beta} =2sinαcosβ,= 2\sin\alpha\cos\beta, and each equation collapses by the sine addition formula: 2sin(α+β)=1,2\sin(\alpha + \beta) = 1, 2sin(β+γ)=2,2\sin(\beta + \gamma) = \sqrt{2}, 2sin(γ+α)=3.2\sin(\gamma + \alpha) = \sqrt{3}.

One admissible choice is α+β=30,\alpha + \beta = 30^\circ, β+γ=45,\beta + \gamma = 45^\circ, γ+α=60,\gamma + \alpha = 60^\circ, which gives α=22.5,\alpha = 22.5^\circ, β=7.5,\beta = 7.5^\circ, γ=37.5.\gamma = 37.5^\circ. The only other branch consistent with 0<α,β,γ900^\circ \lt \alpha,\beta,\gamma \le 90^\circ uses pairwise sums 150,135,120,150^\circ,135^\circ,120^\circ, giving α=67.5,\alpha = 67.5^\circ, β=82.5,\beta = 82.5^\circ, γ=52.5;\gamma = 52.5^\circ; its product below is the negative of the first branch’s product, so the requested square is identical. For the first branch, the double-angle identity gives 1x=cos2α=cos45,1 - x = \cos 2\alpha = \cos 45^\circ, 1y=cos15,1 - y = \cos 15^\circ, and 1z=cos75.1 - z = \cos 75^\circ.

Therefore (1x)(1y)(1z)=22cos15sin15=22sin302=28, \begin{aligned} &(1 - x)(1 - y)(1 - z) \\ &= \frac{\sqrt{2}}{2}\cos 15^\circ \\ &\quad {}\cdot \sin 15^\circ \\ &= \frac{\sqrt{2}}{2} \cdot \frac{\sin 30^\circ}{2} \\ &= \frac{\sqrt{2}}{8}, \end{aligned} whose square is 264=132.\frac{2}{64} = \frac{1}{32}. Thus m+n=1+32=33.m + n = 1 + 32 = 33.