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 106−10820−16=−12,\frac{106 - 108}{20 - 16} = -\frac{1}{2}, so P(0)+Q(0)=R(0)=R(16)+16⋅12=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 a‾ b‾ c‾\underline{a}\,\underline{b}\,\underline{c} whose representation in base nine is b‾ c‾ a‾,\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 3a≡−b(mod8),3a \equiv -b \pmod 8, so b≡5a(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=198−142=56,8c = 198 - 142 = 56, so c=7.c = 7. For each a≥3,a \ge 3, the required bb forces 99a−71b99a - 71b outside the range [0,64],[0, 64], so there is no other solution.

The number is 227,227, and indeed 227=2⋅81+7⋅9+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 ADA′ADA' 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 AB‾∥CD‾,\overline{AB} \parallel \overline{CD}, we have ∠DA′A=∠A′AB=∠A′AD,\angle DA'A = \angle A'AB = \angle A'AD, so triangle ADA′ADA' 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 B′B' 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′=(650−333,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=446−204=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 i⋅wr=zs.\mathrm{i} \cdot w^r = z^s.

Difficulty rating: 2300
Small Hint:

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

Big Hint:

Matching arguments gives 90+30r≡120s(mod360),90 + 30r \equiv 120s \pmod{360}, i.e. r+3≡4s(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=cis⁡30∘w = \operatorname{cis} 30^\circ and z=cis⁡120∘,z = \operatorname{cis} 120^\circ, while i=cis⁡90∘.\mathrm{i} = \operatorname{cis} 90^\circ. The equation i⋅wr=zs\mathrm{i} \cdot w^r = z^s is therefore a statement about arguments: 90+30r≡120s(mod360),90 + 30r \equiv 120s \pmod{360}, i.e. r+3≡4s(mod12).r + 3 \equiv 4s \pmod{12}.

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

The count is 34⋅934 \cdot 9 +33⋅8+ 33 \cdot 8 +33⋅8+ 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−(u−14)2(u + 14)^2 - (u - 14)^2 =6400−3600= 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 (D2t−14)2+(264t)2=602, \begin{aligned} &\left(\frac{D}{2t} - 14\right)^2 \\ &\quad {}+ \left(\frac{264}{t}\right)^2 = 60^2, \end{aligned} (−D2t−14)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−(u−14)2(u + 14)^2 - (u - 14)^2 =56u= 56u =6400−3600= 6400 - 3600 =2800,= 2800, so u=50.u = 50. Substituting back, (50−14)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+23−1)276 - (23 + 23 - 1) −3=276−48=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 a⋅b⋅c−d⋅e⋅fg⋅h⋅i\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 2⋅3⋅6=362 \cdot 3 \cdot 6 = 36 and 1⋅5⋅7=351 \cdot 5 \cdot 7 = 35 differ by 11 and leave 4,8,94, 8, 9 for the denominator, giving the value 36−354⋅8⋅9=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 a−b,\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 30∘30^\circ angle with AO,AO, the radius is r=dsin⁡30∘=d2.r = d \sin 30^\circ = \frac{d}{2}. Internal tangency to ω\omega requires the center to be 18−r18 - r from O,O, which forces the center past O:O: d−18=18−d2,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+(y−3)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,3−117),(0, 3 - \sqrt{117}), at distance 117−3\sqrt{117} - 3 from O.O.

By symmetry the smaller triangle is equilateral with circumradius 117−3,\sqrt{117} - 3, so its side is 3(117−3)=351−27.\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 j−i−1,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 r2−h2;r^2 - h^2; congruence ties the three heights together

Big Hint:

AA and BB are the feet of the centers, so AB2=242−(h2−h1)2;AB^2 = 24^2 - (h_2 - h_1)^2; combine with h22−h12=132−112h_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=112−h12\rho^2 = 11^2 - h_1^2 =132−h22= 13^2 - h_2^2 =192−h32.= 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−(h2−h1)2.AB^2 = 24^2 - (h_2 - h_1)^2. Thus (h2−h1)2=576−560=16.(h_2 - h_1)^2 = 576 - 560 = 16. Congruence gives h22−h12=169−121=48,h_2^2 - h_1^2 = 169 - 121 = 48, so h2−h1=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=121−16=105.\rho^2 = 121 - 16 = 105. Then h32=361−105=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−(h3−h1)2=900−144=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: AP⋅AQ=36AP \cdot AQ = 36 and CQ⋅CP=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 ABcos⁡2 ⁣∠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, AP⋅AQ=3⋅12=36AP \cdot AQ = 3 \cdot 12 = 36 and CQ⋅CP=16⋅25=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 AB−6AB - 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−(AB−6)=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 ABsin⁡2θ,AB \sin 2\theta, so ABsin⁡2θ=2ρ=12tan⁡θ,AB \sin 2\theta = 2\rho = 12 \tan\theta, which simplifies to ABcos⁡2θ=6.AB \cos^2\theta = 6. In triangle ABC,ABC, ∠ABC=180∘−2θ\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+2⋅AB⋅BCcos⁡2θ. \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 cos⁡2θ=2cos⁡2θ−1,\cos 2\theta = 2\cos^2\theta - 1, the AB2AB^2 terms cancel and, using ABcos⁡2θ=6,AB\cos^2\theta = 6, the equation collapses to 24 AB+336+196=784,24\,AB + 336 + 196 = 784, so AB=212AB = \frac{21}{2} and cos⁡2θ=47.\cos^2\theta = \frac{4}{7}.

Then sin⁡2θ=23747=437,\sin 2\theta = 2\sqrt{\frac{3}{7}}\sqrt{\frac{4}{7}} = \frac{4\sqrt{3}}{7}, and the area is AB⋅BCsin⁡2θ=212⋅492⋅437=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=∑∣A∩B∣,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(n−1k−1)2=(2n−2n−1),\sum_k \binom{n-1}{k-1}^2 = \binom{2n-2}{n-1}, so Sn=n(2n−2n−1);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 x∈A∩B.x \in A \cap B. For a fixed xx and size k,k, there are (n−1k−1)\binom{n-1}{k-1} choices for each of AA and BB containing x,x, so by the Vandermonde identity Sn=n∑k=1n(n−1k−1)2=n(2n−2n−1). \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)=20222021⋅4042⋅404120212=2⋅2022⋅404120212. \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=43⋅472021 = 43 \cdot 47 divides neither 2022,2022, 4041=32⋅449,4041 = 3^2 \cdot 449, nor 2,2, this fraction is in lowest terms: p=2⋅2022⋅4041=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 1≤k≤99991 \le k \le 9999 and 9999=32⋅11⋅1019999 = 3^2 \cdot 11 \cdot 101

Big Hint:

mm is a numerator exactly when m≤Dm \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 1≤k≤9999,1 \le k \le 9999, where 9999=32⋅11⋅101.9999 = 3^2 \cdot 11 \cdot 101. In lowest terms this is mD\frac{m}{D} where DD divides 9999,9999, m≤D,m \le D, and gcd⁡(m,D)=1;\gcd(m, D) = 1; conversely any such mD\frac{m}{D} arises from k=m⋅9999D.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=11⋅101=1111:D = 11 \cdot 101 = 1111: multiples of 33 up to 11111111 avoiding 1111 and 101101 number 370−33−3=334.370 - 33 - 3 = 334. If only 1111 divides m,m, take D=9⋅101=909:D = 9 \cdot 101 = 909: that gives 82−27=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 3⋅1013 \cdot 101 or 11⋅10111 \cdot 101 would need D≤11,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=s−c2,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 30∘30^\circ condition forces ∠A=120∘;\angle A = 120^\circ; then make 4⋅2192−3(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+(a−BX), \frac{c}{2}+BX=\frac{c}{2}+b+(a-BX), so BX=a+b2=s−c2.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)sin⁡C2,c \sin\left(B + \frac{C}{2}\right) = (a + b)\sin\frac{C}{2}, which reduces via a+b=2R(sin⁡A+sin⁡B)a + b = 2R(\sin A + \sin B) =4Rcos⁡C2cos⁡A−B2= 4R\cos\frac{C}{2}\cos\frac{A - B}{2} and c=4Rsin⁡C2cos⁡C2c = 4R \sin\frac{C}{2}\cos\frac{C}{2} to sin⁡(B+C2)=cos⁡A−B2,\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 90∘−A2=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)2−bc. \begin{aligned} 219^2 &= b^2 + c^2 + bc \\ &= (b + c)^2 - bc. \end{aligned} Set p=b+c,p = b + c, so bc=p2−2192bc = p^2 - 219^2 and bb and cc are roots of t2−pt+(p2−2192),t^2 - pt + (p^2 - 219^2), requiring 4⋅2192−3p24 \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 4⋅2192≥3p24 \cdot 219^2 \ge 3p^2 restrict 74≤r≤84,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=2402−47961=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 2x−xy+2y−xy=1\sqrt{2x - xy} + \sqrt{2y - xy} = 1 2y−yz+2z−yz=2\sqrt{2y - yz} + \sqrt{2z - yz} = \sqrt{2} 2z−zx+2x−zx=3.\sqrt{2z - zx} + \sqrt{2x - zx} = \sqrt{3}. Then [(1−x)(1−y)(1−z)]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(2−y)\sqrt{x(2 - y)} and substitute x=2sin⁡2α,x = 2\sin^2\alpha, y=2sin⁡2β,y = 2\sin^2\beta, z=2sin⁡2γ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 1−2sin⁡2θ=cos⁡2θ1 - 2\sin^2\theta = \cos 2\theta

Solution:

Each radicand factors: 2x−xy=x(2−y),2x - xy = x(2 - y), and so on, so 0<x,y,z≤2.0 \lt x, y, z \le 2. Substitute x=2sin⁡2α,x = 2\sin^2\alpha, y=2sin⁡2β,y = 2\sin^2\beta, z=2sin⁡2γz = 2\sin^2\gamma with α,β,γ∈(0∘,90∘].\alpha, \beta, \gamma \in \left(0^\circ, 90^\circ\right]. Then x(2−y)=4sin⁡2αcos⁡2β\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∘<α,β,γ≤90∘0^\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 1−x=cos⁡2α=cos⁡45∘,1 - x = \cos 2\alpha = \cos 45^\circ, 1−y=cos⁡15∘,1 - y = \cos 15^\circ, and 1−z=cos⁡75∘.1 - z = \cos 75^\circ.

Therefore (1−x)(1−y)(1−z)=22cos⁡15∘⋅sin⁡15∘=22⋅sin⁡30∘2=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.