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

2017 USAMO Problems真题及答案

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

2017 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

Prove that there are infinitely many distinct pairs $(a,b)$ of relatively prime positive integers $a > 1$ and $b > 1$ such that $a^b + b^a$ is divisible by $a + b.$

Problem 2

Let $m_1, m_2, ldots, m_n$ be a collection of $n$ positive integers, not necessarily distinct. For any sequence of integers $A = (a_1, ldots, a_n)$ and any permutation $w = w_1, ldots, w_n$ of $m_1, ldots, m_n$ , define an $A$ -inversion of $w$ to be a pair of entries $w_i, w_j$ with $i < j$ for which one of the following conditions holds: $[a_i ge w_i > w_j,]$ $[w_j > a_i ge w_i,]$ or $[w_i > w_j > a_i.]$ Show that, for any two sequences of integers $A = (a_1, ldots, a_n)$ and $B = (b_1, ldots, b_n)$ , and for any positive integer $k$ , the number of permutations of $m_1, ldots, m_n$ having exactly $k$ $A$ -inversions is equal to the number of permutations of $m_1, ldots, m_n$ having exactly $k$ $B$ -inversions.

Problem 3

( $*$ ) Let $ABC$ be a scalene triangle with circumcircle $Omega$ and incenter $I$ . Ray $AI$ meets $overline{BC}$ at $D$ and meets $Omega$ again at $M$ ; the circle with diameter $overline{DM}$ cuts $Omega$ again at $K$ . Lines $MK$ and $BC$ meet at $S$ , and $N$ is the midpoint of $overline{IS}$ . The circumcircles of $triangle KID$ and $triangle MAN$ intersect at points $L_1$ and $L_2$ . Prove that $Omega$ passes through the midpoint of either $overline{IL_1}$ or $overline{IL_2}$ .

Day 2

Problem 4

Let $P_1$ , $P_2$ , $dots$ , $P_{2n}$ be $2n$ distinct points on the unit circle $x^2+y^2=1$ , other than $(1,0)$ . Each point is colored either red or blue, with exactly $n$ red points and $n$ blue points. Let $R_1$ , $R_2$ , $dots$ , $R_n$ be any ordering of the red points. Let $B_1$ be the nearest blue point to $R_1$ traveling counterclockwise around the circle starting from $R_1$ . Then let $B_2$ be the nearest of the remaining blue points to $R_2$ travelling counterclockwise around the circle from $R_2$ , and so on, until we have labeled all of the blue points $B_1, dots, B_n$ . Show that the number of counterclockwise arcs of the form $R_i to B_i$ that contain the point $(1,0)$ is independent of the way we chose the ordering $R_1, dots, R_n$ of the red points.

Problem 5

Let $mathbf{Z}$ denote the set of all integers. Find all real numbers $c > 0$ such that there exists a labeling of the lattice points $( x, y ) in mathbf{Z}^2$ with positive integers for which: only finitely many distinct labels occur, and for each label $i$ , the distance between any two points labeled $i$ is at least $c^i$ .

Problem 6

Find the minimum possible value of $[frac{a}{b^3+4}+frac{b}{c^3+4}+frac{c}{d^3+4}+frac{d}{a^3+4}]$ given that $a$ , $b$ , $c$ , $d$ are nonnegative real numbers such that $a+b+c+d=4$ .

2017USAMO真题参考答案及详解

Problem 1

Solution 1

Let $n=a+b$ . Since $gcd(a,b)=1$ , we know $gcd(a,n)=1$ . We can rewrite the condition as

$[a^{n-a}+(n-a)^a equiv 0 mod{n}]$ $[a^{n-a}equiv-(-a)^a mod{n}]$ Assume $a$ is odd. Since we need to prove an infinite number of pairs exist, it suffices to show that infinitely many pairs with $a$ odd exist.

Then we have $[a^{n-a}equiv a^a mod{n}]$ $[1 equiv a^{2a-n} mod{n}]$

We know by Euler's theorem that $a^{varphi(n)} equiv 1 mod{n}$ , so if $2a-n=varphi(n)$ we will have the required condition.

This means $a=frac{n+varphi(n)}{2}$ . Let $n=2p$ where $p$ is a prime, $pequiv 1mod{4}$ . Then $varphi(n) = 2p*left(1-frac{1}{2}right)left(1-frac{1}{p}right) = p-1$ , so $[a = frac{2p+p-1}{2} = frac{3p-1}{2}]$ Note the condition that $pequiv 1mod{4}$ guarantees that $a$ is odd, since $3p-1 equiv 2mod{4}$

This makes $b = frac{p+1}{2}$ . Now we need to show that $a$ and $b$ are relatively prime. We see that $[gcdleft(frac{3p-1}{2},frac{p+1}2right)=frac{gcd(3p-1,p+1)}{2}]$ $[=frac{gcd(p-3,4)}{2}=frac22=1]$ By the Euclidean Algorithm.

Therefore, for all primes $p equiv 1mod{4}$ , the pair $left(frac{3p-1}{2},frac{p+1}{2}right)$ satisfies the criteria, so infinitely many such pairs exist.

Solution 2

Take $a=2n-1, b=2n+1, ngeq 2$ . It is obvious (use the Euclidean Algorithm, if you like), that $gcd(a,b)=1$ , and that $a,b>1$ .

Note that

$[a^2 = 4n^2-4n+1 equiv 1 (bmod 4n)]$

$[b^2 = 4n^2+4n+1 equiv 1 (bmod 4n)]$

$[a^b+b^a = a(a^2)^n+b(b^2)^{n-1} equiv]$ $[acdot 1^n + bcdot 1^{n-1} equiv a+b = 4n equiv 0 (bmod 4n)]$

Since $a+b=4n$ , all such pairs work, and we are done.

Solution 3

Let $x$ be odd where $x>1$ . We have $x^2-1=(x-1)(x+1),$ so $x^2-1 equiv 0 pmod{2x+2}.$ This means that $x^{x+2}-x^x equiv 0 pmod{2x+2},$ and since x is odd, $x^{x+2}+(-x)^x equiv 0 pmod{2x+2},$ or $x^{x+2}+(x+2)^x equiv 0 pmod{2x+2},$ asdesired.

Problem 2&3

暂无官方Solutions，可联系翰林导师进行详解。欢迎点击联系我们资讯翰林顾问！

Problem 4

Solution

I define a sequence to be, starting at $(1,0)$ and tracing the circle counterclockwise, and writing the color of the points in that order - either R or B. For example, possible sequences include $RB$ , $RBBR$ , $BBRRRB$ , $BRBRRBBR$ , etc. Note that choosing an $R_1$ is equivalent to choosing an $R$ in a sequence, and $B_1$ is defined as the $B$ closest to $R_1$ when moving rightwards. If no $B$ s exist to the right of $R_1$ , start from the far left. For example, if I have the above example $RBBR$ , and I define the 2nd $R$ to be $R_1$ , then the first $B$ will be $B_1$ . Because no $R$ or $B$ can be named twice, I can simply remove $R_1$ and $B_1$ from my sequence when I choose them. I define this to be a move. Hence, a possible move sequence of $BBRRRB$ is: $BBR_1RRB_1implies B_2BRR_2implies B_3R_3$

Note that, if, in a move, $B_n$ appears to the left of $R_n$ , then $stackrel{frown}{R_nB_n}$ intersects $(1,0)$

Now, I define a commencing $B$ to be a $B$ which appears to the left of all $R$ s, and a terminating $R$ to be a $R$ which appears to the right of all $B$ s. Let the amount of commencing $B$ s be $j$ , and the amount of terminating $R$ s be $k$ , I claim that the number of arcs which cross $(1,0)$ is constant, and it is equal to $text{max}(j,k)$ . I will show this with induction.

Base case is when $n=1$ . In this case, there are only two possible sequences - $RB$ and $BR$ . In the first case, $stackrel{frown}{R_1B_1}$ does not cross $(1, 0)$ , but both $j$ and $k$ are $0$ , so $text{max}(j,k)=0$ . In the second example, $j=1$ , $k=1$ , so $text{max}(j,k)=1$ . $stackrel{frown}{R_1B_1}$ crosses $(1,0)$ since $B_1$ appears to the left of $R_1$ , so there is one arc which intersects. Hence, the base case is proved.

For the inductive step, suppose that for a positive number $n$ , the number of arcs which cross $(1,0)$ is constant, and given by $text{max}(j, k)$ for any configuration. Now, I will show it for $n+1$ .

Suppose I first choose $R_1$ such that $B_1$ is to the right of $R_1$ in the sequence. This implies that $stackrel{frown}{R_1B_1}$ does not cross $(1,0)$ . But, neither $R_1$ nor $B_1$ is a commencing $B$ or terminating $R$ . These numbers remain constant, and now after this move we have a sequence of length $2n$ . Hence, by assumption, the total amount of arcs is $0+text{max}(j,k)=text{max}(j,k)$ .

Now suppose that $R_1$ appears to the right of $B_1$ , but $B_1$ is not a commencing $B$ . This implies that there are no commencing $B$ s in the series, because there are no $B$ s to the left of $B_1$ , so $j=0$ . Note that this arc does intersect $(1,0)$ , and $R_1$ must be a terminating $R$ . $R_1$ must be a terminating $R$ because there are no $B$ s to the right of $R_1$ , or else that $B$ would be $B_1$ . The $2n$ length sequence that remains has $0$ commencing $B$ s and $k-1$ terminating $R$ s. Hence, by assumption, the total amount of arcs is $1+text{max}(0,k-1)=1+k-1=k=text{max}(j,k)$ .

Finally, suppose that $R_1$ appears to the right of $B_1$ , and $B_1$ is a commencing $B$ . We know that this arc will cross $(1,0)$ . Analogous to the previous case, $R_1$ is a terminating $R$ , so the $2n$ length sequence which remains has $j-1$ commencing $B$ s and $k-1$ terminating $R$ s. Hence, by assumption, the total amount of arcs is $1+text{max}(j-1,k-1)=1+text{max}(j,k)-1=text{max}(j,k)$ .

There are no more possible cases, hence the induction is complete, and the number of arcs which intersect $(1,0)$ is indeed a constant which is given by $text{max}(j,k)$ .

-william122

Problem 5

Solution (INCOMPLETE)

For $cle 1,$ we can label every lattice point $1.$ For $cle sqrt[4]{2},$ we can make a "checkerboard" labeling, i.e. label $(x, y)$ with $1$ if $x+y$ is even and $2$ if $x+y$ is odd. One can easily verify that these labelings satisfy the required conditions. Therefore, a labeling as desired exists for all $0 < cle sqrt[4]{2}.$

An iterated version of the checkerboard labeling can actually work for all values $c < sqrt{2}.$ For convenience, define the original lattice grid to be the set of all lattice points in the coordinate plane. Define a modified lattice grid of size $x$ to be a structure similar to the lattice points on the coordinate plane, but with the minimum separation between any two points equaling $x$ (as opposed to $1$ ).

On the first step, assign a label $1$ to half of the points in a checkerboard arrangement. One can see that the points that have not yet been labeled form a modified lattice grid of size $sqrt{2}$ (this lattice grid is also rotated by $45^{circ}$ from the original lattice grid). At this point, for the second step, assign a label $2$ to half of the points, again in a checkerboard arrangement. At this point, the points that have not yet been labeled form a modified lattice grid of size $2$ (and again, it is rotated $45^{circ}$ from the modified lattice grid after the first step). One then continues in this fashion. For the $N^{text{th}}$ step, the points we are labeling are separated by at least $sqrt{2}timesleft(sqrt{2}right)^{N-1} = left(sqrt{2}right)^N > c^N,$ so we know that our labeling at each step is acceptable.

After the $N^{text{th}}$ step (where $N$ is a natural number), the points that have not yet been labeled form a modified lattice grid with size $left(sqrt{2}right)^N.$ Since $c < sqrt{2},$ we will eventually have $left(sqrt{2}right)^N > c^{n+1}$ for some sufficiently large $N.$ At this point, we can label all remaining points in the original lattice grid $N+1,$ and this produces a labeling of all of the lattice points in the plane that satisfies all of the conditions. Therefore, a labeling as desired exists for all $c < sqrt{2}.$

We now prove that no labeling as desired exists for any $cge 2.$ To do this, we will prove that labeling a $2^k$ -by- $2^k$ square grid of lattice points requires at least $k+3$ distinct labels for all natural numbers $k$ ; hence for a sufficiently large section of the lattice plane the number of distinct labels required grows arbitrarily large, so the entire lattice plane cannot be labeled with finitely many distinct labels. We will prove this using induction.

For the base case, $k=1,$ we have four points in a square of side length $1.$ The maximum distance between any two of these points is $sqrt{2} < c^1$ for all $cge 2,$ so all four points must have different labels. This completes the base case.

Now, for the inductive step, suppose that labeling a $2^k$ -by- $2^k$ square grid of lattice points requires at least $k+3$ distinct labels for some natural number $k.$ We will now prove that labeling a $2^{k+1}$ -by- $2^{k+1}$ square grid of lattice points requires at least $k+4$ distinct labels.

Take a $2^{k+1}$ -by- $2^{k+1}$ square grid of lattice points. Divide this grid into four quadrants, $A, B, C,$ and $D.$ By the inductive hypothesis, $A$ requires at least $k+3$ distinct labels. At least one of these labels must be $k+3$ or greater; take one such label and call it $L.$

The largest distance between any two points in the entire grid is $sqrt{2}left(2^{k+1} - 1right) < c^{k+3}$ for all $cge 2.$ Therefore, the label $L$ cannot be used anywhere else in the grid. However, $B, C,$ and $D$ each require at least $k+3$ distinct labels as well by the inductive hypothesis. Thus, they must use at least one label that is not used in $A.$ It follows that the entire grid requires at least $k+4$ distinct labels. This completes the inductive step, and thus we conclude that no labeling as desired exists for any $cge 2.$

I have heard from others that the actual boundary is $sqrt{2}.$ This makes intuitive sense, since the iterated checkerboard labeling outlined above just breaks down at this value (you will be able to get closer and closer to labeling all of the lattice points, but you can never get there, since you will never have $left(sqrt{2}right)^N > c^{n+1}$ ). The inductive argument above seems fairly loose, so I think that it can be sharpened to bring the upper bound down to $sqrt{2},$ but I am not sure yet how exactly to do so. I think the way to do it is to somehow force $2$ new labels (instead of just $1$ ) each time you double the side length of the square grid.

Problem 6

Solution 1

We observe the miraculous identity $[ frac{1}{b^3+4} ge frac14 - frac{b}{12} ]$ since $12-(3-b)(b^3+4) = b(b+1)(b-2)^2 ge 0$ . Moreover, $[ ab+bc+cd+da = (a+c)(b+d) le left( frac{(a+c)+(b+d)}{2} right)^2 = 4. ]$ Thus $[ sum_{text{cyc}} frac{a}{b^3+4} ge frac{a+b+c+d}{4} - frac{ab+bc+cd+da}{12} ge 1 - frac13 = frac23. ]$ This minimum $frac23$ is achieved at $(a,b,c,d) = (2,2,0,0)$ and permutations.