【全网首发】2021USAJMO 真题及答案

【全网首发】2021USAJMO 真题及答案

文末有答案

Problem 1

Let $\mathbb{N}$ denote the set of positive integers. Find all functions $f : \mathbb{N} \rightarrow \mathbb{N}$ such that for positive integers $a$ and $b,$\[f(a^2 + b^2) = f(a)f(b) \text{ and } f(a^2) = f(a)^2.\]

Problem 2

Rectangles $BCC_1B_2,$ $CAA_1C_2,$ and $ABB_1A_2$ are erected outside an acute triangle $ABC.$ Suppose that\[\angle BC_1C+\angle CA_1A+\angle AB_1B=180^{\circ}.\]Prove that lines $B_1C_2,$ $C_1A_2,$ and $A_1B_2$ are concurrent.

Problem 3

An equilateral triangle $\Delta$ of side length $L>0$ is given. Suppose that $n$ equilateral triangles with side length 1 and with non-overlapping interiors are drawn inside $\Delta$, such that each unit equilateral triangle has sides parallel to $\Delta$, but with opposite orientation. (An example with $n=2$ is drawn below.)[asy] draw((0,0)--(1,0)--(1/2,sqrt(3)/2)--cycle,linewidth(0.5)); filldraw((0.45,0.55)--(0.65,0.55)--(0.55,0.55-sqrt(3)/2*0.2)--cycle,gray,linewidth(0.5)); filldraw((0.54,0.3)--(0.34,0.3)--(0.44,0.3-sqrt(3)/2*0.2)--cycle,gray,linewidth(0.5)); [/asy]Prove that\[n \leq \frac{2}{3} L^{2}.\]

Problem 4

Carina has three pins, labeled $A, B$, and $C$, respectively, located at the origin of the coordinate plane. In a move, Carina may move a pin to an adjacent lattice point at distance $1$ away. What is the least number of moves that Carina can make in order for triangle $ABC$ to have area 2021?

(A lattice point is a point $(x, y)$ in the coordinate plane where $x$ and $y$ are both integers, not necessarily positive.)

 

Problem 5

A finite set $S$ of positive integers has the property that, for each $s \in S,$ and each positive integer divisor $d$ of $s$, there exists a unique element $t \in S$ satisfying $\text{gcd}(s, t) = d$. (The elements $s$ and $t$ could be equal.)

Given this information, find all possible values for the number of elements of $S$.

Problem 6

Let $n \geq 4$ be an integer. Find all positive real solutions to the following system of $2n$ equations:\begin{align*} a_{1} &=\frac{1}{a_{2 n}}+\frac{1}{a_{2}}, & a_{2}&=a_{1}+a_{3}, \\ a_{3}&=\frac{1}{a_{2}}+\frac{1}{a_{4}}, & a_{4}&=a_{3}+a_{5}, \\ a_{5}&=\frac{1}{a_{4}}+\frac{1}{a_{6}}, & a_{6}&=a_{5}+a_{7}, \\ &\vdots \\ a_{2 n-1}&=\frac{1}{a_{2 n-2}}+\frac{1}{a_{2 n}}, & a_{2 n}&=a_{2 n-1}+a_{1} \end{align*}

 

参考答案及详解注册登录可见:

Problem 1

Solution

I claim that the only function $f$ that satisfies the constraints outlined within the problem is the function $f(n) = 1$ for all positive integers $n$.

We will proceed with strong induction. The base case is simple, as plugging $a=1$ into the second equation given within the problem gives $f(1)=f(1)^2$. Since $f(n)$ can only return a positive integer value, we have that $f(1)=1$.

Now we proceed with the inductive step. If the next number $n$ is either a perfect square or can be represented as a sum of two perfect squares, then obviously $f(n)=1$, as it is either the product of two $f$-values that are both equal to $1$ from the inductive assumption or is the square of an $f$-value that is equal to $1$, again due to the inductive assumption. Otherwise, we can use the Sum of Two Squares Theorem, which tells us that $n$has at least one prime in its prime factorization that is $3(mod 4)$ and is raised to an odd power.

Lemma 1: Given that $a^2+b^2=c^2$ and $f(b)=f(c)=1$, we then have $f(a)=1$.

Proof: Note that the first condition in the problem tells us that $f(a^2+b^2)=f(a)f(b)$, or $f(c^2)=f(a)f(b)$. Using the second condition gives us $f(c)^2=f(a)f(b)$. Plugging in the values of $f(b)$ and $f(c)$ gives us that $f(a)=1$.

Now we will attempt to repeatedly remove prime factors that are $3(mod 4)$ and taken to an odd power, and we will move from the largest prime down to the smallest prime that satisfies above conditions. The prime factors will be removed by constructing a Pythagorean Triple with the prime being the smallest leg in the form of $p,\frac{p^2-1}{2},\frac{p^2+1}{2}$(this will always work as $p\neq 2$(not 3 mod 4), and this method works via Lemma 1). We will then prove the ending numbers that we achieve via removing all the $(\text{mod } 4)$ primes(which I will refer to as "tips") are equal to 1 b/c they can be expressed as the sum of two squares or is a perfect square(Sum of Two Squares Theorem). For example, if we took the number $21$, we would first aim to remove the $7$ by splitting it into $24$ and $25$, so $21$ would become $72$ and $75$$75$ is divisible by $3$ to an odd power, so we transform it into $100$ and $125$. These two don't have any divisors that are $3 (\text{mod } 4)$ raised to an odd power so we leave it alone, as sum of two squares will work on them or they are perfect squares. $72$ does have a prime factor that is $3(\text{mod } 4)$, but it is an even power so we leave it alone. In this case, the tips are $72$$100$, and $125$. However, now we need to prove two key facts: using this Pythagorean Triple Method will never generate another $3(\text{mod } 4)$ prime that is bigger than the current one we are working on or create more primes or keep the same number of primes in the tips' prime factorizations., as otherwise it could cause an infinite cycle, and also we must prove when we use Sum of Two Squares/Perfect Square given in the second condition on the tips the square root of the square(s) used will never be greater than or equal to $n$.

The first claim can be proved rather simply. Note that $\frac{p^2-1}{2}$ can have no prime factors greater than or equal to $p$, as it can be factored as $(p-1)(\frac{p+1}{2})$, which are both less than $p$ and are integers($p+1$ must be an integer due to $p$ must being odd(not equal to $2$)). For $\frac{p^2+1}{2}$, we can prove something a bit more general.

Lemma 2: For any positive integer $n$, all prime factors of $n^2+1$ must be $1(\text{mod } 4)$.

Proof: Note that if $n^2+1\equiv 0(\text{mod } p)$, then we also must have $(n^2+1)(n^2-1)=(n^4-1)\equiv 0(\text{mod } p)$, or $n^4 \equiv 1(\text{mod } p)$. Now we can apply Fermat's Little Theorem to obtain $n^{p-1}\equiv 1(\text{mod } p)$. Note that since $n$ and $n^2$ are obviously not $1(\text{mod } p)$, as $n^2\equiv -1 (\text{mod } p)$, we have that $p-1$ is a multiple of $4$, or $p \equiv 1(\text{mod } 4)$.

We can simply apply Lemma 2 to $p^2+1$ as $2$ is obviously not $3(\text{mod } 4)$, and this means that a prime factor $3(\text{mod } 4)$ will never be generated from this term. This completes the first of our two claims.

Now we proceed to the second of our two claims. Note that every time we use the method on $n$ based on prime $p$, we will multiply by around $\frac{p}{2}$, clearly less than $p$(if we multiply by $p$ we would get $p^2$ which is clearly greater than $\frac{p^2+1}{2}$). We will never have to use the same prime twice in our method, so at max in the end we will multiply $n$ by the product of a little less than all $3(mod 4)$ primes that divide it, which is less than $n$itself for $n$ greater than or equal to $3$(the smallest 3 mod 4 prime), meaning that the largest number that we must use two squares on that is generated by out method is less than $n^2$. We need to prove that the two squares that sum to this are both less than $n$, which is quite trivial, as they are less than $\sqrt{n^2}$, which obviously means it must be less than $n$. This proves the second of our claims.

This completes the second case of the inductive step, and therefore completes both the induction and the problem. ~Solution by hyxue

Solution 2 (Taken from Twitch Solves ISL)

The Answer is $\boxed{f\equiv 1}$ which works but we want to prove that it's the only one. Claim: If $f(a)=f(b)=1$ and a>b, then $f(a^2-b^2)= f(2ab)= 1$. Proof: We can write $1=f(a)=f(b)= f(a^2+b^2)= \sqrt{f((a^2+b^2)^2)} = \sqrt{f((a^2-b^2)^2+ (2ab)^2} = \sqrt{f(a^2-b^2)f(2ab)}$. We set it to $a=b=1$ and we get that $f(1)=f(2)=1$. Easily by Induction it shows f(n)=1. We take if $n=2k$ take $(u,v)=(k,1)$ which $2uv=n$. If $n=2k+1$, just take $(u,v)= (k+1,k)$ which $u^2-v^2=n$. Thus the only answer is $\boxed{f\equiv 1}$ and we are done.

Solution 3 (clear Solution 2)

The answer is $\boxed{f\equiv 1}$, which works. To show it is necessary, we first get $f(1)=f(1)^2$, so $f(1)=1$. Then, we get $f(2)=f(1^2 + 1^2)=f(1)^2 =1$.

The following claim finishes the problem via induction:

Claim: If $f(n)=f(n-1)=1$ for $n \ge 2$, we have $f(2n)=f(2n-1)=1$.

Proof: Note that $f(n^2+1)=f(n)f(1)=1$, so\[1=f(n^2+1)^2 = f((n^2+1)^2)=f(2n)f(n^2 -1)\]implies $f(2n)=1$.

Note that $f(2n^2 -2n+1)=f(n)f(n-1)=1$, so\[1=f(2n^2 - 2n+1)^2 = f((2n^2-2n+1)^2)=f(2n-1)f(2n^2 -2n)\]implies $f(2n-1)=1$$\square$

Thus, the only solution is $\boxed{f\equiv 1}$.

Problem 2

Solution

Leonard my dude.png

We first claim that the three circles $(BCC_1B_2),$ $(CAA_1C_2),$ and $(ABB_1A_2)$ share a common intersection.

Let the second intersection of $(BCC_1B_2)$ and $(CAA_1C_2)$ be $X$. Then\begin{align*} \angle AXC &= 360^\circ - \angle BXA - \angle CXB \\ &= 360^\circ - (180^\circ - \angle AB_1B + 180^\circ - \angle BC_1C) \\& = 180^\circ - \angle CA_1A, \end{align*}which implies that $AA_1C_2CX$ is cyclic as desired.

Now we show that $X$ is the intersection of $B_1C_2,$ $C_1A_2,$ and $A_1B_2.$ Note that $\angle C_1XB = \angle BXA_2 = 90^\circ,$ so $A_2, X, C_1$ are collinear. Similarly, $B_1, X, C_2$ and $A_1, X, B_2$ are collinear, so the three lines concur and we are done.

Problem 4

Solution 1

The answer is $128$, achievable by $A=(10,0), B=(0,-63), C=(-54,1)$. We now show the bound.

We first do the following optimizations:

-if you have a point goes both left and right, we may obviously delete both of these moves and decrease the number of moves by $2$.

-if all of $A,B,C$ lie on one side of the plane, for example $y>0$, we shift them all down, decreasing the number of moves by $3$, until one of the points is on $y=0$ for the first time.

Now we may assume that $A=(a,d)$$B=(b,-e)$$C=(-c,f)$ where $a,b,c,d,e,f \geq 0$. Note we may still shift all $A,B,C$ down by $1$ if $d,f>0$, decreasing the number of moves by $1$, until one of $d,f$ is on $y=0$ for the first time. So we may assume one of $(a,b)$ and $(d,f)$ is $0$, by symmetry. In particular, by shoelace the answer to 2021 JMO Problem 4 is the minimum of the answers to the following problems:

Case 1 (where $a=d=0$) if $wx-yz=4042$, find the minimum possible value of $w+x+y+z$.

Case 2 (else) $wy+xy+xz=(w+x)(y+z)-wz=4042$, find the minimum possible value of $w+x+y+z$.

Note that $(m+n)^2=4mn+(m-n)^2$ so if $m+n$ is fixed then $mn$ is maximized exactly when $|m-n|$ is minimized. In particular, if $m+n \leq 127$ then $mn-op \leq mn \leq 63*64 = 4032 <4042$ as desired.


AMC8/AMC10/AMC12/AIME