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.