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{b}{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{b}{2} \right\rfloor + 1$ . But the desired ending configuration has $\left\lfloor \frac{b}{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{b}{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.