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

2018 USAJMO Problems真题及答案

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

2018 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

For each positive integer $n$ , find the number of $n$ -digit positive integers that satisfy both of the following conditions:

$bullet$ no two consecutive digits are equal, and

$bullet$ the last digit is a prime.

Problem 2

Let $a,b,c$ be positive real numbers such that $a+b+c=4sqrt[3]{abc}$ . Prove that $[2(ab+bc+ca)+4min(a^2,b^2,c^2)ge a^2+b^2+c^2.]$

Problem 3

( $*$ ) Let $ABCD$ be a quadrilateral inscribed in circle $omega$ with $overline{AC} perp overline{BD}$ . Let $E$ and $F$ be the reflections of $D$ over lines $BA$ and $BC$ , respectively, and let $P$ be the intersection of lines $BD$ and $EF$ . Suppose that the circumcircle of $triangle EPD$ meets $omega$ at $D$ and $Q$ , and the circumcircle of $triangle FPD$ meets $omega$ at $D$ and $R$ . Show that $EQ = FR$ .

Day 2

Problem 4

Triangle $ABC$ is inscribed in a circle of radius 2 with $angle ABC geq 90^circ$ , and $x$ is a real number satisfying the equation $x^4 + ax^3 + bx^2 + cx + 1 = 0$ , where $a=BC,b=CA,c=AB$ . Find all possible values of $x$ .

Problem 5

Let $p$ be a prime, and let $a_1, dots, a_p$ be integers. Show that there exists an integer $k$ such that the numbers $[a_1 + k, a_2 + 2k, dots, a_p + pk]$ produce at least $tfrac{1}{2} p$ distinct remainders upon division by $p$ .

Problem 6

Karl starts with $n$ cards labeled $1,2,3,dots,n$ lined up in a random order on his desk. He calls a pair $(a,b)$ of these cards swapped if $a>b$ and the card labeled $a$ is to the left of the card labeled $b$ . For instance, in the sequence of cards $3,1,4,2$ , there are three swapped pairs of cards, $(3,1)$ , $(3,2)$ , and $(4,2)$ .

He picks up the card labeled 1 and inserts it back into the sequence in the opposite position: if the card labeled 1 had $i$ card to its left, then it now has $i$ cards to its right. He then picks up the card labeled $2$ and reinserts it in the same manner, and so on until he has picked up and put back each of the cards $1,2,dots,n$ exactly once in that order. (For example, the process starting at $3,1,4,2$ would be $3,1,4,2to 3,4,1,2to 2,3,4,1to 2,4,3,1to 2,3,4,1$ .)

Show that, no matter what lineup of cards Karl started with, his final lineup has the same number of swapped pairs as the starting lineup.

2018USAJMO真题参考答案及详解

Problem 1

Solution 1

The answer is $boxed{frac{2}{5}left(9^n+(-1)^{n+1}right)}$ .

Suppose $a_n$ denotes the number of $n$ -digit numbers that satisfy the condition. We claim $a_n=4cdot 9^{n-1}-a_{n-1}$ , with $a_1=4$ . $textit{Proof.}$ It is trivial to show that $a_1=4$ . Now, we can do casework on whether or not the tens digit of the $n$ -digit integer is prime. If the tens digit is prime, we can choose the digits before the units digit in $a_{n-1}$ ways and choose the units digit in $3$ ways, since it must be prime and not equal to the tens digit. Therefore, there are $3a_{n-1}$ ways in this case.

If the tens digit is not prime, we can use complementary counting. First, we consider the number of $(n-1)$ -digit integers that do not have consecutive digits. There are $9$ ways to choose the first digit and $9$ ways to choose the remaining digits. Thus, there are $9^{n-1}$ integers that satisfy this. Therefore, the number of those $(n-1)$ -digit integers whose units digit is not prime is $9^{n-1}-a_{n-1}$ . It is easy to see that there are $4$ ways to choose the units digit, so there are $4left(9^{n-1}-a_{n-1}right)$ numbers in this case. It follows that $[a_n=3a_{n-1}+4left(9^{n-1}-a_{n-1}right)=4cdot 9^{n-1}-a_{n-1},]$ and our claim has been proven.

Then, we can use induction to show that $a_n=frac{2}{5}left(9^n+(-1)^{n+1}right)$ . It is easy to see that our base case is true, as $a_1=4$ . Then, $[a_{n+1}=4cdot 9^n-a_n=4cdot 9^n-frac{2}{5}left(9^n+(-1)^{n+1}right)=4cdot 9^n-frac{2}{5}cdot 9^n-frac{2}{5}(-1)^{n+1},]$ which is equal to $[a_{n+1}=left(4-frac{2}{5}right)cdot 9^n-frac{2}{5}cdotfrac{(-1)^{n+2}}{(-1)}=frac{18}{5}cdot 9^n+frac{2}{5}cdot(-1)^{n+2}=frac{2}{5}left(9^{n+1}+(-1)^{n+2}right),]$ as desired.

Solution by TheUltimate123.

Solution 2

The answer is $boxed{frac{2}{5}left(9^n-(-1)^{n}right)}$ .

As in the first solution, let $a_n$ denote the number of $n$ -digit numbers that satisfy the condition. Clearly $a_1 = 4$ and $a_2 = 32$ . We claim that for $n geq 3$ we have the recurrence $a_n = 8a_{n-1} + 9a_{n-2}$ .

To prove this, we split the $n$ -digit numbers satisfying the conditions into cases depending on whether or not the second digit is $0$ . If the second digit is nonzero, our number is formed from one of the $a_{n-1}$ numbers with one fewer digit satisfying the conditions, times $8$ possible choices of adding a digit to the left. If the second digit is zero, our number is formed from one of the $a_{n-2}$ numbers with two fewer digits satisfying the conditions, times $9$ possible choices of adding $0$ and then any nonzero digit to the left. This proves our claim.

This gives us a linear three-term recurrence. It is well-known that its solution is of the form $c_1r_1^n + c_2r_2^n$ , where the $c_i$ are constants to be determined from the initial conditions $a_1$ and $a_2$ , and $r_1$ and $r_2$ are the roots of the corresponding quadratic equation $x^2 = 8x + 9$ . We solve and get $(x-9)(x+1) = 0$ , so our roots are $r_1 = 9$ and $r_2 = -1$ . Now, we use our conditions $a_1 = 4$ and $a_2 = 32$ to derive the system of linear equations

$[9c_1 - c_2 = 4]$ $[81c_1 + c_2 = 32]$

Solving this system yields $c_1 = frac{2}{5}$ and $c_2 = -frac{2}{5}$ , and we are done.

Solution by putnam-lowell.

Solution 3

The answer is $boxed{frac{2}{5}left(9^n-(-1)^{n}right)}$ .

As in the first solution, let $a_n$ denote the number of $n$ -digit numbers that satisfy the condition. Clearly $a_1 = 4$ and $a_2 = 32$ .

From here, we proceed by complementary counting. We first count the total amount of numbers that satisfy both bullets but that may have zero as its first digit. The units digit can be one of four primes, and each digit to the left will have 9 choices (any digit but the one that was just used). Then the total for this group of numbers is just $4*9^{n-1}$ .

Now we must subtract all numbers in the above group that have 0 as its first digit. This is just $a_{n-1}$ because for each number in the first group beginning with a zero, we could take away the zero, leaving us with a number that works for the case $n-1$ (this is true because the next number would not be zero, or the consecutive digit requirement would be violated). Then we have the recursive formula $a_n = 4*9^{n-1}-a_{n-1}$ .

To simplify this, we take a look at the first few terms. We see that

$[a_2 = 4*9^1-a_1 = 36-4 = 4(9-1) = 4(9^1-9^0)]$ $[a_3 = 4*9^2-a_2 = 4(81) - 4(9-1) = 4(9^2-9^1+9^0)]$

We see a pattern where $a_n = 4(9^{n-1}-9^{n-2}+9^{n+3}...+(-1)^{n-1}9^0)$ and we can prove that it holds for all $a_n$ because subtracting $a_{n-1}$ from $4(9^n)$ is the same thing as reversing all previous signs of the preceding powers of 9. This constitutes an alternating pattern, which we can calculate as a geometric series. The first term is $4(9^{n-1})$ and the common ratio is $-frac{1}{9}$ , so

$[a_n = frac{4(9^{n-1})(1-(-frac{1}{9})^n)}{1-(-frac{1}{9}))} = frac{4(9^{n-1}-(-1)^n(frac{1}{9}))}{frac{10}{9}} = frac{4(9^{n}-(-1)^n)}{10} = frac{2}{5}left(9^n-(-1)^{n}right)]$

We are done.

Problem 2

Solution 1

WLOG let $a leq b leq c$ . Add $2(ab+bc+ca)$ to both sides of the inequality and factor to get: $[4(a(a+b+c)+bc) geq (a+b+c)^2]$ $[frac{4asqrt[3]{abc}+bc}{2} geq 2sqrt[3]{a^2b^2c^2}]$

The last inequality is true by AM-GM. Since all these steps are reversible, the proof is complete.

Solution 2

WLOG let $a leq b leq c$ . Note that the equations are homogeneous, so WLOG let $c=1$ . Thus, the inequality now becomes $2ab + 2a + 2b + 4 geq a^2 + b^2 + 1$ , which simplifies to $4ab + 3 geq (a-b)^2$ .

Now we will use the condition. Letting $x=a+b$ and $y=a-b$ , we have $x+1=sqrt[3]{16(x^2-y^2)} implies 16y^2=-x^3+13x^2-3x-1$ .

Plugging this into the inequality, we have $2x+3 geq frac{1}{16}(-x^3+13x^2-3x-1) implies x^3-13x^2+35x+49 = (x-7)^2(x+1) geq 0$ , which is true since $x geq 0$ .

Problem 3

Solution 1

First we have that $BE=BD=BF$ by the definition of a reflection. Let $angle DEB = alpha$ and $angle DFB = beta.$ Since $triangle DBE$ is isosceles we have $angle BDE = alpha.$ Also, we see that $angle BDE = angle CAB = angle CDB = alpha,$ using similar triangles and the property of cyclic quadrilaterals. Similarly, $[angle DFB = angle FDB = angle ACB = angle ADB = beta.]$ Now, from $BE=BD=BF$ we know that $B$ is the circumcenter of $triangle DEF.$ Using the properties of the circumcenter and some elementary angle chasing, we find that $[angle DPE = 90^{circ} + beta - alpha.]$

Now, we claim that $Q$ is the intersection of ray $overrightarrow{EB}$ and the circumcircle of $ABCD.$ To prove this, we just need to show that $DEPQ$ is cyclic by this definition of $Q.$ We have that $[angle DQE = angle DCB = angle DCA + angle ACB = (90^{circ}-alpha)+beta.]$ We also have from before that $[angle DPE = 90+beta-alpha,]$ so $angle DQE=angle DPE$ and this proves the claim.

We can use a similar proof to show that $F, B, R$ are collinear.

Now, $DP$ is the radical axis of the circumcircles of $triangle EDP$ and $triangle FDP.$ Since $B$ lies on $DP,$ and $E, Q$ lie on the circumcircle of $triangle EPD$ and $F, R$ lie on the circumcircle of $triangle FPD,$ we have that $[BF cdot BR = BE cdot BQ.]$ However, $BF=BE,$ so $BR=BQ.$ Since $E, B, Q$ are collinear and so are $F, B, R$ we can add these $2$ equations to get $[EQ=BE+BQ=BF+BR=FR,]$ which completes the proof.

Problem 4

Solution

Notice that $[x^4 + ax^3 + bx^2 + cx + 1 = left(x^2 + frac{a}{2}xright)^2 + left(frac{c}{2}x + 1right)^2 + left(b - frac{a^2}{4} - frac{c^2}{4}right)x^2.]$ Thus, if $b > frac{a^2}{4} + frac{c^2}{4},$ then the expression above is strictly greater than $0$ for all $x,$ meaning that $x$ cannot satisfy the equation $x^4 + ax^3 + bx^2 + cx + 1 = 0.$ It follows that $blefrac{a^2}{4} + frac{c^2}{4}.$

Since $angle ABCge 90^{circ},$ we have $b^2ge a^2 + c^2.$ From this and the above we have $4ble a^2 + c^2le b^2,$ so $4ble b^2.$ This is true for positive values of $b$ if and only if $bge 4.$ However, since $triangle ABC$ is inscribed in a circle of radius $2,$ all of its side lengths must be at most the diameter of the circle, so $ble 4.$ It follows that $b=4.$

We know that $4ble a^2 + c^2le b^2.$ Since $4b = b^2 = 16,$ we have $4b = a^2 + c^2 = b^2 = 16.$

The equation $x^4 + ax^3 + bx^2 + cx + 1 = 0$ can be rewritten as $left(x^2 + frac{a}{2}xright)^2 + left(frac{c}{2}x + 1right)^2 = 0,$ since $b = frac{a^2}{4} + frac{c^2}{4}.$ This has a real solution if and only if the two separate terms have zeroes in common. The zeroes of $left(x^2 + frac{a}{2}xright)^2$ are $0$ and $-frac{a}{2},$ and the zero of $left(frac{c}{2}x + 1right)^2 = 0$ is $-frac{2}{c}.$ Clearly we cannot have $0=-frac{2}{c},$ so the only other possibility is $-frac{a}{2} = -frac{2}{c},$ which means that $ac = 4.$

We have a system of equations: $ac = 4$ and $a^2 + c^2 = 16.$ Solving this system gives $(a, c) = left(sqrt{6}+sqrt{2}, sqrt{6}-sqrt{2}right), left(sqrt{6}-sqrt{2}, sqrt{6}+sqrt{2}right).$ Each of these gives solutions for $x$ as $-frac{sqrt{6}+sqrt{2}}{2}$ and $-frac{sqrt{6}-sqrt{2}}{2},$ respectively. Now that we know that any valid value of $x$ must be one of these two, we will verify that both of these values of $x$ are valid.

First, consider a right triangle $ABC,$ inscribed in a circle of radius $2,$ with side lengths $a = sqrt{6}+sqrt{2}, b = 4, c = sqrt{6}-sqrt{2}.$ This generates the polynomial equation $[x^4 + left(sqrt{6}+sqrt{2}right)x^3 + 4x^2 + left(sqrt{6}-sqrt{2}right)x + 1 = left(frac{sqrt{6}-sqrt{2}}{2}x + 1right)^2left(left(frac{sqrt{6}+sqrt{2}}{2}xright)^2+1right) = 0.]$ This is satisfied by $x=-frac{sqrt{6}+sqrt{2}}{2}.$

Second, consider a right triangle $ABC,$ inscribed in a circle of radius $2,$ with side lengths $a = sqrt{6}-sqrt{2}, b = 4, c = sqrt{6}+sqrt{2}.$ This generates the polynomial equation $[x^4 + left(sqrt{6}-sqrt{2}right)x^3 + 4x^2 + left(sqrt{6}+sqrt{2}right)x + 1 = left(frac{sqrt{6}+sqrt{2}}{2}x + 1right)^2left(left(frac{sqrt{6}-sqrt{2}}{2}xright)^2+1right) = 0.]$ This is satisfied by $x=-frac{sqrt{6}-sqrt{2}}{2}.$

It follows that the possible values of $x$ are $-frac{sqrt{6}+sqrt{2}}{2}$ and $-frac{sqrt{6}-sqrt{2}}{2}.$

Fun fact: these solutions correspond to a $15$ - $75$ - $90$ triangle.

Problem 5

Solution

$textbf{Lemma: }$ For fixed $ineq j,$ where $i, jin{1, 2, ..., p},$ the statement $a_i + ikequiv a_j + jktext{ (mod } ptext{)}$ holds for exactly one $kin {1, 2, ..., p}.$

$textbf{Proof: }$ Notice that the left side minus the right side is congruent to $(a_i - a_j) + (i - j)k$ modulo $p.$ For this difference to equal $0,$ there is a unique solution for $k$ modulo $p$ given by $kequiv (a_j - a_i)(i - j)^{-1}text{ (mod } ptext{)},$ where we have used the fact that every nonzero residue modulo $p$ has a unique multiplicative inverse. Therefore, there is exactly one $kin {1, 2, ..., p}$ that satisfies $a_i + ikequiv a_j + jktext{ (mod } ptext{)}$ for any fixed $ineq j. textbf{ End Lemma}$

Suppose that you have $p$ graphs $G_1, G_2, ..., G_p,$ and graph $G_k$ consists of the vertices $(i, k)$ for all $1le ile p.$ Within any graph $G_k,$ vertices $(i_1, k)$ and $(i_2, k)$ are connected by an edge if and only if $a_{i_1} + i_1kequiv a_{i_2} + i_2ktext{ (mod } ptext{)}.$ Notice that the number of disconnected components of any graph $G_k$ equals the number of distinct remainders when divided by $p$ given by the numbers $a_1 + k, a_2 + 2k, ..., a_p + pk.$

These $p$ graphs together have exactly one edge for every unordered pair of elements of ${1, 2, ..., p},$ so they have a total of exactly $frac{p(p-1)}{2}$ edges. Therefore, there exists at least one graph $G_k$ that has strictly fewer than $frac{p}{2}$ edges, meaning that it has more than $frac{p}{2}$ disconnected components. Therefore, the collection of numbers ${a_i + ik: 1le ile p}$ for this particular value of $k$ has at least $frac{p}{2}$ distinct remainders modulo $p.$ This completes the proof.

Problem 6

Solution

We define a new process $P'$ where, when re-inserting card $i$ , we additionally change its label from $i$ to $n+i$ . For example, an example of $P'$ also starting with $3142$ is: $[3142 longrightarrow 3452 longrightarrow 6345 longrightarrow 6475 longrightarrow 6785.]$ Note that now, each step of $P'$ preserves the number of inversions. Moreover, the final configuration of $P'$ is the same as the final configuration of $P$ with all cards incremented by $n$ , and of course thus has the same number of inversions.