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
Source: USAJMO 2021/4
Tags: USA(J)MO, USAJMO, 2021 usajmo
15.04.2021 20:09
It's not 133
15.04.2021 20:12
The answer was $128$. You basically make optimizations to get it down to (wlog) $A=(a,d)$, $B=(b,-e)$, $C=(-c,f)$ where one of $a,b$ is $0$ and one of $(d,f)$ is $0$, and $a,b,c,d,e,f \geq 0$, and then casework shoelace: there are two cases, (1, where $a=d=0$) $wx-yz=4042$, find the minimum possible value of $w+x+y+z$ (2, else) $(w+x)(y+z)-wz=4042$, find the minimum possible value of $w+x+y+z$ and from here it is clear because $63*64=4032<4042$. Why do I feel like this was a rejected hmmt proposal or something
15.04.2021 20:30
Pretty hard, especially finding the construction. You can show that either one vertex is the origin and the other two are in opposite quadrants (quadrants here include the axes bounding them) or two of the vertices are on one of each axis and the third is in the quadrant not containing either of the other two. Then shoelace and use extremely weak inequalities and a bit of AM-GM to get that you need at least 128.
15.04.2021 20:31
The answer is $\boxed{128},$ achieved by moving $A$ to $(-10,0),$ moving $B$ to $(54,-1),$ and moving $C$ to $(0,63).$ We may assume Carina performs all horizontal moves before vertical moves, as this affects neither the final positions of the pins nor the number of moves necessary. Suppose that after Carina has performed all horizontal moves, the pins are at $(x_1,0),(x_2,0),$ and $(x_3,0)$ respectively. $\textbf{Claim: }$ We may assume WLOG that $x_1\le0=x_2\le x_3.$ $\emph{Proof: }$ Suppose for the sake of contradiction that $x_1\le 0$ and $x_3\ge x_2\ge 0.$ Then, Carina performed at least $-x_1+x_2+x_3$ horizontal moves. If Carina had instead moved the pins to $(x_1-x_2,0),(0,0),$ and $(x_3-x_2,0)$ (which wouldn't affect their relative positions), then she would have performed $$(x_2-x_1)+(x_3-x_2)=x_3-x_1<-x_1+x_2+x_3$$horizontal moves. The case $x_3\ge x_2\ge 0$ can be dealt with similarly, so it is always optimal for $x_1\le 0=x_2\le x_3.$ $\blacksquare$ Now let the y-coordinates of the pins be $y_1,y_2,y_3$ respectively. By Shoelace, $$[ABC]=\frac{1}{2}\left|\underline{(x_1y_2+x_3y_1)-(x_3y_2+x_1y_3)}\right|.$$Immediately after Carina has performed all horizontal moves, the underlined expression is $0.$ Moreover, Increasing $y_1$ by $1$ increases the expression by $x_3$ Increasing $y_2$ by $1$ increases the expression by $x_1-x_3$ Increasing $y_3$ by $1$ increases the expression by $-x_1,$ and the opposite is true for decreasing $y$-coordinates. Therefore, in order for the expression to reach $\pm 4042,$ Carina must perform at least $$\left\lceil\frac{4042}{\max(|x_3|,|x_1-x_3|,|-x_1|)}\right\rceil=\left\lceil\frac{4042}{x_3-x_1}\right\rceil$$vertical moves. This yields a total of $$(x_3-x_1)+\left\lceil\frac{4042}{x_3-x_1}\right\rceil$$moves. It is easy to check that this expression has a minimum of $128,$ as desired.
15.04.2021 20:32
I believe the answer was 128 My construction: (5, 1); (-52, 0); and (0, -70) the maximum area you can create with 127 moves is 63*64/2=2016
15.04.2021 20:36
This problem was so harddddd for its position(I was able to solve it but took me quite some time )
15.04.2021 20:39
How many points is a correct proof and answer but no construction?
15.04.2021 20:39
Awesome_guy wrote: How many points is a correct proof and answer but no construction? usually this would be a 6
15.04.2021 20:41
I proved that the maximum area after n moves is n^2/8 by shoelace bash
15.04.2021 20:48
wow bob you took jmo? you're like in 7th right? I basically considered x and y coordinates separately, showed the median of the x coordinates is 0 to be optimal and same for y, then shoelaced, factored, and stuff to get 128
15.04.2021 20:51
This was the only problem I got :/ I showed that no two of $A,B,C$ can be in in the same direction in any axis, and then there were only 3 cases: the one where $C$ goes both left and down, which we can reduce to $C$ being only moving in one direction. Then all 3 move in only one direction, which we can use AM-GM on easily. If $C$ doesn't move at all, it's just a right triangle.
15.04.2021 20:53
I’m pretty sure my construction was (-6,-9),(58,0),(0,55)
15.04.2021 20:55
Wait what to do after getting ab + ac + bd = 4042
15.04.2021 20:57
add cd to both sides
15.04.2021 21:02
Leonard_my_dude wrote: Wait what to do after getting ab + ac + bd = 4042 Factor it as (a+d)(b+c)-cd=4042, so (a+d)(b+c)≥4042. If (a+b)+(c+d)≤127, then (a+b)(c+d) is maximized by 64*63=4032, so if their sum is less than 128 it is impossible to get a triangle with area greater than 2016
15.04.2021 22:24
Define the rectangular hull (R.H. for brevity) of $\triangle ABC$ as the smallest rectangle with vertices at lattice points and sides parallel to the axes such that $\triangle ABC$ is complete contained in the rectangle. Claim: The area of $\triangle ABC$ is at most $1/2$ of the area of its R.H. Proof: First, consider the case where two of $A,B,C$ are opposite corners of the R.H. Clearly, the segment between these two opposite vertices divides the R.H. in half, so $[ABC]$ cannot exceed $[R.H.]/2$. Now, consider all other cases. Clearly, one vertex of $\triangle ABC$ lies on a corner of the R.H. [asy][asy] import olympiad; import geometry; size(100); pair a, b, c, p, q, r; a = (5, -3); b = (-2,4); c = (-4,0); p = (5,4); q = (-4,4); r = (-4,-3); draw(a--b--c--a--p--q--r--a); label("$L-x$",(b+p)/2,N); label("$x$",(b+q)/2,N); label("$W-y$",(c+r)/2,W); label("$y$",(c+q)/2,W); [/asy][/asy] It suffices to show the area outside $\triangle ABC$ but in the R.H. is at least half of the total R.H. $$\iff \frac{1}{2}\big(xy+L(W-y)+W(L-x)\big)\ge\frac{1}{2}LW$$$$\iff (L-x)(W-y)\ge 0,$$which is obviously true. This proves the claim. Claim: After Carina has made $n$ moves, the perimeter of $\triangle ABC$'s R.H. is at most $2n$. Proof: We use induction. The base cases of $n=0$ and $n=1$ are trivial. Now, assume that this holds for $n$ moves. If, after $n$ moves, the R.H. has dimensions $L\times W$, then, since a move only goes one unit in one direction, the R.H. can have dimensions of $(L+1)\times W$, $L\times(W+1)$, $L\times W$, $(L-1)\times W$, or $L\times (W-1)$. In any case, the perimeter cannot exceed $2(L+W+1)$, which is at most $2(n+1)$ as desired. It is clear that the area of a rectangle with perimeter $P$ is at most $P^2/16$. Therefore, after $n$ moves, the area of the R.H. is at most $\frac{n^2}{4}$, and the area of $\triangle ABC$ is at most $\frac{n^2}{8}$. Solving the inequality $2021\le\frac{n^2}{8}$, we find that $n$ must be at least $128$. Finally, we show that $128$ moves are indeed achievable. Consider the points $A=(-12,0)$, $B=(0,-62)$, and $C=(53,1)$. It takes Carina $128$ moves to reach these points, and the triangle formed by them has area $2021$. This proves the answer is $128$.
15.04.2021 23:55
I misread the problem and thought it meant area at least 2021 Noticed 30 minutes before test ended; wrote a note at top of solution that I misread the problem, but my lower bound of 128 moves is still valid (and my proof of the bound seems to be correct). What score can I expect?
15.04.2021 23:59
How many points do y'all think I would get if I wrote the correct answer with a valid construction?
16.04.2021 00:10
SHZhang wrote: I misread the problem and thought it meant area at least 2021 Noticed 30 minutes before test ended; wrote a note at top of solution that I misread the problem, but my lower bound of 128 moves is still valid (and my proof of the bound seems to be correct). What score can I expect? 5 (2 if super strict, 6 if lenient). kred9 wrote: How many points do y'all think I would get if I wrote the correct answer with a valid construction? I feel the construction was nontrivial enough to earn 1 point.
06.03.2022 05:40
30.03.2022 18:10
For a triangle with vertices $(x_1,y_1)$, $(x_2,y_2)$, $(x_3,y_3)$, let the bounding box of the triangle be the rectangle with vertices $(\min(x_1,x_2,x_3),\min(y_1,y_2,y_3))$, $(\min(x_1,x_2,x_3),\max(y_1,y_2,y_3))$, $(\max(x_1,x_2,x_3),\min(y_1,y_2,y_3))$, $(\max(x_1,x_2,x_3),\max(y_1,y_2,y_3))$. Claim: A triangle's area is at most half of the area of its bounding box. WLOG let $(0,0)$, $(0,q)$, $(p,0)$, $(p,q)$ be the vertices of the bounding box and let $(j,q)$, $(p,k)$, $(0,0)$ be the vertices of the triangle such that $0\le j\le p$ and $0\le k\le q$. Then (since $jk\le pq$) the ratio of the triangle's area to the bounding box's is: $$\frac{\frac{pq-jk}2}{pq}=\frac12-\frac{jk}{2pq}\le\frac12$$(where the area of the triangle was calculated with Shoelace). After $n$ moves, the sum of two adjacent side lengths of the bounding box is at most $n$, since each move increases either dimension of the bounding box by at most one. Then $pq\le\frac{(p+q)^2}4\le\frac{n^2}4$ by AM-GM, so the area of the triangle is at most $\frac{n^2}8$. In order for the triangle to have area $2021$, we must have $n\ge\lceil\sqrt{2021\cdot8}\rceil=128$.
18.08.2022 01:04
(0,0) (64,0) and (0,64) is the easiest construction
18.08.2022 02:39
exactly 2021 not at least 2021
22.08.2022 22:27
04.01.2023 07:26
05.08.2023 18:23
kind of a boring problem, construction is just weird The answer is 128. First note that the area of a triangle is at most half of the area of the box around it (with sides parallel to the axes), because if you place three of the vertices on the corners of the box, moving any of them decreases the area. Now note that in n moves, by AM-GM this box has area at most $(\tfrac{n}{2})^2$. Indeed, this implies that for a triangle with 2021 area, you need a box of area at least 4042, so n is at least $2\sqrt{4042}$, or 128 moves. This intuition can be checked also because 63x64/2 is not enough, while 64x64/2 is more than 2021. As for the construction, WLOG A=(0,0); noticing that 2048 maximal area is not far from 2021, we still want our vertices close to 64,0 and 0,64 to see if it's possible, which can easily be guessed and checked by Shoelace to find B and C have coordinates 10,63 and 64,-1.
11.08.2023 00:07
First, to get from the origin to some point, say $(x,y)$, the minimum number of moves to get to there is $|x|+|y|$. One possible construction is $A=(-1, 54)$, $B=(63,0)$, $C=(0,-10)$, and we can verify the area is $2021$ using the Shoelace Theorem, and the number of moves is \[\lvert-1\rvert+|54|+|63|+|0|+|0|+\lvert-10\rvert=128.\]We claim that $128$ is in fact the minimum possible number of moves, and we'll prove it. First, create a rectangle $R$ with sides parallel to the axes such that it's the smallest rectangle that contains all of the points $A, B, C$, and clearly, one of $A$, $B$, and $C$ must be a vertex of $R$. WLOG, let $C$ be a vertex of $R$, $A$ be on a line parallel to the x-axis, and $B$ be on a line parallel to the y-axis. Then, draw a line $\ell_1$ parallel to the y-axis from $A$, draw a line $\ell_2$ parallel to the x-axis from $B$, and call their intersection $P$. Now, we show it's optimal for us to start at $P$. Let $O$ be our starting point, so that it's a distance $d_1$ from $\ell_1$ and a distance $d_2$ from $\ell_2$. Notice that shifting $O$ onto line $\ell_1$ will decrease the number of moves to get from $O$ to the points $A$ and $B$ by $d_1$, while increasing the number of moves to get from $O$ to $C$ by $d_1$, if $O$ is to the right of $\ell_1$. Otherwise, if $O$ is to the left of $\ell_1$, it will decrease the number of moves to get from $O$ to the points $A$ and $C$ by $d_1$, while increasing the number of moves to get from $O$ to $B$ by $d_1$. Either way, the total decrease of the number of moves is $d_1+d_1-d_1=d_1$, which is good. Similarly, shifting $O$ onto $\ell_2$ decreases the number of total moves needed by $d_2$. So, once we shift $O$ onto both $\ell_1$ and $\ell_2$, we have $O=P$. Then, we see that the total number of moves starting from $P$ is $w+\ell$ where $w$ is the width of $R$, and $\ell$ is the length (or height) of $R$. Now, we show that the maximum area of $ABC$ is half the area of $R$. Let $\ell_1$ intersect the bottom edge of $R$ at $P_1$ and let $\ell_2$ intersect the left edge of $R$ at $P_2$. Then, it's not hard to show that $[AP_1CB]=[ABP_2C]=[R]/2$, so since $[AP_1CB] = [ABC]+[AP_1C]$ and $[ABP_2C]=[ABC]+[BP_2C]$, meaning $[ABC]\leq [R]/2$, as desired. Now, in the case of $A=(-1, 54)$, $B=(63,0)$, $C=(0,-10)$, we have $w=\ell=64$, which gives $[ABC]\leq 64^2/2 = 2048$, which has a possible construction since $2021<2048$. However, if we had $w+\ell < 128$, then the maximum possible value of $[R]/2$ would be $w\ell/2 = 63\cdot 64/2 = 2016 < 2021$, which implies there is no possible construction if $w+\ell < 128$, so we're done.
08.10.2023 22:21
09.10.2023 00:23
oh no i have ptsd1
28.10.2023 02:20
Define the $\textit{bounding box}$ of $ABC$ to be the smallest axis-parallel rectangle that contains $ABC$. Lemma: The area of $ABC$ is at most half the area of the bounding box. Proof: Suppose the bounding box is $AXYZ$. If we fix $C$ and only vary $B$ around the perimeter of the rectangle, the maximal area must be achieved when $B$ coincides with one of the corners of the rectangles. Manually checking each case, we find that the area of $ABC$ is at most half the area of $AXYZ$. $\square$ We proceed by making a claim. Claim: After $n$ moves, the bounding box has area at most $\frac{n^2}{4}$. Proof: The sum of the width and height of the bounding box increases by at most $1$ each move. Hence, letting the length equal $l$ and the width $w$, we obtain $l+w=n$, at which point the result follows by AM-GM. $\square$ The claim implies a bounding box of area $A$ requires at least $\lceil 2 \sqrt{A} \rceil$ moves, implying that $n \ge 128$. Now, we must find a construction for $n=128$. The following construction works: \begin{align*} A &= (-3,-18) \\ B&= (61,0) \\ C &= (0,46) \end{align*} so the answer is $n=128$. $\square$
21.12.2023 02:28
The following two results can be easily proven with some unfortunately bashy case analysis: The area of a triangle is at most half of the area its "bounding rectangle", or the smallest rectangle with axes-parallel sides containing the triangle. The sum of the taxicab distances from a point to the three vertices of a triangle is at least the sum of the dimensions of its "bounding rectangle". We can set this optimal point to be our origin. Note our the area of our bounding rectangle is at least $2 \cdot 2021 = 4042$, from which AM-GM gives us a bound of $\lceil 2\sqrt{2024} \rceil = \boxed{128}$. A construction of this case uses the points $(0,55)$, $(58,0)$, and $(-6,-9)$ with bounding rectangle of dimensions $64 \times 64$. $\blacksquare$
09.01.2024 05:31
When mocking this JMO I thought the maximum area was $133$ This time around I had to look at hints from ARCH :skull: The answer is $128.$ First, define the surrounding rectangle of a triangle as the smallest rectangle with sides parallel to the axes that contains a triangle. It is pretty easy to see (e.g. by an area bash) that the area of the surrounding rectangle is at least twice as large as the area of the triangle. Every move, the sidelength of exactly one side increases by $1$. Thus the area of the surrounding rectangle after every move is at most equal to $\frac{n^2}{2},$ so the area of the triangle is at most equal to $\frac{n^2}{4}.$ This must be greater than or equal to $2021,$ so $n \ge 128.$ A construction for $n = 128$ is $(-2,-27), (0, 62), (37, 0).$
06.05.2024 11:40
Denote the surrounding rectangle of a triangle as the smallest rectangle with sides parallel to the axes that contains the triangle. The area of the triangle is at most half of the area of the surrounding rectangle, because if you place three of the vertices on the corners of the rectangle, moving any of them decreases the area. The sidelength of exactly one side increases by 1 $\Rightarrow$ the area of the surrounding rectangle after all n moves is at most $(\frac{n}{2})^2 = \frac{n^2}{4}$ $\Rightarrow$ the area of the triangle is at most $\frac{n^2}{8}$. But $\frac{n^2}{8} \geq 2021$, so $n \ge 128$. A construction for n = 128 is A = (0,0); B = (1,64); C = (64,54).
04.11.2024 20:31
coolmath2017 wrote: It's not 133 lol I was so excited to see the answer and this the first thing that pops up