Let $n \geq 2$ be an integer. Carl has $n$ books arranged on a bookshelf.
Each book has a height and a width. No two books have the same height, and no two
books have the same width.
Initially, the books are arranged in increasing order of height from left to right. In a
move, Carl picks any two adjacent books where the left book is wider and shorter than
the right book, and swaps their locations. Carl does this repeatedly until no further
moves are possible.
Prove that regardless of how Carl makes his moves, he must stop after a finite number
of moves, and when he does stop, the books are sorted in increasing order of width
from left to right.

Solution:
Without loss of generality, let the books have widths and heights of 1, 2, 3,..., and n. First we will show that Carl can only make finitely many moves.
Note that two books can never be swapped more than once with each other. This is because after a first swap, the wider book will be to the left of the other, so they can never be swapped back. Thus there can be at most ${n\choose 2}$ moves.
Now we will show that the books are in increasing order of width when Carl is done making moves. Assume otherwise for the sake of contradiction. Now let $f(k)$ be the width of the book in the kth spot from the left. Since the books are not in increasing order of width, there must be i such that $f(i)>f(i+1)$, for $1\leq i\leq n-1$.
Claim: The ith book must be shorter than the $(i+1)$th book.
Proof: Assume otherwise for contradiction. Then the ith book must have started to the right of the $(i+1)$th book, since the ith book is taller. However, the ith book is now to the left of the $(i+1)$th book, so they must have been swapped at some point. But since $f(i)>f(i+1)$, the ith book is also wider. But the ith book started to the right, so since it was wider it cannot have been swapped with the $(i+1)$th book, so we arrive at a contradiction. $\blacksquare$
From the claim, the ith book must be shorter than the $(i+1)$th book. But since the ith book is also wider by definition (as $f(i)>f(i+1)$), Carl can swap those two books, so he still has legal moves and we arrive at a contradiction, so we are done. $\blacksquare$
~MortemEtInteritum


Let $\omega$ be the incircle of a fixed equilateral triangle $ABC$. Let $\ell$ be a variable line that is tangent to $\omega$ and meets the interior of segments $BC$ and $CA$ at points $P$ and $Q$, respectively. A point $R$ is chosen such that $PR = PA$ and $QR = QB$. Find all possible locations of the point $R$, over all choices of $\ell$.

Call a point good if it is a possible location for $R$.
Let the incircle of $\triangle ABC$ touch $BC$ at $D$, $AC$ at $E$, and $\ell$ at $T$. Also, let the center of the incircle be $I$. Clearly, a point is good iff it lies on the circle containing $A$ with center $P$ as well as the circle containing $B$ with center $Q$. Call these circles $\omega_1$ and $\omega_2$, respectively.
Note that point $T$ can only lie on minor arc $\overarc{DE}$ (excluding the endpoints).
Claim: A point $X$ is good iff $XT\perp PQ$ and $XT=AD=BE$.
Proof: WLOG, let $X$ be on the same side of $PQ$ as $I$. Then we have that $T, I, X$ are collinear. In particular, we have $\angle XTP=90^{\circ}$. Then $TX=AD$, $PT=PD$, $\angle XTP=\angle ADP$, so that $\triangle ADP\cong \triangle XTP\rightarrow PA=PX$. Similarly, $QB=QX$, so $X$ is good. Then $X'$, the reflection of $X$ across $T$, is also good. But $\omega_1$ and $\omega_2$ have at most two intersections, so $X$ and $X'$ must be these intersections, and since a point is good iff it lies on both circles, we are done.
Now, we know that $R, I, T$ are collinear. Then we have two cases:
Case 1: $R$ and $I$ lie on the same side of $PQ$. Then we have $RI+IT=AI+ID=BI+IE$, so that $RI=AI=BI$. Then we have that $R, A, B$ lie on a circle with center $I$. Note that because $T$ lies on $\overarc{DE}$, $R$ must lie on $\overarc{AB}$. So, one of the solutions is $\boxed{R \text{ in arc } AB\text{ (excluding the endpoints)}}$.
Case 2: $R$ and $I$ lie on opposite sides of $PQ$. Then extend $ID$ out from $D$ to $X$ such that $DX=TR$, and extend $IE$ out from $E$ to $Y$ such that $EY=TR$. Then we see that $IR=IX=IY$, so that $\boxed{R \text{ lies on arc } XY\text{ (excluding the endpoints)}}$.

We claim that $R$ can lie on minor arc $AB$ of the circumcircle of triangle ABC, and it can also lie on the dilation of this arc about the center of triangle $ABC$ with a factor of $-2.$
Let $D, E,$ and $F$ be the feet of the angle bisectors from points $A, B,$ and $C$ respectively. Trivially, $DEF$ is also the medial triangle, orthic triangle, and contact triangle (ABC is equilateral).
Let $I$ be the incenter of ABC. Trivially, $I$ is the centroid, orthocenter, and circumcenter of ABC (ABC is equilateral). Also, $AD=BE=CF=3r$ where $r$ is the radius of circle $\omega$ (This is trivial). $T$ is the point of tangency of $\omega$ and segment $\overline{PQ}$.
R has to lie on the intersection of circles $\omega1$(center P, radius PA) and $\omega2$(center Q, radius QB), and for each choice of P, there exist two locations for R. The location that we claim to lie on the minor arc AB of the circumcircle of ABC shall be denoted M, and the other location shall be denoted N.
Define triangle XYZ to be the homothety of triangle ABC about I with a factor of -2.
Critical claim: M, T, I, and N are collinear.
Proof:
First we shall prove that T lies on MN using phantom points.
Let the intersection of MN and PQ be denoted as K. We shall prove that K and T are the same point.
Let $PT = p$ and $QT = q$. Because of the equal tangent theorem, $PD=PT=p$ and $QE=QT=q$. Hence, by the pythagorean theorem (recall $AD=BE=3r$), $PA^2 = 9r^2 + p^2$ and $QB^2 = 9r^2 + q^2$. Since PN = PA and QN = QB, then $PN^2 = 9r^2 + p^2$ and $QN^2 = 9r^2 + q^2$.
PQ is the perpendicular bisector of MN because MN is the radical axis of $\omega1$ and $\omega2$. Hence, M is the reflection of N across K. Also, NK is the altitude of triangle PNQ, so $PK^2-QK^2 = PN^2-QN^2 = p^2 - q^2$ by using the pythagorean theorem and earlier expressions for $PN^2$ and $QN^2$. However, $PK+QK=PQ=p+q$. Now, we have a system of equations to solve for PK and QK in terms of p and q.
Dividing the first equation by the second (we can do this because p+q is always nonzero), we get $PK-QK=p-q$. Combining this with our PK+QK result, we get $PK = p$ and $QK = q$. However, $PT = p$ and $QT = q$, and only one point can exist on PQ for which this result holds true. As a result, K and T are the same point, otherwise it is a contradiction. Hence M, T, and N are collinear.
$IT \parallel MN$. This is because both MN and IT are perpendicular to PQ (IT is perpendicular to PQ because PQ is a tangent with point of tangency T). However, both lines share point T, as discussed earlier. Hence, IT and MN are the same line, and M, T, I, and N are collinear.
In fact, from our earlier results from the lengths of PN and PT, we can use the pythagorean theorem to get that $NT = 3r$, a result that is always true and independent of P and Q! Also, because M is the reflection of N over K (which is the same as T), $MT = 3r$ also. However, T varies based on P and Q. On the other hand, $IT = r$ and M, T, I and N are collinear. Remembering our earlier definitions of M and N, we get that $MI = 2r$ and $IN = 4r$, with M on the opposite side of N and T from I. Hence, M can be taken to N with a homothety about I with a factor of -2, and T can be taken to M with a homothety about I with a factor of -2. Since, trivially, the circumradius of ABC is 2r (ABC is equilateral), it seems like M can lie anywhere on the circumcircle of ABC.
However, we must take into account the restrictions on P and Q. This limits T to only minor arc DE on the incircle of ABC, hence, because of our earlier homothety statement, M is restricted to minor arc AB on the circumcircle of ABC.  Because of our homothety statement about N, N has to lie on minor arc XY on the circumcircle of triangle XYZ.
Because we defined both M and N to be possible locations for R, $\fbox{R can only lie on minor arc AB of the circumcircle of triangle ABC, and also on minor arc XY of the circumcircle of triangle XYZ}$.
-QED
-Solution by thanosaops


An empty $2020 \times 2020 \times 2020$ cube is given, and a $2020 \times 2020$ grid of square unit cells is drawn  on each of its six faces. A beam is a $1 \times 1 \times 2020$ rectangular prism. Several beams are placed inside the cube subject to the following conditions:
- The two $1 \times 1$ faces of each beam coincide with unit cells lying on opposite faces of the cube. (Hence, there are $3 \cdot {2020}^2$ possible positions for a beam.)
- No two beams have intersecting interiors.
- The interiors of each of the four $1 \times 2020$ faces of each beam touch either a face of the cube or the interior of the face of another beam.
What is the smallest positive number of beams that can be placed to satisfy these conditions?

Solution:
Place the cube in the xyz-coordinate, with the positive x-axis pointing forward, the positive y-axis pointing right, and the positive z-axis pointing up. Let the position of a unit cube be $(x, y, z)$ if it is centered at $(x, y, z)$. Place the $2020 \times 2020 \times 2020$ cube so that the edges are parallel to the axes, and two of its corners are at $(1, 1, 1)$ and $(2020, 2020, 2020)$. Now call a beam z-oriented if its endpoints differ only in z-coordinates, and similarly call it x-oriented or y-oriented if the endpoints differ in x- or y-coordinates, respectively.
We claim that the answer is $\boxed{3030}$. First we will prove 3030 suffices. Place the first beam so its endpoints lie at $(1, 1, 1)$, and $(2020, 1, 1)$. Place the 2nd beam so its endpoints lie at $(1, 1, 2)$ and $(1, 2020, 2)$. Place the 3rd beam so its endpoints lie at $(2, 2, 1)$ and $(2, 2, 2020)$. Now it is clear that the only faces among these three beams that are not touching the faces of the $2020 \times 2020 \times 2020$ cube of the face of another beam are the top face of beam 2, and the front and right faces of beam 3.
Now place the 4th beam from $(1, 3, 3)$ to $(2020, 3, 3)$, 2 units up and right of beam 1. Then place beam 5 from $(3, 1, 4)$ to $(3, 2020, 4)$, 2 units forward and up of beam 2. Place beam 6 from $(4, 4, 1)$ to $(4, 4, 2020)$, 2 unites forward and right of beam 3. Note that these 3 beams will touch the top face of beam 2, and the front and right faces of beam 3. Now the only faces that are not touching another face are the top of beam 5, and the front and right of beam 6.
We can repeat this process 1010 times, placing the beams in groups of 3 so that beam $3n+1$ is 2 units up and right of beam $3n-2$, beam $3n+2$ is 2 units forward and up of beam $3n-1$, and beam $3n+3$ is 2 units forward and right of beam $3n$, for all $1\leq n \leq 1009$. After placing each set of 3 as such, the faces of the previous beams will all satisfy condition 3. And for the last set of 3 (that is, beams 3028, 3029, and 3030), their faces will satisfy condition 3 as well, since the top face of beam 3029 and the front/right faces of beam 3030 will touch the cube (again, note that all other faces will be touching another beam).
Thus, we have shown that 3030 beams suffices, so we will now show that 3030 beams is the minimum. Let there be $A$ x-oriented beams, $B$ y-oriented beams, and $C$ z-oriented beams. Now look each $2020 \times 1 \times 2020$ slice of the cube, parallel to the xz-plane. Note there are 2020 such slices. There are two cases. Either $B=2020^2$, or at least one of A or C is nonzero. In the first case, we clearly have at least $2020^2>3030$ beams as desired. In the second case, we must have at least one beam in each $2020 \times 1 \times 2020$ slice, in order to satisfy condition 3. If there is some slice without a beam, then there will be some x- or z-oriented beam with no beams touching its top or bottom face. Additionally, notice that only x- or z-oriented beams can fit in a $2020 \times 1 \times 2020$ slice, so $A+C\geq 2020$. Similarly, we must have $A=2020^2$, $C=2020^2$, or both $A+B\geq 2020$ and $B+C\geq 2020$. In every case, the number of beams, $A+B+C$, will be at least 3030 as desired.$\blacksquare$
~MortemEtInteritum


Let $ABCD$ be a convex quadrilateral inscribed in a circle and satisfying $DA < AB = BC < CD$. Points $E$ and $F$ are chosen on sides $CD$ and $AB$ such that $BE \perp AC$ and $EF \parallel BC$. Prove that $FB = FD$.

Solution:
Let $G$ be the intersection of $AE$ and $(ABCD)$ and $H$ be the intersection of $DF$ and $(ABCD)$.
Claim: $GH || FE || BC$
By Pascal's on $GDCBAH$, we see that the intersection of $GH$ and $BC$, $E$, and $F$ are collinear. Since $FE || BC$, we know that $HG || BC$ as well. $\blacksquare$
Note that since all cyclic trapezoids are isosceles, $HB = GC$. Since $AB = BC$ and $EB \perp AC$, we know that $EA = EC$, from which we have that $DGCA$ is an isosceles trapezoid and $DA = GC$. It follows that $DA = GC = HB$, so $BHAD$ is an isosceles trapezoid, from which $FB = FD$, as desired. $\blacksquare$

Let $G=\overline{FE}\cap\overline{BC}$, and let $G=\overline{AC}\cap\overline{BE}$. Now let $x=\angle ACE$ and $y=\angle BCA$.
From $BA=BC$ and $\overline{BE}\perp \overline{AC}$, we have $AE=EC$ so $\angle EAC =\angle ECA = x$. From cyclic quadrilateral ABCD, $\angle ABD = \angle ACD = x$. Since $BA=BC$, $\angle BCA = \angle BAC = y$.
Now from cyclic quadrilateral ABC and $\overline{FE}\parallel \overline{BC}$ we have $\angle FAC = \angle BAC = \pi - \angle BCD = \pi - \angle FED$. Thus F, A, D, and E are concyclic, and $\angle DFG = \angle DAE = \angle DAC - \angle EAC = \angle DBC - x$ Let this be statement 1.
Now since $\overline{AH}\perp \overline {BH}$, triangle ABC gives us $\angle BAH + \angle ABG = \frac{\pi}{2}$. Thus $y+x+\angle GBE=\frac{\pi}{2}$, or $\angle GBE = \frac{\pi}{2}-x-y$.
Right triangle BHC gives $\angle HBC = \frac{\pi}{2}-y$, and $\overline{BC}\parallel \overline{FE}$ implies $\angle BEG=\angle HBC = \frac{\pi}{2}-y.$
Now triangle BGE gives $\angle BGE = \pi - \angle BEG - \angle GBE = \pi - (\frac{\pi}{2}-y)-(\frac{\pi}{2}-x-y)=x+2y$. But $\angle FGB = \angle BGE$, so $\angle FGB=x+2y$. Using triangle FGD and statement 1 gives
Thus, $\angle FDB = \angle FBD$, so $\boxed{FB=FD}$ as desired.$\blacksquare$
~MortemEtInteritum

Proving that $FB=FD$ is equivalent to proving that $\angle FBD= \angle FDB$. Note that $\angle FBD=\angle ACD$ because quadrilateral $ABCD$ is cyclic. Also note that $\angle BAC=\angle ACB$ because $AB=BC$. $AE=EC$, which follows from the facts that $BE \perp AC$ and $AB=AC$, implies that $\angle CAE= \angle ACE= \angle ACD= \angle FBD$. Thus, we would like to prove that triangle $FBD$ is similar to triangle $AEC$. In order for this to be true, then $\angle BFD$ must equal $\angle AEC$ which implies that $\angle AFD$ must equal $\angle AED$. In order for this to be true, then quadrilateral $AFED$ must be cyclic. Using the fact that $EF \parallel BC$, we get that $\angle AFE= \angle ABC$, and that $\angle FED= \angle BCE$, and thus we have proved that quadrilateral $AFED$ is cyclic. Therefore, triangle $FDB$ is similar to isosceles triangle $AEC$ from AA and thus $FB=FD$.
-xXINs1c1veXx

BE is perpendicular bisector of AC, so $\angle ACE = \angle EAC$. FE is parallel to BC and ABCD is cyclic, so AFED is also cyclic. $\angle AFD = \angle AED = 2 \angle ACE = 2 \angle FBD$. Hence, $\angle FBD = \angle BDF$, $FD = FB$.
Mathdummy

Let $G$ be on $AB$ such that $GD \perp DB$, and $H = GD \cap EB$. Then $\angle{ADB} = \angle{EDB} = 90^{\circ} - \angle{ABE} \implies \triangle{DAE}$ is the orthic triangle of $\triangle{HGB}$. Thus, $F$ is the midpoint of $GB$ and lies on the $\perp$ bisector of $DB$.

Let $FE$ meet $AC$ at $J$, $BE$ meet $AC$ at $S$, connect $AE, SD$.
Denote that $\angle{BCA}=\alpha; AB=BC, \angle{BAC}=\angle{BCA}=\alpha$, since $EF$ is parallel to $BC$, $\angle{AJF}=\angle{ACB}=\alpha$. $\angle{AJF}$and $\angle{EJS}$ are vertical angle, so they are equal to each other.
$BE\bot{AC}$,$\angle{JES}=90^{\circ}-\alpha$, since $\angle{EFB}=\angle{AJF}+\angle{FAJ}=2\alpha$, we can express $\angle{FBE}=180^{\circ}-2\alpha-(90^{\circ}-\alpha)=90^{\circ}-\alpha= \angle{FEB}$, leads to $FE=FB$
Notice that quadrilateral $AFED$ is a cyclic quadrilateral since $\angle{ADE}+\angle{AFE}=\angle{ADE}+\angle{ABC}=180^{\circ}$.
Assume $\angle{ECA}=\beta$, $\triangle{AES}$ is congruent to $\triangle{CES}$ since $AS=AS,\angle{ASE}=\angle{BSE}, SE=SE(SAS)$, so we can get $\angle{EAS}=\beta$
Let the circumcircle of $AFED$ meets $AC$ at $Q$
Now notice that $\widehat{QE}=\widehat{QE}, \angle{QAE}=\angle{QDE}=\beta$; similarly, $\widehat{FQ}=\widehat{FQ}; \angle{FDQ}=\angle{FAQ}=\alpha$.
$\angle{FDE}=\alpha+\beta; \angle{FED}=\angle{BCD}=\alpha+\beta$, it leads to $FD=FE$.
since $FE=FB;FD=FE, DF=BF$ as desired
~bluesoul


Suppose that $(a_1,b_1),$ $(a_2,b_2),$ $\dots,$ $(a_{100},b_{100})$ are distinct ordered pairs of nonnegative integers. Let $N$ denote the number of pairs of integers $(i,j)$ satisfying $1\leq i<j\leq 100$ and $|a_ib_j-a_jb_i|=1$. Determine the largest possible value of $N$ over all possible choices of the $100$ ordered pairs.

Solution:
Call the pair $(i, j)$ good if $1\leq i < j \leq 100$ and $|a_ib_j-a_jb_i|=1$. Note that we can reorder the pairs $(a_1, b_1), (a_2, b_2), \ldots, (a_{100}, b_{100})$ without changing the number of good pairs. Thus, we can reorder them so that $a_1\leq a_2\leq\ldots\leq a_{100}$. Furthermore, reorder them so that if $a_i=a_j$ for some $i<j$, then $b_i<b_j$.
Now I claim the maximum value of $N$ is $\boxed{197}$. First, we will show $N\leq 197$.
The key claim is that for any fixed integer $m$, $1\leq m \leq 100$, then there are at most 2 values of $i$ with $1\leq i<m$ with the pair $(i, m)$ good. We will prove this with contradiction.
Assume there are 3 integers $i$, $j$, and $k$ that are less than $m$, such that $(i, m)$, $(j, m)$, and $(k, m)$ are all good. Note that $gcd(a_m, b_m)$ divides $a_ib_m-a_mb_i=\pm 1$, so $gcd(a_m, b_m)=1$. From $a_ib_m-a_mb_i=\pm 1$, we have
Similarly,
From $gcd(a_m, b_m)=1$ we have
But since $i$, $j$, and $k$ are less than $m$, from our reordering we have $0\leq a_i<a_m$, $0\leq a_j<a_m$, and $0\leq a_k<a_m$. Thus our congruence gives us that $a_j=a_i$ or $a_j=a_m-a_i$, and similar for $a_k$. Thus at least two of $a_i, a_j, a_k$ are equal. WLOG let them be $a_i$ and $a_j$. Now we have 4 cases.
Case 1: $a_m>2$
We have $a_ib_m-a_mb_i=\pm 1$ and $a_jb_m-a_mb_j=\pm 1$, so since $a_i=a_j$ we can subtract the two equations to get $a_mb_i-a_mb_j$ equals $\pm 2, 0$. But $a_m>2$, so $|a_m(b_i-b_j)|\leq 2$ implies that $b_i=b_j$. But all pairs are distinct and $a_i=a_j$, so this is a contradiction.
Case 2: $a_m=2$
We have 2 subcases.
Subcase 2a: $a_i\equiv a_j\equiv a_k\equiv 1 \mod a_m$
Clearly we must have $a_i=a_j=a_k=1$ in this case, as all 3 variables are less than $a_m=2$. Then $1\cdot b_m-a_mb_i=\pm 1$, $1\cdot b_m-a_mb_j=\pm 1$, and $1\cdot b_m-a_mb_k=\pm 1$. So at least 2 of $b_i$, $b_j$, and $b_k$ must be equal, but this contradicts the fact that all pairs $(a_x, b_x)$ are distinct.
Subcase 2b: $a_i\equiv a_j\equiv a_k\equiv 0 \mod a_m$
$a_i$ must be even in this case, but since $a_m$ is also even then $a_ib_m-a_mb_i$ must be even, which contradicts $|a_ib_m-a_mb_i|=1$.
Case 3: $a_m=1$
We must have $a_i=0,1$, and similarly for $a_j$ and $a_k$. Thus at least 2 of the 3 must be equal. Now we have 2 subcases again.
Subcase 3a: 2 of the 3 are equal to 0
WLOG let $a_i=a_j=0$. Then $a_ib_m-a_mb_i=\pm 1$ and $a_m=1$ so $b_i=\pm 1$. Since $b_i$ is nonnegative, $b_i=1$. Similarly $b_j=1$, but all pairs are distinct so we have a contradiction.
Subcase 3b: 2 of the 3 are equal to 1
WLOG let $a_i=a_j=0$. Then $a_ib_m-a_mb_i=\pm 1$, so $b_m-b_i=\pm 1$. But $i<m$ and $a_i=a_m=1$, so by our ordering of the pairs we have $b_i<b_m$ so $b_m-b_i=1$. But similarly $b_m-b_j=1$, so $b_i=b_j$, which is a contradiction to all pairs being distinct.
Case 4: $a_m=0$
We must have $a_i=0$, since $0\leq a_i\leq a_m=0$. Thus $a_ib_m-a_mb_i=0$, but $|a_ib_m-a_mb_i|=1$, contradiction.$\blacksquare$
Thus our claim is proved. Now for $m=1$, there is clearly no $i$ with $1\leq i < m \leq 100$ and $(i, m)$ good. For $m=2$, there is at most one value of i with $1\leq i < m \leq 100$ and $(i, m)$ good (namely, this is when $i=1$). By our claim, for all $2<m\leq 100$ there are at most 2 values of $i$ with $1\leq i < m \leq 100$ and $(i, m)$ good, so adding these up gives at most $2\cdot 98+1=197$ good pairs. Now we will show that 197 good pairs is achievable.
The sequence $(1,1), (1,2), (2,3),\ldots ,(99,100)$ has 197 good pairs - namely, $(1, n)$ is good for all $1<n\leq 100$, and $(i, i+1)$ is good for all $1<i<100$. This adds up for a total of 197 good pairs, so we are done. $\blacksquare$
~MortemEtInteritum

We claim the answer is $2n-3$ (so $197$), where $100$ is to be replaced with $n$.
The problem essentially counts unordered pairs $(P,Q)$ of lattice points so that $POQ$ has area $\frac{1}{2}$ due to Shoelace ($O$ is the origin).
For a construction, take the points $(0,1),(1,1),(1,2), \dots (1,n-1)$.
We now show by induction that $2n-3$ is the maximum, where $n=2$ obviously holds as a base case.
To reduce to the inductive hypothesis of $n-1$ points from $n$ points, we are allowed to consider the point with the greatest sum of coordinates $R$.
The key claim is that $R$ is part of at most $2$ pairs (triangles) with area $\frac{1}{2}$.
Before we proceed, note that $R$ must have relatively prime coordinates $(m,n)$, or else any triangles found can be reduced down by a greatest common factor along $OR$, impossible since $\frac{1}{2}$ is the minimum positive area.
Call the hypothetical point(s) $X$. With triangle $XOR$ with area $\frac{1}{2}$, we know the length of $OR$, so indeed the locus of $X$ is two lines evenly spaced next to $OR$ each parallel to $OR$ (before we consider the lattice condition).
When we add in the lattice condition, we see that each of these two lines contain at most one valid $X$. This is because if two lattice points with non-negative integers lied on one of these lines, one would have to be a multiple of $m$ more than the other on the $x$-coordinates and a multiple of $n$ more on the $y$-coordinates. This contradicts the coordinate sum maximality of $R$.
Thus, by deleting $R$, we lose at most two pairs $(X,R)$, completing the induction and the problem.


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,$

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

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.

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  implies $f(2n)=1$.
Note that $f(2n^2 -2n+1)=f(n)f(n-1)=1$, so  implies $f(2n-1)=1$. $\square$
Thus, the only solution is $\boxed{f\equiv 1}$.


Rectangles $BCC_1B_2,$ $CAA_1C_2,$ and $ABB_1A_2$ are erected outside an acute triangle $ABC.$ Suppose thatProve that lines $B_1C_2,$ $C_1A_2,$ and $A_1B_2$ are concurrent.

Solution:
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

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.
~Leonard_my_dude


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.)

Prove that

Solution:
I will use the word "center" to refer to the centroid of any equilateral triangle.
Consider the center of each triangle we place and the surrounding area that is "denied" placement for any centers. With a little bit of testing and sliding the equilateral triangle along each side of the center triangle, it is easy to see that this region forms a hexagon of side length $1$ where any other center being in this hexagon would mean that the two equilateral triangles at those centers would overlap.
Let us define a region for each center as its "personal space", where its personal space intersecting with any other center's personal space results in the two equilateral triangles intersecting. Given the above fact, it is easy to see that this personal space region encapsulates a hexagon of sidelength $\frac{1}{2}$ centered at each center by simply scaling the denied region by a factor of $\frac{1}{2}$. The area of each personal space would simply be $6(\frac{\sqrt{3}}{4}(\frac{1}{2})^2)=\frac{3\sqrt{3}}{8}$. Since each personal space cannot intersect, the maximum amount of equilateral triangles would be bounded by $\frac{\text{Area of Big Triangle}}{\text{Area of individual personal space}}=\frac{L^2\frac{\sqrt{3}}{4}}{\frac{3\sqrt{3}}{8}}=\frac{2}{3}L^2$, which completes the problem. (Unrigorous solution that I hope someone else can improve on ~ hyxue)


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.)

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.
~Lcz


For which positive integers $m$ does there exist an infinite arithmetic sequence of integers $a_1,a_2,\cdots$ and an infinite geometric sequence of integers $g_1,g_2,\cdots$ satisfying the following properties?
$\bullet$ $a_n-g_n$ is divisible by $m$ for all integers $n>1$;
$\bullet$ $a_2-a_1$ is not divisible by $m$.

We claim that $m$ satisfies the given conditions if and only if $m$ is a perfect square.
To begin, we let the common difference of $\{a_n\}$ be $d$ and the common ratio of $\{g_n\}$ be $r$. Then, rewriting the conditions modulo $m$ gives:
Condition $(1)$ holds if no consecutive terms in $a_i$ are equivalent modulo $m$, which is the same thing as never having consecutive, equal, terms, in $a_i\pmod{m}$. By Condition $(2)$, this is also the same as never having equal, consecutive, terms in $g_i\pmod{m}$:

Also, Condition $(2)$ holds if
Restating, $(1),(2)\quad \textrm{if} \quad(3),(4)$, and the conditions $g_{l-1}(r-1)\not\equiv 0\pmod{m}$ and $g_{l-1}(r-1)^2\equiv0\pmod{m}$ hold if and only if $m$ is a perfect square.
[will finish that step here]


Let $a$ and $b$ be positive integers. The cells of an $(a + b + 1)\times (a + b + 1)$ grid are colored amber and bronze such that there are at least $a^2+ab-b$ amber cells and at least $b^2+ab-a$ bronze cells. Prove that it is possible to choose $a$ amber cells and $b$ bronze cells such that no two of the $a+b$ chosen cells lie in the same row or column.

Let $n=a+b+1$. There are $n!$ ways to select $n$ cells such that no two are in the same row or column. Each such selection can be specified by $p_i=(p_{i1},p_{i2},\cdots,p_{in})$, a permutation of $1,2,3,\cdots,n$, such that in the $k^\text{th}$ row, the cell in column $p_{ik}$ is selected. Let $A(p_i)$ be the number of amber cells in the selection $p_i$. We just need to prove there exists a $p_i$ such that

Using contradiction, assuming no such $p_i$ exists.
In calculating $\sum A(p_i)$, each amber cell is counted $(n-1)!$ times. We have

WLOG, let $A(p_1)=\max(A(p_i))$. With the contradiction assumption

Similarly, let $A(p_2)=\min(A(p_i))$.
One can always move from $p_1$ to $p_2$ via a path in $p$ space

such that in each step two numbers in the starting permutation are swapped to get the next permutation. For example if

one such path is

Then the value of $A$ along the path changes by at most 2 in each step.
On the other hand since $A(p_i)\neq a, a+1$, there is a gap of at least width 3 in the range of $A$. A path starting above the gap and ending below the gap with max step size two should not exist. Contradiction.
Therefore there must be an $i$ such that either $A(p_i)=a$ or $A(p_i)=a+1$.
(Y)

We claim that it is possible to choose $a$ amber cells such that no two lie in the same row or column.
Number the rows and columns from $1$ to $a+b+1.$ In cell $(x,y),$ write the number $x+y\pmod{a+b+1}.$  Then two same-numbered cells will be on different rows and columns.
There are $a+b+1$ different numbers and $\geq a^2+ab-b = (a-1)(a+b+1)+1$ amber cells. Using Pigeonhole, we have $a+b+1$ holes, and cells in the same hole are in different rows and columns, and $\geq(a-1)(a+b+1)+1$ pigeons, so there exists $a$ amber cells such that no two lie in the same row or column. Similarly, there exists b bronze cells such that no two lie in the same row or column.
Choose those $a$ amber cells and $b$ bronze cells. If no two chosen cells lie in the same row or column then we are done. Otherwise, since there are $a+b+1$ rows and columns, there exists a row and a column with no chosen cell. If their intersection is an amber cell, choose that cells and unchoose an amber cell that is in the same row or column as a bronze cell. If the intersection is a bronze cell, choose that cell and unchoose a chosen bronze cell that is in the same row or column as an amber cell. Repeating this process, we can obtain $a$ amber cells and $b$ bronze cells such that no two lie in the same row or column.

We can prove this statement by using the Hall's marriage theorem. Let us define a bipartite graph $G = (A \cup B, E)$, where $A$ is the set of rows of the grid, $B$ is the set of columns of the grid, and $E$ is the set of edges between $A$ and $B$. We say that a row $a \in A$ is connected to a column $b \in B$ if and only if the cell in row $a$ and column $b$ is colored amber.
Now, we need to show that the conditions of Hall's marriage theorem are satisfied. That is, for any subset $S \subseteq A$, the number of columns connected to $S$ is at least $|S|$. To prove this, let $S$ be any subset of $A$, and let $T$ be the set of columns connected to $S$. Then, the number of amber cells in the rows of $S$ is at least $a|S|$, and the number of amber cells in the rows not in $S$ is at least $b(a+b+1)-a|S|$. Therefore, the total number of amber cells is at least $a|S| + b(a+b+1)-a|S| = ab + b(a+b)$, which is at least $a^2+ab-b$ by assumption. Hence, the number of columns connected to $S$ is at least $b$.
Similarly, we can define a bipartite graph $G' = (A \cup B', E')$, where $B'$ is the set of rows of the grid, and an edge between a row $a$ and a column $b' \in B'$ exists if and only if the cell in row $a$ and column $b'$ is colored bronze. We can show that the conditions of Hall's marriage theorem are also satisfied for $G'$.
Therefore, by Hall's marriage theorem, there exist matchings $M$ and $M'$ in $G$ and $G'$, respectively, such that each row and column in the grid is incident to at most one edge in $M$ or $M'$. Let $X$ be the set of cells in the grid that are covered by $M$, and $Y$ be the set of cells in the grid that are covered by $M'$. Then, $|X| = |Y| = a+b$, since each matching covers a total of $a+b$ cells. Moreover, no two cells in $X$ or $Y$ lie in the same row or column, since each row and column is incident to at most one edge in $M$ or $M'$.
Finally, we can choose $a$ amber cells and $b$ bronze cells from $X$ and $Y$, respectively, such that no two of the chosen cells lie in the same row or column. This is because $|X| = |Y| = a+b$, and there are at least $a^2+ab-b$ amber cells in the grid and at least $b^2+ab-a$ bronze cells in the grid. Therefore, there are at least $a^2+ab-b$ cells colored amber in $X$, and at least $b^2+ab-a$ cells colored bronze in $Y$. This implies that there are at least $a$ amber cells in $X$ and at least $b$ bronze cells in $Y$, so we can choose a subset of $a$ amber cells from $X$ and a subset of $b$ bronze cells from $Y$, such that no two of the chosen cells lie in the same row or column.


Let $b\geq2$ and $w\geq2$ be fixed integers, and $n=b+w$. Given are $2b$ identical black rods and $2w$ identical white rods, each of side length $1$.
We assemble a regular $2n$-gon using these rods so that parallel sides are the same color. Then, a convex $2b$-gon $B$ is formed by translating the black rods, and a convex $2w$-gon $W$ is formed by translating the white rods. An example of one way of doing the assembly when $b=3$ and $w=2$ is shown below, as well as the resulting polygons $B$ and $W$.

Prove that the difference of the areas of $B$ and $W$ depends only on the numbers $b$ and $w$, and not on how the $2n$-gon was assembled.

First notice that the black rods and the white rods form polygons iff in the original $2n$-gon, if a side is a color $x$, then the side that is parallel to that side in the original $2n$-gon is also the color $x$.
We can prove that the difference in areas is only affected by the values of $b$ and $w$ by showing that for any valid arrangement of $2b$ rods and $2w$ rods, we may switch any two adjacent black and white rods(and their "parallel pairs"), and end up with the same area difference.

In the figure above (click to expand), after the switch, we can see that after removing the mutually congruent parts, we are left with two parallelograms from each color. Let $x$, $\alpha{}$, $y$, and $\beta{}$ be defined as shown. Notice that if we angle chase, the sides of the other parallelogram are the same, but if the angles of the original $2n$-gon all have measure $2k$, the angles of the new parallelograms are $\alpha{}+180-2k$ and $\beta{}+180-2k$, as shown. We must prove that the differences between the areas are the same.
Using area formulas, the change in the difference of areas is $x\sin{\alpha{}}-y\sin{\beta{}}+y\sin{(2k-\beta{})}-x\sin{(2k-\alpha{})}$, which is equal to $x(\sin{k}(2\cos^2{k})-2\sin{k}\cos{k}\cos{\alpha{}})-y(\sin{k}(2\cos^2{k}))+y(\sin{k}\cos{k}\cos{\beta{}})$, or $2\cos{k}(x\sin{(\alpha{}-k)}+y\sin{(k-\beta{}}))$. Since $\cos{k}$ is not $0$ because $n\geq{}3$, we are left with proving that $x\sin{(\alpha{}-k)}+y\sin{(k-\beta{}})=0$.
Now we rotate the polygon so that the vertex between the two sides that we switched is at the point $(0,0)$, the angle bisector of that vertex is $y=0$, and the black side is in the positive $y$-direction. Now think of all the sides as vectors, all pointing in the clockwise direction of the $2n$-gon.
Notice the part labeled $a$ in the black polygons. We have that the vector labeled $x$ is really just the sum of all of the vectors in the part labeled $a$ - or all the vectors in the $2n$-gon that are in the positive $y$-direction excluding the one that was interchanged. Also notice that the angle of this vector $x$ has a signed angle of $\alpha{}-k$ with $y=0$ and has length $x$ - meaning that the vertical displacement of the vector $x$ from $y=0$ is equal to $x\sin{(\alpha{}-k)}$! Similarly, we get that the vertical displacement of the vector $y$ is equivalent to $y\sin{(k-\beta{}})$.
Adding these two together, we get that $x\sin{(\alpha{}-k)}+y\sin{(k-\beta{}})$ is simply the vertical displacement of the sum of the vectors $x$ and $y$. Since the sum of the vectors $x$ and $y$ is equivalent to the sum of the vectors in the positive half of the polygon minus the sum of the black vector that would be switched with the white vector(the leftmost vector in the positive half of the polygon) and the rightmost vector in the positive half(which is the parallel pair of the white vector that would be interchanged later), and we know that this sum happens to have a vertical displacement of $0$, along with the fact that the positive half of the polygon summed together also has a vertical displacement of $0$, we get that the total vertical displacement is $0$, meaning that $x\sin{(\alpha{}-k)}+y\sin{(k-\beta{}})=0$, and we are done.
~by @peppapig_

Pick a pair of parallel sides of the regular $2n$-gon and flip their color. Let those two lines be the horizontal. The area of the polygon formed by rods of the original color decreases by a parallelogram with height equal to the sum of the vertical heights of the rods of that color divided by $2$ and base length $1$. Similarly, the area of the polygon formed by rods of the new color increases by the sum of the vertical heights of the rods of the new color divided by $2$. The sum of the heights of all the rod is equal to twice the height of the $2n$-gon, so the difference between the areas of $B$ and $W$ changes by the height of the $2n$-gon, which is fixed when $n$ is fixed.
If we pair two pairs different-colored pairs of parallel sides of the $2n$-gon and flip the colors of both pairs, then $b$ and $w$ and the difference in the areas of $B$ and $W$ will remain unchanged. Thus, the difference in the areas of $B$ and $W$ depends only on $b$ and $w$.


Let $ABCD$ be a rhombus, and let $K$ and $L$ be points such that $K$ lies inside the rhombus, $L$ lies outside the rhombus, and $KA=KB=LC=LD$. Prove that there exist points $X$ and $Y$ on lines $AC$ and $BD$ such that $KXLY$ is also a rhombus.

Solution:
(Image of the solution is here [1])
Let's draw ($\ell$) perpendicular bisector of $\overline{KL}$. Let $X, Y$ be intersections of $\ell$ with $AC$ and $BD$, respectively. $KXLY$ is a kite. Let $O$ mid-point of $\overline{KL}$. Let $M$ mid-point of $\overline{BD}$ (and also $M$ is mid-point of $\overline{AC}$). $X, O, Y$ are on the line $\ell$.
$BK=DL$, $BX=XD$, $XK=XL$ and so $\triangle BXK \cong \triangle DXL$ (side-side-side). By spiral similarity, $\triangle BXD \sim\triangle KXL$. Hence, we get
Similarly, $AK =CL$, $YK = YL$, $YA=YC$ and so $\triangle AKY \cong \triangle CYL$ (side-side-side). From spiral similarity, $\triangle YKL\sim \triangle YAC$. Thus,

If we can show that $a=b$, then the kite $KXLY$ will be a rhombus.
By spiral similarities, $\dfrac{BX}{BD} = \dfrac{XK}{KL}$ and $\dfrac{YA}{AC} = \dfrac{YK}{KL}$. Then, $KL = \dfrac{BD \cdot XK}{BX} = \dfrac{AC \cdot YK}{YA}$.
$\dfrac{XK}{YK} = \dfrac{AC \cdot BX}{AY \cdot BD}$. Then, $\dfrac{YK}{XK} = \dfrac{(BD/2) \cdot AY}{(AC/2) \cdot BX} = \dfrac{\sin b}{\sin a}$. Also, in the right triangles $\triangle KXO$ and $\triangle KYO$,  $\dfrac{YK}{XK} = \dfrac{OK/\cos a}{OK/\cos b} = \dfrac{\cos b}{\cos a}$. Therefore,
$\sin a \cos b = \sin b \cos a \implies \sin a \cos b - \sin b \cos a = 0 \implies \sin(a-b) = 0$ and we get $a=b$.
(Lokman GÖKÇE)


Find all pairs of primes $(p,q)$ for which $p-q$ and $pq-q$ are both perfect squares.

We first consider the case where one of $p,q$ is even. If $p=2$, $p-q=0$ and $pq-q=2$ which doesn't satisfy the problem restraints. If $q=2$, we can set $p-2=x^2$ and $2p-2=y^2$ giving us $p=y^2-x^2=(y+x)(y-x)$. This forces $y-x=1$ so $p=2x+1\rightarrow 2x+1=x^2+2 \rightarrow x=1$ giving us the solution $(p,q)=(3,2)$.
Now assume that $p,q$ are both odd primes. Set $p-q=x^2$ and $pq-q=y^2$ so $(pq-q)-(p-q)=y^2-x^2 \rightarrow p(q-1)$ $=(y+x)(y-x)$. Since $y+x>y-x$, $p | (x+y)$. Note that $q-1$ is an even integer and since $y+x$ and $y-x$ have the same parity, they both must be even. Therefore, $x+y=pk$ for some positive even integer $k$. On the other hand, $p>p-q=x^2 \rightarrow p>x$ and $p^2-p>pq-q=y^2 \rightarrow p>y$. Therefore, $2p>x+y$ so $x+y=p$, giving us a contradiction.
Therefore, the only solution to this problem is $(p,q)=(3,2)$.
~BennettHuang


Find all triples of positive integers $(x,y,z)$ that satisfy the equation

We claim that the only solutions are $(2,3,3)$ and its permutations.
Factoring the above squares and canceling the terms gives you:
$8(xyz)^2 + 2(x^2 +y^2 + z^2) = 4((xy)^2 + (yz)^2 + (zx)^2) + 2024$
Jumping on the coefficients in front of the $x^2$, $y^2$, $z^2$ terms, we factor into:
$(2x^2 - 1)(2y^2 - 1)(2z^2 - 1) = 2023$
Realizing that the only factors of 2023 that could be expressed as $(2x^2 - 1)$ are $1$, $7$, and $17$, we simply find that the only solutions are $(2,3,3)$ by inspection.
-Max
Alternatively, a more obvious factorization is:
$2(x+y+z+2xyz)^2=(2xy+2yz+2zx+1)^2+2023$
$(\sqrt{2}x+\sqrt{2}y+\sqrt{2}z+2\sqrt{2}xyz)^2-(2xy+2yz+2zx+1)^2=2023$
$(2\sqrt{2}xyz+2xy+2yz+2zx+\sqrt{2}x+\sqrt{2}y+\sqrt{2}z+1)(2\sqrt{2}xyz-2xy-2yz-2zx+\sqrt{2}x+\sqrt{2}y+\sqrt{2}z-1)=2023$
$(\sqrt{2}x+1)(\sqrt{2}y+1)(\sqrt{2}z+1)(\sqrt{2}x-1)(\sqrt{2}y-1)(\sqrt{2}z-1)=2023$
$(2x^2-1)(2y^2-1)(2z^2-1)=2023$
Proceed as above. ~eevee9406


(Holden Mui) In an acute triangle $ABC$, let $M$ be the midpoint of $\overline{BC}$. Let $P$ be the foot of the perpendicular from $C$ to $AM$. Suppose that the circumcircle of triangle $ABP$ intersects line $BC$ at two distinct points $B$ and $Q$. Let $N$ be the midpoint of $\overline{AQ}$. Prove that $NB=NC$.

The condition is solved only if $\triangle{NBC}$ is isosceles, which in turn only happens if $\overline{MN}$ is perpendicular to $\overline{BC}$.
Now, draw the altitude from $A$ to $\overline{BC}$, and call that point $X$. Because of the Midline Theorem, the only way that this condition is met is if $\triangle{AXQ} \sim \triangle{NMQ}$, or if $\overline{XM}=\overline{MQ}$.
By $AA$ similarity, $\triangle{AXM} \sim \triangle{CPM}$. Using similarity ratios, we get that $\frac{\overline{AM}}{\overline{XM}}=\frac{\overline{CM}}{\overline{PM}}$. Rearranging, we get that $\overline{AM} \cdot \overline{MP}=\overline{XM} \cdot \overline{MC}$. This implies that $AXPC$ is cyclic.
Now we start using Power of a Point. We get that $\overline{BX} \cdot \overline {XQ}= \overline{AM} \cdot \overline{MP}$, and $\overline{AM} \cdot \overline{MP}=\overline{XM} \cdot \overline{MC}$ from before. This leads us to get that $\overline{BX} \cdot \overline {XQ}=\overline{XM} \cdot \overline{MC}$.
Now we assign variables to the values of the segments. Let $\overline{BX}=a, \overline{XM}=b, \overline{MQ}=c,$ and $\overline{QC}=d$. The equation from above gets us that $(a+b)c=b(c+d)$. As $a+b=c+d$ from the problem statements, this gets us that $b=c$ and $\overline{XC}=\overline{CQ}$, and we are done.
-dragoon and rhydon516 (:

Let $D$ be the foot of the altitude from $A$ onto $BC$. We want to show that $DM=MQ$ for obvious reasons.
Notice that $ADPC$ is cyclic and that $M$ lies on the radical axis of $(ABPQ)$ and $(ADPC)$. By Power of a Point, $(CM)(DM)=(BM)(MQ)$. As $BM=CM$, we have $DM=MQ$, as desired.
- Leo.Euler

We are going to use barycentric coordinates on $\triangle ABC$. Let $A=(1,0,0)$, $B=(0,1,0)$, $C=(0,0,1)$, and $a=BC$, $b=CA$, $c=AB$. We have $M=\left(0,\frac{1}{2},\frac{1}{2}\right)$ and $P=(x:1:1)$ so $\overrightarrow{CP}=\left(\frac{x}{x+2},\frac{1}{x+2},\frac{1}{x+2}-1\right)$ and $\overrightarrow{AM}=\left(-1,\frac{1}{2},\frac{1}{2}\right)$. Since $\overleftrightarrow{CP}\perp\overleftrightarrow{AM}$, it follows that

Solving this gives

so

The equation for $(ABP)$ is

Plugging in $A$ and $B$ gives $u=v=0$. Plugging in $P$ gives

so

Now let $Q=(0,t,1-t)$ where

so $Q=\left(0,\frac{w}{a^2},1-\frac{w}{a^2}\right)$. It follows that $N=\left(\frac{1}{2},\frac{w}{2a^2},1-\frac{w}{2a^2}\right)$. It suffices to prove that $\overleftrightarrow{ON}\perp\overleftrightarrow{BC}$. Setting $\overrightarrow{O}=0$, we get $\overrightarrow{N}=\left(\frac{1}{2},\frac{w}{2a^2},1-\frac{w}{2a^2}\right)$. Furthermore we have $\overrightarrow{CB}=(0,1,-1)$ so it suffices to prove that

which is valid. $\square$
~KevinYang2.71

We employ barycentric coordinates. Set $AMC$ as the reference triangle with $A = (1, 0, 0)$, $M = (0, 1, 0)$, and $C = (0, 0, 1)$. We immediately have,

Since it passes through $A$, for some $v, w$, the equation of circle $(ABP)$ is,

Plugging in $P$,

Plugging in $B$,

In conclusion the circle has formula,

$Q$ is the second intersection of circle $(ABP)$ with $\overline{CM}$. We let $Q = (0, 1 - t, t)$ for some $t \neq -1$. Plugging this in,

We claim that $t = -\frac{S_B}{a^2}$ is the other solution.

Factoring out the $\frac{3a^2 - b^2 + c^2}{2a^2}$, this is clearly true.
We also check that, these are not the same value.

The triangle is acute, so this is impossible.
Since we had a quadratic in $t$ with at most two solutions, the second intersection $Q$ is indeed,

Therefore,
~ Daniel Ge


Consider an $n$-by-$n$ board of unit squares for some odd positive integer $n$. We say that a collection $C$ of identical dominoes is a maximal grid-aligned configuration on the board if $C$ consists of $(n^2-1)/2$ dominoes where each domino covers exactly two neighboring squares and the dominoes don't overlap: $C$ then covers all but one square on the board. We are allowed to slide (but not rotate) a domino on the board to cover the uncovered square, resulting in a new maximal grid-aligned configuration with another square uncovered. Let $k(C)$ be the number of distinct maximal grid-aligned configurations obtainable from $C$ by repeatedly sliding dominoes. Find the maximum value of $k(C)$ as a function of $n$.

Solution:
To start off, we put the initial non-covered square in a corner (marked by the shaded square). Let's consider what happens when our first domino slides over the empty square. We will call such a move where we slide a domino over the uncovered square a "step":

When the vertically-oriented domino above the shaded square moved down to cover the shaded square, it had uncovered a new square two squares above the original one. Next, we consider the second another direction the uncovered square can move to:

In this case, the horizontally-oriented domino besides the shaded square moved to cover the previous shaded square. The new uncovered square, as a result, would be either two squares to the left, or to the right of the previous shaded square.
So, to summarize, during each "move", the uncovered square can move either two steps up, down, left, or right. We can make a path for which the shaded square takes:

We put the original shaded square was in the corner, so, the possible number of squares that cound be uncovered is $\left(\dfrac{n+1}{2}\right)^2 = \frac{n^2+2n+1}{4}$, all of which can be connected by a single path. Let those $\frac{n^2+2n+1}{4}$ belong to a set $S$ of squares.
If the initial uncovered square was not an element of $S$, then it could either be $1$ or $\sqrt{2}$ away from a square in $S$. If the initial square was a distance of $1$ from a element of $S$, then there would be $\left(\dfrac{n+1}{2}\right)\left(\dfrac{n-1}{2}\right)$ possible uncovered squares:

If the initial square was a distance of $\sqrt{2}$ away from a square in $S$, then there would be $\left(\dfrac{n-1}{2}\right)^2$ possible squares that could be uncovered:

So, that means the maximal number of squares that can be uncovered is $\frac{n^2+2n+1}{4}$, thus making a maxmial of $k(C)=\boxed{\frac{n^2+2n+1}{4}}$ achievable configurations from $C$ ($C$'s uncovered square must belong in $S$).
~ sml1809


Two players, $B$ and $R$, play the following game on an infinite grid of unit squares, all initially colored white. The players take turns starting with $B$. On $B$'s turn, $B$ selects one white unit square and colors it blue. On $R$'s turn, $R$ selects two white unit squares and colors them red. The players alternate until $B$ decides to end the game. At this point, $B$ gets a score, given by the number of unit squares in the largest (in terms of area) simple polygon containing only blue unit squares. What is the largest score $B$ can guarantee?
(A simple polygon is a polygon (not necessarily convex) that does not intersect itself and has no holes.)

Solution:
It is clear that $B$ can guarantee a score of $4$ squares. We will show that $R$ has a strategy to limit blue to $4$ squares, thus solving the problem.
Partition the grid into 2x2 squares. Red's strategy is as follows:
- If $B$ plays in a 2x2 square, play the two adjacent squares to $B$'s square that are not in the 2x2 square.
- If one (or both) of these moves are blocked, instead play a square a megaparsec away from the rest of the moves. This move can only benefit you and will not change the outcome of the game.
By induction, it is clear that no two blue squares that are adjacent are not in the same 2x2 square. Thus, we conclude that $R$ has limited blue to a maximum score of $2^2 = 4$, and the proof is complete. $\square$
~mathboy100


A positive integer $a$ is selected, and some positive integers are written on a board. Alice and Bob play the following game. On Alice's turn, she must replace some integer $n$ on the board with $n+a$, and on Bob's turn he must replace some even integer $n$ on the board with $n/2$. Alice goes first and they alternate turns. If on his turn Bob has no valid moves, the game ends.
After analyzing the integers on the board, Bob realizes that, regardless of what moves Alice makes, he will be able to force the game to end eventually. Show that, in fact, for this value of $a$ and these integers on the board, the game is guaranteed to end regardless of Alice's or Bob's moves.

Solution:
We claim that the game will always end if and only if $\nu_{2}(n) < \nu_{2} (a)$ for all $n$ that are in the list of positive integers.
First, we will prove the if direction. Notice that if Alice adds $a$ to $n,$ since we have  for all integers $k>0,$ eventually Bob will decrease $\nu_{2} (n)$ by $1,$ and Alice will not be able to change $\nu_{2} (n),$ and so $\nu_{2}(n)$ will eventually become $0.$
Similarly, all of the other numbers on the list will have the same fate as $n,$ and so, no matter what Bob or Alice do, the game will end.
Now, we complete the only if direction, i.e. if $\nu_{2} (n) \ge \nu_{2} (a),$ where $n$ is one of the numbers in the list, we will prove that Alice can keep the game going forever.
Notice that Bob can only decrease $\nu_{2} (n)$ by $1$ at a time, and so if $\nu_{2} (n) \le \nu_{2} (a),$ we need $\nu_{2} (n) = \nu_{2} (a)$ at some point. But, then, if this is true, take $n = 2^{k}(2m+1),$ and $a = 2^{k}(2\ell+1),$ and notice that
 so
$\nu_{2}(a+n) > \nu_{2} (n).$
Thus, if Bob gets $\nu_{2} (n)$ equal to $\nu_{2} (a),$ Alice can simply add $a$ to $n,$ and then $\nu_{2} (n) > \nu_{2} (a)$ again. Thus, Alice can keep the game going forever, and hence we are done.
~Mr.Sharkman


Isosceles triangle $ABC$, with $AB=AC$, is inscribed in circle $\omega$. Let $D$ be an arbitrary point inside $BC$ such that $BD\neq DC$. Ray $AD$ intersects $\omega$ again at $E$ (other than $A$). Point $F$ (other than $E$) is chosen on $\omega$ such that $\angle DFE = 90^\circ$. Line $FE$ intersects rays $AB$ and $AC$ at points $X$ and $Y$, respectively. Prove that $\angle XDE = \angle EDY$.

Solution:
All angle and side length names are defined as in the figures below. Figure 1 is the diagram of the problem while Figure 2 is the diagram of the Ratio Lemma. Do note that the point names defined in the Ratio Lemma are not necessarily the same defined points on Figure 1.
First, we claim the Ratio Lemma:

We prove this as follows:
By the Law of Sines of $\triangle{ABP},$ we get:

By the Law of Sines of $\triangle{ACP},$ we get:

Dividing each of the corresponding equations, we get:

Noting that $\sin \theta_1= \sin(180^\circ - \theta_1’)=\sin \theta_1’,$ we have:
We transition into our problem.
By Power of a Point on circle $\omega,$ we have:

By power of a point on circle $\omega_1,$ we have:

Using the transitive property, we have:

Thus, by reverse Power of a Point, we have that quadrilaterals $ADKB$ and $ACLD$ are cyclic.
Now, we move to angle chasing.
It is from here in which we focus on quadrilateral $AKEL.$
Let $\angle KDE=\beta$ and $\angle EDL=\gamma.$ Now realize that all we want to show, as given by the problem statement, is $\beta=\gamma.$
Thus, $\angle{KED}=90^\circ-\beta, \angle{DEL}=90^\circ-\gamma.$
We also have:
\begin{align*}
\angle LAD&=180^\circ-(\angle ADL+\alpha)\\
&=180^\circ-((180^\circ-\gamma)+\alpha))\\
&=\gamma-\alpha.
\end{align*}
Similarly, $\angle{KAD}=\beta-\alpha.$
Calling back to what we want to show - if we want to show that $\beta=\gamma,$ it suffices to show that $\angle KAD=\angle LAD$ and $\angle KED=\angle LED.$ But this is equivalent to showing $\triangle{AKE}\sim\triangle{ALE}.$
However, applying our Ratio Lemma to $\triangle{AKE},$ we have:

Applying our Ratio Lemma to $\triangle{ALE},$ we have:

From the transitive property, we have:

Now, realize that we already have a shared side $AE$ and equivalent angles $\angle{ALE}=90^\circ+\alpha=\angle{AKE}.$ Thus, we establish a stronger bound between these two triangles - a congruence.
Thus, these two triangles are similar, and our proof is complete.
mathboy282

(cred. to v_Enhance diagram)


Let $ABCD$ be a cyclic quadrilateral with $AB = 7$ and $CD = 8$. Points $P$ and $Q$ are selected on segment $AB$ such that $AP = BQ = 3$. Points $R$ and $S$ are selected on segment $CD$ such that $CR = DS = 2$. Prove that $PQRS$ is a cyclic quadrilateral.

First, let $E$ and $F$ be the midpoints of $AB$ and $CD$, respectively. It is clear that $AE=BE=3.5$, $PE=QE=0.5$, $DF=CF=4$, and $SF=RF=2$. Also, let $O$ be the circumcenter of $ABCD$.

By properties of cyclic quadrilaterals, we know that the circumcenter of a cyclic quadrilateral is the intersection of its sides' perpendicular bisectors. This implies that $OE\perp AB$ and $OF\perp CD$. Since $E$ and $F$ are also bisectors of $PQ$ and $RS$, respectively, if $PQRS$ is indeed a cyclic quadrilateral, then its circumcenter is also at $O$. Thus, it suffices to show that $OP=OQ=OR=OS$.
Notice that $PE=QE$, $EO=EO$, and $\angle QEO=\angle PEO=90^\circ$. By SAS congruency, $\Delta QOE\cong\Delta POE\implies QO=PO$. Similarly, we find that $\Delta SOF\cong\Delta ROF$ and $OS=OR$. We now need only to show that these two pairs are equal to each other.
Draw the segments connecting $O$ to $B$, $Q$, $C$, and $R$.

Also, let $r$ be the circumradius of $ABCD$. This means that $AO=BO=CO=DO=r$. Recall that $\angle BEO=90^\circ$ and $\angle CFO=90^\circ$. Notice the several right triangles in our figure.
Let us apply Pythagorean Theorem on $\Delta BEO$. We can see that $EO^2+EB^2=BO^2\implies EO^2+3.5^2=r^2\implies EO=\sqrt{r^2-12.25}.$
Let us again apply Pythagorean Theorem on $\Delta QEO$. We can see that $QE^2+EO^2=QO^2\implies0.5^2+r^2-12.25=QO^2\implies QO=\sqrt{r^2-12}.$
Let us apply Pythagorean Theorem on $\Delta CFO$. We get $CF^2+OF^2=OC^2\implies4^2+OF^2=r^2\implies OF=\sqrt{r^2-16}$.
We finally apply Pythagorean Theorem on $\Delta RFO$. This becomes $OF^2+FR^2=OR^2\implies r^2-16+2^2=OR^2\implies OR=\sqrt{r^2-12}$.
This is the same expression as we got for $QO$. Thus, $OQ=OR$, and recalling that $OQ=OP$ and $OR=OS$, we have shown that $OP=OQ=OR=OS$. We are done. QED
~Technodoggo

We can consider two cases: $AB \parallel CD$ or $AB \nparallel CD.$ The first case is trivial, as $PQ \parallel RS$ and we are done due to symmetry. For the second case, WLOG, assume that $A$ and $C$ are located on $XB$ and $XD$ respectively. Extend $AB$ and $CD$ to a point $X,$ and by Power of a Point, we have  which may be written as  or  We can translate this to  so  and therefore by the Converse of Power of a Point $PQRS$ is cyclic, and we are done.
- spectraldragon8


Find all functions $f:\mathbb{R}\rightarrow\mathbb{R}$ that satisfy

for all $x,y\in\mathbb{R}$.

I will denote the original equation $f(x^2-y)+2yf(x)=f(f(x))+f(y)$ as OE.
I claim that the only solutions are $f(x) = -x^2, f(x) = 0,$ and $f(x) = x^2.$
Lemma 1: $f(0) = 0.$
Proof of Lemma 1:
We prove this by contradiction. Assume $f(0) = k \neq 0.$
By letting $x=y=0$ in the OE, we have
If we let $x = 0$ and $y = k^2$ in the OE, we have
 and if we let $x = k$ and $y = k^2$ in the OE, we get

However, upon substituting $x = k$ and $y = -k^2$ in the OE, this implies

This means $k = 0,$ but we assumed $k \neq 0,$ contradiction, which proves the Lemma.
Substitute $y = 0$ in the OE to obtain

and let $y = x^2$ in the OE to get
Thus we can write $f(x) = kx^2$ for some $k.$ By $f(x^2) = f^2(x),$ we have  so $k = -1, 0, 1,$ yielding the solutions
- spectraldragon8