Home » 國際競賽 » 數學國際競賽 » AMC美國數學競賽 » Details

2019 USAMO Problems真題及答案

Category: AMC美國數學競賽, 國際競賽 Date: 2019年8月13日上午10:54

2019 USAMO 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

Let? $\mathbb{N}$ ?be the set of positive integers. A function? $f:\mathbb{N}\to\mathbb{N}$ ?satisfies the equation $\underbrace{f(f(\ldots f}_{f(n)\text{ times}}(n)\ldots))=\frac{n^2}{f(f(n))}$ for all positive integers? $n$ . Given this information, determine all possible values of? $f(1000)$ .

Problem 2

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}$ .

Problem 3

Let? $K$ ?be the set of all positive integers that do not contain the digit? $7$ ?in their base- $10$ ?representation. Find all polynomials? $f$ ?with nonnegative integer coefficients such that? $f(n)\in K$ ?whenever? $n\in K$ .

Day 2

Problem 4

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,\ldots,2n\}$ , for integers? $i,j$ ?with? $0\leq i,j\leq n$ , such that: for all? $0\leq i,j\leq n$ , the set? $S_{i,j}$ ?has? $i+j$ ?elements; and? $S_{i,j}\subseteq S_{k,l}$ ?whenever? $0\leq i\leq k\leq n$ ?and? $0\leq j\leq l\leq n$ .

Problem 5

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.

Problem 6

Find all polynomials? $P$ ?with real coefficients such that $\frac{P(x)}{yz}+\frac{P(y)}{zx}+\frac{P(z)}{xy}=P(x-y)+P(y-z)+P(z-x)$ holds for all nonzero real numbers? $x,y,z$ ?satisfying? $2xyz=x+y+z$ .

Problem 1

Solution

Let? $f^r(x)$ ?denote the result when? $f$ ?is applied to? $x$ ? $r$ ?times.? $\hfill \break \hfill \break$ ?If? $f(p)=f(q)$ , then? $f^2(p)=f^2(q)$ ?and? $f^{f(p)}(p)=f^{f(q)}(q)$

$\implies p^2=f^2(p)\cdot f^{f(p)}(p)=f^2(q)\cdot f^{f(q)}(q)=q^2$

$\implies p=\pm q$

$\implies p=q$ ?since? $p,q>0$ .

Therefore,? $f$ ?is injective. It follows that? $f^r$ ?is also injective.

Lemma 1: If? $f^r(b)=a$ ?and? $f(a)=a$ , then? $b=a$ .

Proof:

$f^r(b)=a=f^r(a)$ ?which implies? $b=a$ ?by injectivity of? $f^r$ .

Lemma 2: If? $f^2(m)=f^{f(m)}(m)=m$ , and? $m$ ?is odd, then? $f(m)=m$ .

Proof:

Let? $f(m)=k$ . Since? $f^2(m)=m$ ,? $f(k)=m$ . So,? $f^2(k)=k$ .? $\newline f^2(k)\cdot f^{f(k)}(k)=k^2$ .

Since? $k\neq0$ ,? $f^{f(k)}(k)=k$

$f^m(k)=k$

$f^{gcd(m, 2)}=k$

$m=f(k)=k$

This proves Lemma 2.

I claim that? $f(m)=m$ ?for all odd? $m$ .

Otherwise, let? $m$ ?be the least counterexample.

Since? $f^2(m)\cdot f^{f(m)}(m)=m^2$ , either

$(1) f^2(m)=k<m$ , contradicted by Lemma 1 since? $k$ ?is odd and? $f(k)=k$ .

$(2) f^{f(m)}(m)=k<m$ , also contradicted by Lemma 1 by similar logic.

$(3) f^2(m)=m$ ?and? $f^{f(m)}(m)=m$ , which implies that? $f(m)=m$ ?by Lemma 2. This proves the claim.

By injectivity,? $f(1000)$ ?is not odd. I will prove that? $f(1000)$ ?can be any even number,? $x$ . Let? $f(1000)=x, f(x)=1000$ , and? $f(k)=k$ ?for all other? $k$ . If? $n$ ?is equal to neither? $1000$ ?nor? $x$ , then? $f^2(n)\cdot f^{f(n)}(n)=n\cdot n=n^2$ . This satisfies the given property.

If? $n$ ?is equal to? $1000$ ?or? $x$ , then? $f^2(n)\cdot f^{f(n)}(n)=n\cdot n=n^2$ ?since? $f(n)$ ?is even and? $f^2(n)=n$ . This satisfies the given property.

Problem 2&3

暫無官方Solutions，可聯系翰林導師進行詳解。歡迎點擊聯系我們資訊翰林顧問！

Problem 4

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}$ .

-Stormersyle

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 5

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.