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

2019 USAJMO Problems真题及答案

Category: AMC美国数学竞赛, 国际竞赛 Date: 2019年8月13日上午10:49

2019 USAJMO Problems真题及答案

Day 1

Note:?For any geometry problem whose statement begins with an asterisk? $(*)$ , the first page of the solution must be a large, in-scale, clearly labeled diagram. Failure to meet this requirement will result in an automatic 1-point deduction.

Problem 1

There are? $a+b$ ?bowls arranged in a row, numbered? $1$ ?through? $a+b$ , where? $a$ ?and? $b$ ?are given positive integers. Initially, each of the first? $a$ ?bowls contains an apple, and each of the last? $b$ ?bowls contains a pear.

A legal move consists of moving an apple from bowl? $i$ ?to bowl? $i+1$ ?and a pear from bowl? $j$ ?to bowl? $j-1$ , provided that the difference? $i-j$ ?is even. We permit multiple fruits in the same bowl at the same time. The goal is to end up with the first? $b$ ?bowls each containing a pear and the last? $a$ ?bowls each containing an apple. Show that this is possible if and only if the product? $ab$ ?is even.

Problem 2

Let? $\mathbb Z$ ?be the set of all integers. Find all pairs of integers? $(a,b)$ ?for which there exist functions? $f:\mathbb Z\rightarrow\mathbb Z$ ?and? $g:\mathbb Z\rightarrow\mathbb Z$ ?satisfying $f(g(x))=x+a\quad\text{and}\quad g(f(x))=x+b$ for all integers? $x$ .

Problem 3

$(*)$ ?Let? $ABCD$ ?be a cyclic quadrilateral satisfying? $AD^2+BC^2=AB^2$ . The diagonals of? $ABCD$ ?intersect at? $E$ . Let? $P$ ?be a point on side? $\overline{AB}$ ?satisfying? $\angle APD=\angle BPC$ . Show that line? $PE$ ?bisects? $\overline{CD}$ .

Day 2

Problem 4

$(*)$ ?Let? $ABC$ ?be a triangle with? $\angle ABC$ ?obtuse. The? $A$ -excircle?is a circle in the exterior of? $\triangle ABC$ ?that is tangent to side? $BC$ ?of the triangle and tangent to the extensions of the other two sides. Let? $E, F$ ?be the feet of the altitudes from? $B$ ?and? $C$ ?to lines? $AC$ ?and? $AB$ , respectively. Can line? $EF$ ?be tangent to the? $A$ -excircle?

Problem 5

Let? $n$ ?be a nonnegative integer. Determine the number of ways that one can choose? $(n+1)^2$ ?sets? $S_{i,j} \subseteq \{1,2,...,2n\}$ , for integers? $i,j$ ?with? $0 \le i,j \le n$ ?such that:

$\bullet$ ?for all? $0 \le i,j \le n$ , the set? $S_{i,j}$ ?has? $i+j$ ?elements; and

$\bullet$ ? $S_{i,j} \subseteq S_{k,l}$ ?whenever? $0 \le i \le k \le n$ ?and? $0 \le j \le l \le n$

Problem 6

Two rational numbers? $\tfrac{m}{n}$ ?and? $\tfrac{n}{m}$ ?are written on a blackboard, where? $m$ ?and? $n$ ?are relatively prime positive integers. At any point, Evan may pick two of the numbers? $x$ ?and? $y$ ?written on the board and write either their arithmetic mean? $\tfrac{x+y}{2}$ ?or their harmonic mean? $\tfrac{2xy}{x+y}$ ?on the board?as?well. Find all pairs? $(m,n)$ ?such that Evan can write? $1$ ?on the board in finitely many steps.

2019USAJMO真题参考答案及详解

Problem 1

Solution

Claim:?If? $a$ ?and? $b$ ?are both odd, then the end goal of achieving? $b$ ?pears followed by? $a$ ?apples is impossible.

Proof:?Let? $A_1$ ?and? $P_1$ ?denote the number of apples and the number of pears in odd-numbered positions, respectively. We show that? $A_1 - P_1$ ?is invariant. Notice that if? $i$ ?and? $j$ ?are odd, then? $A_1$ ?and? $P_1$ ?both decrease by 1, as one apple and one pear are both moved from odd-numbered positions to even-numbered positions. If? $i$ ?and? $j$ ?are even, then? $A_1$ ?and? $P_1$ ?both increase by 1.

Because the starting configuration? $aa\ldots ab\ldots b$ ?has? $\left\lfloor \frac{a}{2} \right\rfloor + 1$ ?odd-numbered apples and? $\left\lfloor \frac{2} \right\rfloor$ ?odd-numbered pears, the initial value of? $A_1 - P_1$ ?is? $\left\lfloor \frac{a}{2} \right\rfloor - \left\lfloor \frac{2} \right\rfloor + 1$ . But the desired ending configuration has? $\left\lfloor \frac{2}\right\rfloor + 1$ ?odd-numbered pears and? $\left\lfloor \frac{a}{2} \right\rfloor$ ?odd-numbered apples, so? $A_1 - P_1 = \left\lfloor \frac{a}{2} \right\rfloor - \left\lfloor \frac{2} \right\rfloor - 1$ .?As? $A_1 - P_1$ ?is invariant, it is impossible to attain the desired ending configuration.? $\blacksquare$

Claim:?If at least one of? $a$ ?and? $b$ ?is even, then the end goal of achieving? $b$ ?pears followed by? $a$ ?apples is possible.

Proof:?Without loss of generality, assume? $a$ ?is even. If only? $b$ ?is even, then we can number the bowls in reverse, and swap apples with pears. We use two inductive arguments to show that? $(a,b) = (2,b)$ ?is achievable for all? $b\ge 1$ , then to show that? $(a,b)$ ?is achievable for all even? $a$ ?and all? $b\ge 1$ .

Base case:? $(a,b) = (2,1)$ . Then we can easily achieve the ending configuration in two moves, by moving the apple in bowl #1 and the pear in bowl #3 so that everything is in bowl #2, then finishing the next move.

Inductive step:?suppose that for? $a \ge 2$ ?(even) apples and? $b \ge 1$ ?pears, that with? $a$ ?apples and? $b$ ?pears, the ending configuration is achievable. We will show two things: i) achievable with? $a$ ?apples and? $b+1$ ?pears, and ii) achievable with? $a+2$ ?apples and? $b$ ?pears.

i) Apply the process on the? $a$ ?apples and first? $b$ ?pairs to get a configuration? $bb\ldots ba\ldots ab$ . Now we will "swap" the leftmost apple with the last pear by repeatedly applying the move on just these two fruits (as? $a$ ?is even, the difference? $i-j$ ?is even). This gives a solution for? $a$ ?apples and? $b+1$ ?pears. In particular, this shows that? $(a,b) = (2,b)$ ?for all? $b\ge 1$ ?is achievable.

ii) To show? $(a+2, b)$ ?is achievable, given that? $(a,b)$ ?is achievable, apply the process on the last? $a$ ?apples and? $b$ ?pears to get the configuration? $aabbb\ldots baaa\ldots a$ . Then, because we have shown that 2 apples and? $b$ ?pears is achievable in i), we can now reverse the first two apples and? $b$ pears.

Thus for? $ab$ ?even, the desired ending configuration is achievable.? $\blacksquare$

Combining the above two claims, we see that this is possible if and only if? $ab$ is even.

Solution 2

"If" part: Note that two opposite fruits can be switched if they have even distance. If one of? $a$ ,? $b$ ?is odd and the other is even, then switch? $1$ ?with? $a+b$ ,? $2$ ?with? $a+b-1$ ,? $3$ ?with? $a+b-2$ ... until all of one fruit is switched. If both are even, then if? $a>b$ , then switch? $1$ ?with? $a+1$ ,? $2$ ?with? $a+2$ ,? $3$ ?with? $a+3$ ... until all of one fruit is switched; if? $a<b$ ?then switch? $a$ ?with? $a+b$ ,? $a-1$ ?with? $a+b-1$ ,? $a-2$ ?with? $a+b-2$ ... until all of one fruit is switched. Each of these processes achieve the end goal.

"Only if" part: Assign each apple a value of? $1$ ?and each pear a value of? $-1$ . At any given point in time, let? $E$ ?be the sum of the values of the fruit in even-numbered bowls. Because? $a$ ?and? $b$ ?both are odd, at the beginning there are? $\frac{a-1}{2}$ ?apples in even bowls and? $\frac{b+1}{2}$ ?pears in even bowls, so at the beginning? $E=\frac{a-b}{2}-1$ . After the end goal is achieved, there are? $\frac{a+1}{2}$ ?apples in even bowls and? $\frac{b-1}{2}$ ?pears in even bowls, so after the end goal is achieved? $E=\frac{a-b}{2}+1$ . However, because two opposite fruits must have the same parity to move and will be the same parity after they move, we see that? $E$ ?is invariant, which is a contradiction; hence, it is impossible for the end goal to be reached if? $ab$ ?is odd.

Problem 2

Solution

We claim that the answer is? $|a|=|b|$ .

Proof:? $f$ ?and? $g$ ?are surjective because? $x+a$ ?and? $x+b$ ?can take on any integral value, and by evaluating the parentheses in different order, we find? $f(g(f(x)))=f(x+b)=f(x)+a$ ?and? $g(f(g(x)))=g(x+a)=g(x)+b$ . We see that if? $a=0$ ?then? $g(x)=g(x)+b$ ?to? $b=0$ as?well, so similarly if? $b=0$ ?then? $a=0$ , so now assume? $a, b\ne 0$ .

We see that if? $x=|b|n$ ?then? $f(x)\equiv f(0) \pmod{|a|}$ , if? $x=|b|n+1$ ?then? $f(x)\equiv f(1)\pmod{|a|}$ , if? $x=|b|n+2$ ?then? $f(x)\equiv f(2)\pmod{|a|}$ ... if? $x=|b|(n+1)-1$ ?then? $f(x)\equiv f(|b|-1)\pmod{|a|}$ . This means that the? $b$ -element collection? $\left\{f(0), f(1), f(2), ... ,f(|b|-1)\right\}$ ?contains all? $|a|$ ?residues mod? $|a|$ ?since? $f$ ?is surjective, so? $|b|\ge |a|$ . Doing the same to? $g$ ?yields that? $|a|\ge |b|$ , so this means that only? $|a|=|b|$ ?can work.

For? $a=b$ ?let? $f(x)=x$ ?and? $g(x)=x+a$ , and for? $a=-b$ ?let? $f(x)=-x+a$ ?and? $g(x)=-x-a$ , so? $|a|=|b|$ ?does work and are the only solutions,?as?desired.

Problem 3

Solution 1

Let? $PE \cap DC = M$ . Also, let? $N$ ?be the midpoint of? $AB$ .

Note that only one point? $P$ ?satisfies the given angle condition. With this in mind, construct? $P'$ ?with the following properties:

$AP' \cdot AB = AD^2 \quad \text{and} \quad BP' \cdot AB = CD^2$

Claim:? $P = P'$

Proof:

The conditions imply the similarities? $ADP \sim ABD$ ?and? $BCP \sim BAC$ ?whence? $\measuredangle APD = \measuredangle BDA = \measuredangle BCA = \measuredangle CPB$ ?as desired.

Claim:? $PE$ ?is a symmedian in? $AEB$

Proof:

We have

$AP \cdot AB = AD^2 \iff AB^2 \cdot AP = AD^2 \cdot AB$ $\iff \left( \frac{AB}{AD} \right)^2 = \frac{AB}{AP}$ $\iff \left( \frac{AB}{AD} \right)^2 - 1 = \frac{AB}{AP} - 1$ $\iff \frac{AB^2 - AD^2}{AD^2} = \frac{BP}{AP}$ $\iff \left(\frac{BC}{AD} \right)^2 = \left(\frac{BE}{AE} \right)^2 = \frac{BP}{AP}$

as desired.

Since? $P$ ?is the isogonal conjugate of? $N$ ,? $\measuredangle PEA = \measuredangle MEC = \measuredangle BEN$ . However? $\measuredangle MEC = \measuredangle BEN$ ?implies that? $M$ ?is the midpoint of? $CD$ from similar triangles, so we are done.

~sriraamster

Solution 2

By monoticity, we can see that the point? $P$ ?is unique. Therefore, if we find another point? $P'$ ?with all the same properties?as? $P$ , then? $P = P'$

Part 1) Let? $N$ ?be a point on? $\overline{AB}$ ?such that? $AN\cdot AB = AD^2$ , and? $BN \cdot AB = BC^2$ . Obviously? $N$ ?exists because adding the two equations gives? $AN\cdot AB + BN \cdot AB = AD^2 + BC^2 = AB^2$ , which is the problem statement. Notice that converse PoP gives $AN\cdot AB = AD^2 \implies \bigtriangleup ADN \sim \bigtriangleup ABD$ $BN\cdot AB = AD^2 \implies \bigtriangleup CBN \sim \bigtriangleup ABC$ Therefore,? $\angle AND = \angle ADB = \angle ACB = \angle CNB$ , so? $N$ ?does indeed satisfy all the conditions? $P$ ?does, so? $N = P$ . Hence,? $\bigtriangleup ADP \sim \bigtriangleup ABD$ ?and? $\bigtriangleup CBP \sim\bigtriangleup ABC$ .

Part 2) Define? $G$ ?as?the midpoint of? $CD$ . Furthermore, create a point? $X$ ?such that? $DX || DC$ ?and? $CX || ED$ . Obviously? $XCED$ ?must be a parallelogram. Now we set up for Jacobi's. The problem already gives us that? $\angle APD = \angle CPB$ , which is good for starters. Furthermore,? $\bigtriangleup ADP \sim \bigtriangleup ABD$ ?tells us that $\angle ADP = \angle ABD = \angle ACD = \angle XDC$ This gives us our second needed angle equivalence. Lastly,? $\bigtriangleup CBP \sim\bigtriangleup ABC$ ?will give $\angle BCP = \angle BAC = \angle BDC = \angle XCD$ which is our last necessary angle equivalence to apply Jacobi's. Finally, applying Jacobi's tells us that? $AC$ ,? $BD$ , and? $XP$ ?are concurrent? $\implies$ ? $X$ ,? $E$ ,? $P$ ?collinear. Additionally, since parallelogram diagonals bisect each other,? $X$ ,? $G$ , and? $E$ ?are collinear, so finally we obtain that? $P$ ,? $E$ , and? $G$ are collinear,?as?desired.

Problem 4

Solution

Instead of trying to find a synthetic way to describe? $EF$ ?being tangent to the? $A$ -excircle (very hard), we instead consider the foot of the perpendicular from the? $A$ -excircle to? $EF$ , hoping to force something via the length of the perpendicular. It would be nice if there were an easier way to describe? $EF$ , something more closely related to the? $A$ -excircle;?as?we are considering perpendicularity, if we could generate a line parallel to? $EF$ , that would be good.

So we recall that it is well known that triangle? $AEF$ ?is similar to? $ABC$ . This motivates reflecting? $BC$ ?over the angle bisector at? $A$ ?to obtain? $B'C'$ , which is parallel to? $EF$ ?for obvious reasons.

Furthermore,?as?reflection preserves intersection,? $B'C'$ ?is tangent to the reflection of the? $A$ -excircle over the? $A$ -angle bisector. But it is well-known that the? $A$ -excenter lies on the? $A$ -angle bisector, so the? $A$ -excircle must be preserved under reflection over the? $A$ -excircle. Thus? $B'C'$ ?is tangent to the? $A$ -excircle.Yet for all lines parallel to? $EF$ , there are only two lines tangent to the? $A$ -excircle, and only one possibility for? $EF$ , so? $EF = B'C'$ .

Thus?as? $ABB'$ ?is isoceles, $[ABC] = \frac{1}{2} \cdot AC \cdot BE = \frac{AC}{2} \cdot \sqrt{AB^2 - AE^2} = \frac{AC}{2} \cdot \sqrt{AB^2 - AB'^2} = \frac{AC}{2} \cdot \sqrt{AB^2 - AB^2} = 0,$ contradiction. -alifenix-

Solution 2

The answer is no.

Suppose otherwise. Consider the reflection over the bisector of? $\angle BAC$ . This swaps rays? $AB$ ?and? $AC$ ; suppose? $E$ ?and? $F$ ?are sent to? $E'$ ?and? $F'$ . Note that the? $A$ -excircle is fixed, so line? $E'F'$ ?must also be tangent to the? $A$ -excircle.

Since? $BEFC$ ?is cyclic, we obtain? $\measuredangle ECB = \measuredangle EFB = \measuredangle EF'E'$ , so? $\overline{E'F'} \parallel \overline{BC}$ . However,?as? $\overline{EF}$ ?is a chord in the circle with diameter? $\overline{BC}$ ,? $EF \le BC$ .

If? $EF < BC$ ?then? $E'F' < BC$ ?too, so then? $\overline{E'F'}$ ?lies inside? $\triangle ABC$ ?and cannot be tangent to the excircle.

The remaining case is when? $EF = BC$ . In this case,? $\overline{EF}$ ?is also a diameter, so? $BECF$ ?is a rectangle. In particular? $\overline{BE} \parallel \overline{CF}$ . However, by the existence of the orthocenter, the lines? $BE$ ?and? $CF$ ?must intersect, contradiction.

Problem 5

Solution 1

Note that there are? $(2n)!$ ?ways to choose? $S_{1, 0}, S_{2, 0}... S_{n, 0}, S_{n, 1}, S_{n, 2}... S{n, n}$ , because there are? $2n$ ?ways to choose which number? $S_{1, 0}$ ?is,? $2n-1$ ?ways to choose which number to append to make? $S_{2, 0}$ ,? $2n-2$ ?ways to choose which number to append to make? $S_{3, 0}$ ... After that, note that? $S_{n-1, 1}$ ?contains the? $n-1$ ?in? $S_{n-1. 0}$ ?and 1 other element chosen from the 2 elements in? $S_{n, 1}$ ?not in? $S_{n-1, 0}$ ?so there are 2 ways for? $S_{n-1, 1}$ . By the same logic there are 2 ways for? $S_{n-1, 2}$ ?as?well so? $2^n$ ?total ways for all? $S_{n-1, j}$ , so doing the same thing? $n-1$ ?more times yields a final answer of? $(2n)!\cdot 2^{n^2}$ .

Solution 2

There are? $\frac{(2n)!}{2^n}$ ?ways to choose? $S_{0,0}, S_{1,1} .... S_{n,n}$ . Since, there are? $\binom{2n}{2}$ ?ways to choose? $S_{1,1}$ , and after that, to generate? $S_{2,2}$ , you take? $S_{1,1}$ and add 2 new elements, getting you? $\binom{2n-2}{2}$ ?ways to generate? $S_{2,2}$ . And you can keep going down the line, and you get that there are? $\frac{(2n)!}{2^n}$ ways to pick? $S_{0,0}, S_{1,1} ... S_{n,n}$ ?Then we can fill out the rest of the gird. First, let’s prove a lemma.

Lemma

Claim:?If we know what? $S_{a,b}$ ?is and what? $S_{a+1,b+1}$ ?is, then there are 2 choices for both? $S_{a,b+1}$ ?and? $S_{a+1,b}$ .

Proof:?Note? $a \leq a+1$ ?and? $b \leq b+1$ , so? $S_{a,b}\subseteq S_{a+1,b+1}$ . Let? $A$ ?be a set that contains all the elements in? $S_{a+1,b+1}$ ?that are not in? $S_{a,b}$ .? $A = S_{a+1,b+1} - S_{a,b}$ . We know? $S_{a+1,b+1}$ ?contains total? $a+b+2$ ?elements. And? $S_{a,b}$ ?contains total? $a+b$ ?elements. That means? $A$ ?contains only 2 elements since? $(a+b+2)-(a+b) = 2$ . Let’s call these 2 elements? $m, n$ .? $A = \{m, n\}$ .? $S_{a,b+1}$ ?contains 1 elements more than? $S_{a,b}$ and 1 elements less than? $S_{a+1,b+1}$ . That 1 elements has to select from? $A$ . It’s easy to see? $S_{a,b+1} = S_{a,b}\cup \{m\}$ ?or? $S_{a,b+1} = S_{a,b}\cup \{n\}$ , so there are 2 choice for? $S_{a,b+1}$ . Same thing applies to? $S_{a+1,b}$ .

Filling in the rest of the grid

We used our proved lemma, and we can fill in? $S_{0,1}, S_{1,2} ... S_{n-1,n}$ ?then we can fill in the next diagonal, until all? $S_{i,j}$ ?are filled, where? $i \leq j$ . But, we haven’t finished everything! Fortunately, filling out the rest of the diagonals in a similar fashion is pretty simple. And, it’s easy to see that we have made? $n(n+1)$ ?decisions, each with 2 choices, when filling out the rest of the grid, so there are? $2^{n(n+1)}$ ?ways to finish off.

Finishing off

To finish off, we have? $\frac{(2n)!}{2^n} \cdot 2^{n(n+1)}$ ?ways to fill in the gird, which gets us? $\boxed{(2n)! \cdot 2^{n^2}}$

Problem 6

Solution

We claim that all odd? $m, n$ ?work if? $m+n$ ?is a positive power of 2.

Proof: We first prove that? $m+n=2^k$ ?works. By weighted averages we have that? $\frac{n(\frac{m}{n})+(2^k-n)\frac{n}{m}}{2^k}=\frac{m+n}{2^k}=1$ ?can be written, so the solution set does indeed work. We will now prove these are the only solutions.

Assume that? $m+n\ne 2^k$ , so then? $m+n\equiv 0\pmod{p}$ ?for some odd prime? $p$ . Then? $m\equiv -n\pmod{p}$ , so? $\frac{m}{n}\equiv \frac{n}{m}\equiv -1\pmod{p}$ . We see that the arithmetic mean is? $\frac{-1+(-1)}{2}\equiv -1\pmod{p}$ ?and the harmonic mean is? $\frac{2(-1)(-1)}{-1+(-1)}\equiv -1\pmod{p}$ , so if 1 can be written then? $1\equiv -1\pmod{p}$ ?and? $2\equiv 0\pmod{p}$ ?which is obviously impossible, and we are done.