\documentclass[11pt]{scrartcl}
\usepackage[sexy]{evan}
\ihead{\footnotesize\textbf{\thetitle}}
\ohead{\footnotesize\theauthor}
\begin{document}
\title{USA TST 2024 Solutions}
\subtitle{United States of America --- Team Selection Test}
\author{Andrew Gu, Evan Chen, Gopal Goel, Luke Robitaille}
\date{65\ts{th} IMO 2024 United Kingdom and 13\ts{th} EGMO 2024 Georgia}
\maketitle
\tableofcontents
\newpage
\addtocounter{section}{-1}
\section{Problems}
\begin{enumerate}[\bfseries 1.]
\item %% Problem 1
Find the smallest constant $C > 1$ such that the following statement holds:
for every integer $n \ge 2$ and sequence of non-integer
positive real numbers $a_1$, $a_2$, \dots, $a_n$ satisfying
\[ \frac{1}{a_1} + \frac{1}{a_2} + \dots + \frac{1}{a_n} = 1, \]
it's possible to choose positive integers $b_i$ such that
\begin{enumerate}
\ii[(i)] for each $i=1,2,\dots,n$,
either $b_i = \left\lfloor a_i \right\rfloor$ or $b_i = \left\lfloor a_i \right\rfloor + 1$; and
\ii[(ii)] we have
\[ 1 < \frac1{b_1} + \frac1{b_2} + \dots + \frac{1}{b_n} \le C. \]
\end{enumerate}
\item %% Problem 2
Let $ABC$ be a triangle with incenter $I$.
Let segment $AI$ intersect the incircle of triangle $ABC$ at point $D$.
Suppose that line $BD$ is perpendicular to line $AC$.
Let $P$ be a point such that $\angle BPA = \angle PAI = 90^\circ$.
Point $Q$ lies on segment $BD$ such that the
circumcircle of triangle $ABQ$ is tangent to line $BI$.
Point $X$ lies on line $PQ$ such that $\angle IAX = \angle XAC$.
Prove that $\angle AXP = 45^\circ$.
\item %% Problem 3
Let $n > k \ge 1$ be integers and let $p$ be a prime dividing $\tbinom nk$.
Prove that the $k$-element subsets of $\{1, \dots, n\}$ can be
split into $p$ classes of equal size, such that
any two subsets with the same sum of elements belong to the same class.
\item %% Problem 4
Find all integers $n \ge 2$ for which there exists
a sequence of $2n$ pairwise distinct points $(P_1, \dots, P_n, Q_1, \dots, Q_n)$
in the plane satisfying the following four conditions:
\begin{enumerate}[label={(\roman*)}]
\ii no three of the $2n$ points are collinear;
\ii $P_iP_{i+1} \ge 1$ for all $i=1,2,\dots,n$, where $P_{n+1} = P_1$;
\ii $Q_iQ_{i+1} \ge 1$ for all $i=1,2,\dots,n$, where $Q_{n+1} = Q_1$; and
\ii $P_i Q_j \leq 1$ for all $i=1,2,\dots,n$ and $j=1,2,\dots,n$.
\end{enumerate}
\item %% Problem 5
Suppose $a_1 < a_2 < \dots < a_{2024}$ is an arithmetic sequence of positive integers,
and $b_1 < b_2 < \dots < b_{2024}$ is a geometric sequence of positive integers.
Find the maximum possible number of integers that could appear in both sequences,
over all possible choices of the two sequences.
\item %% Problem 6
Solve over $\RR$ the functional equation
\[ f(xf(y)) + f(y)=f(x+y)+f(xy). \]
\end{enumerate}
\pagebreak
\section{Solutions to Day 1}
\subsection{USA TST 2024/1, proposed by Merlijn Staps}
\textsl{Available online at \url{https://aops.com/community/p29409075}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Find the smallest constant $C > 1$ such that the following statement holds:
for every integer $n \ge 2$ and sequence of non-integer
positive real numbers $a_1$, $a_2$, \dots, $a_n$ satisfying
\[ \frac{1}{a_1} + \frac{1}{a_2} + \dots + \frac{1}{a_n} = 1, \]
it's possible to choose positive integers $b_i$ such that
\begin{enumerate}
\ii[(i)] for each $i=1,2,\dots,n$,
either $b_i = \left\lfloor a_i \right\rfloor$ or $b_i = \left\lfloor a_i \right\rfloor + 1$; and
\ii[(ii)] we have
\[ 1 < \frac1{b_1} + \frac1{b_2} + \dots + \frac{1}{b_n} \le C. \]
\end{enumerate}
\end{mdframed}
\paragraph{Answer.} The answer is $C=\frac{3}{2}$.
\paragraph{Lower bound.}
Note that if $a_1 = \frac{4n-3}{2n-1}$ and $a_i = \frac{4n-3}{2}$ for $i > 1$,
then we must have $b_1 \in \{1,2\}$ and $b_i \in \{2n-2,2n-1\}$ for $i > 1$. If
we take $b_1 = 2$ then we obtain
\[
\frac{1}{b_1} + \frac{1}{b_2} + \dots + \frac{1}{b_n} \le \frac{1}{2} + (n-1)
\cdot \frac{1}{2n-2} = 1,
\]
whereas if we take $b_1 = 1$ then we obtain
\[
\frac{1}{b_1} + \frac{1}{b_2} + \dots + \frac{1}{b_n} \ge 1 + (n-1) \cdot
\frac{1}{2n-1} = \frac{3n-2}{2n-1}.
\]
This shows that $C \ge \frac{3n-2}{2n-1}$, and as $n\to \infty$ this shows that
$C\geq \frac{3}{2}$.
\paragraph{Upper bound.}
For $0\leq k\leq n$, define
\[
c_i = \sum_{i=1}^{k}\frac{1}{\lfloor a_i\rfloor}
+ \sum_{i=k+1}^{n}\frac{1}{\lfloor a_i\rfloor+1}.
\]
Note that $c_0 < c_1 < \dots < c_n$ and
\[c_0 < \frac{1}{a_1} + \frac{1}{a_2} + \dots + \frac{1}{a_n} = 1 < c_n.\]
This means there exists a unique value of $k$ for which $c_{k-1} < 1 < c_{k}$. For
this $k$ we have
\[
1 < c_{k} = c_{k-1} + \frac{1}{(\lfloor a_k\rfloor)(\lfloor a_k\rfloor+1)} < 1 +
\frac{1}{1\cdot 2} = \frac{3}{2}.
\]
Therefore we may choose $b_i = \lfloor a_i\rfloor$ for $i\leq k$ and $b_i =
\lfloor a_i\rfloor+1$ for $i > k$.
\begin{remark*}
The solution can be phrased in the following ``motion-based'' way.
Imagine starting with all floors (corresponding to $c_0$),
then changing each floor to a ceiling one by one
until after $n$ steps every floor is a ceiling (arriving at $c_n$).
As we saw, $c_0 < 1 < c_n$, but $c_0 < \dots < c_n$.
Moreover, each discrete step increases the sum by at most
\[ \frac{1}{\left\lfloor a_i \right\rfloor}
- \frac{1}{\left\lfloor a_i \right\rfloor + 1} \leq \frac 12 \]
and so the changing sum must be in the interval $[1, 3/2]$ at some point.
\end{remark*}
\paragraph{Upper bound (alternate).}
First suppose $a_i < 2$ for some $i$. Assume without loss of generality $i=1$
here. Let $b_1=1$ and $b_i=\lfloor a_i\rfloor+1$ for all other $i$. Then
\begin{align*}
1 &< \frac{1}{b_1} + \dots + \frac{1}{b_n} = 1 + \frac{1}{\lfloor a_2\rfloor +
1} + \dotsb + \frac{1}{\lfloor a_n\rfloor + 1} \\
&< \left(\frac{1}{2} +
\frac{1}{a_1}\right) + \frac{1}{a_2} + \dotsb + \frac{1}{a_n} = \frac{3}{2}.
\end{align*}
Now suppose $a_i > 2$ always. Then $\frac{a_i}{\lfloor a_i\rfloor} <
\frac{3}{2}$, so
\[
1 = \frac{1}{a_1} + \dotsb + \frac{1}{a_n} < \frac{1}{\lfloor a_1\rfloor} +
\dots + \frac{1}{\lfloor a_n\rfloor} < \frac{3}{2}\left(\frac{1}{a_1} + \dotsb
+ \frac{1}{a_n}\right) = \frac{3}{2}.
\]
Therefore we may let $b_i=\lfloor a_i\rfloor$ for all $i$.
\begin{remark*}
The original proposal asked to find the optimal $C$ for a fixed $n$. The
answer is $\frac{3n-2}{2n-1}$, i.e. the lower bound construction in the
solution is optimal.
\end{remark*}
\pagebreak
\subsection{USA TST 2024/2, proposed by Luke Robitaille}
\textsl{Available online at \url{https://aops.com/community/p29409083}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $ABC$ be a triangle with incenter $I$.
Let segment $AI$ intersect the incircle of triangle $ABC$ at point $D$.
Suppose that line $BD$ is perpendicular to line $AC$.
Let $P$ be a point such that $\angle BPA = \angle PAI = 90^\circ$.
Point $Q$ lies on segment $BD$ such that the
circumcircle of triangle $ABQ$ is tangent to line $BI$.
Point $X$ lies on line $PQ$ such that $\angle IAX = \angle XAC$.
Prove that $\angle AXP = 45^\circ$.
\end{mdframed}
We show several approaches.
\paragraph{First solution, by author.}
\begin{center}
\begin{asy}
unitsize(1.0inches);
real eps = 1.15104332322704; /* trololol */
real v = 52 + eps;
real w = 150 + eps;
pair V = dir(v);
pair W = dir(w);
pair A = 2*V*W/(V+W);
pair D = dir((v+w)/2);
pair B = (D/(V*V)-1/D+2/W)/(1/(V*V)+1/(W*W));
pair I = 0;
pair U = 2*foot(W,I,B)-W;
pair C = 2*U*V/(U+V);
pair P = foot(B,A,A+A*dir(90));
pair Q = B + dir(D-B)*(P-B)/dir(P-B);
pair X = extension(P,Q,A,incenter(A,I,V));
draw(circumcircle(V,-V,W));
draw(A--B--C--cycle);
draw(A--I);
draw(I--U,linewidth(0.3));
draw(B--P--A);
draw(B--Q--D);
draw(B--I,linewidth(0.3));
draw(P--Q--X);
draw(A--X,linewidth(0.3));
pair O = circumcenter(A,Q,B);
pair AA = (A-O)*dir(20)+O;
pair BB = (B-O)*dir(-20)+O;
draw(arc(O,BB,AA),linewidth(0.4)+dashed);
dot("$A$",A,dir(45));
dot("$D$",D,dir(-30));
dot("$B$",B,dir(260));
dot("$I$",I,dir(0));
dot("$E$",U,dir(U));
dot("$C$",C,dir(C));
dot("$P$",P,dir(P));
dot("$Q$",Q,dir(-55));
dot("$X$",X,dir(270));
\end{asy}
\end{center}
\begin{claim*}
We have $BP=BQ$.
\end{claim*}
\begin{proof}
For readability, we split the proof into three unconditional parts.
\begin{itemize}
\ii We translate the condition $\ol{BD} \perp \ol{AC}$.
It gives $\angle DBA = 90\dg - A$, so that
\begin{align*}
\angle DBI &= \left| \frac B2 - (90\dg - A) \right| = \frac{|A-C|}{2} \\
\angle BDI &= \angle DBA + \angle BAD = (90\dg-A) + \frac A2 = 90\dg - \frac A2.
\end{align*}
Hence, letting $r$ denote the inradius, we can translate $\ol{BD} \perp \ol{AC}$
into the following trig condition:
\[ \sin \frac B2 = \frac{r}{BI} = \frac{DI}{BI}
= \frac{\sin \angle DBI}{\sin \angle BDI}
= \frac{\sin\frac{|A-C|}{2}}{\sin\left(90\dg-\frac A2\right)}. \]
\ii The length of $BP$ is given from right triangle $APB$ as
\[ BP = BA \cdot \sin \angle PAB = BA \cdot \sin\left( 90\dg-\frac A2 \right). \]
\ii The length of $BQ$ is given from the law of sines on triangle $ABQ$.
The tangency gives $\angle BAQ = \angle DBI$ and
$\angle BQA = 180\dg - \angle ABI = 180\dg - \angle IBE$ and thus
\[ BQ = BA \cdot \frac{\sin \angle BAQ}{\sin \angle AQB}
= BA \cdot \frac{\sin \angle DBI}{\sin \angle ABI}
= BA \cdot \frac{\sin \frac{|A-C|}{2}}{\sin \frac B2}. \]
\end{itemize}
The first bullet implies the expressions in the second and third bullet
for $BP$ and $BQ$ are equal, as needed.
\end{proof}
\begin{remark*}
In the above proof, one dos not actually need to compute $\angle DBI = \frac{|A-C|}{2}$.
The proof works equally leaving that expression intact as $\sin \angle DBI$
in place of $\sin \frac{|A-C|}{2}$.
\end{remark*}
Now we can finish by angle chasing. We have
\[ \angle PBQ = \angle PBA + \angle ABD = \frac{A}{2} + 90\dg - A =
90\dg - \frac{A}{2}.
\]
Then
\[
\angle BPQ = \frac{180\dg - \angle PBQ}{2} = 45\dg + \frac{A}{4},
\]
so $\angle APQ = 90\dg - \angle BPQ = 45\dg - \frac{A}{4}$.
Also, if we let $J$ be the incenter of $IAC$,
then $\angle PAJ = 90 \dg + \frac{A}{4}$, and clearly $X$ lies on line $AJ$.
Then $\angle APQ + \angle PAJ = 135 \dg < 180 \dg$,
so $X$ lies on the same side of $AP$ as $Q$ and $J$ (by the parallel postulate).
Therefore $\angle AXP = 180 \dg - 135 \dg = 45 \dg$, as desired.
\begin{remark*}
The problem was basically written backwards by starting from the $BD \perp AC$
condition, turning that into trig, and then contriving $P$ and $Q$ so that the
$BD \perp AC$ condition implied $BP=BQ$.
\end{remark*}
\paragraph{Second solution, by Jeffrey Kwan.}
We prove the following restatement:
\begin{quote}
Consider isosceles triangle $AEF$ with $AE = AF$ and incenter $D$.
Let $B$ be the point on ray $AE$ such that $BD\perp AF$,
and let $P$ be the projection of $B$ onto the line through $A$ parallel to $EF$.
Let $I$ be the point diametrically opposite $A$ in the circumcircle of $AEF$,
and let $Q$ be the point on line $BD$ such that $BI$ is tangent to the circumcircle of
$AQB$. Then $\angle APQ = 45^\circ - \angle A / 4$.
\end{quote}
First note that $\angle DFE = 45^\circ - \angle A / 4$, so it suffices to show that $\ol{PQ}\parallel \ol{DF}$.
Let $U = \ol{BD} \cap \ol{EF}$, and let $V = BI\cap (AEF)$. Observe that:
\begin{itemize}
\item $P$ and $V$ both lie on the circle with diameter $AB$, so $\angle BVP = \angle PAB = 90^\circ - \angle A / 2$.
\item We have $\angle EVB = \angle EVI = \angle A / 2 = \angle DUF = \angle BUE$.
Hence $BEUV$ is cyclic.
\end{itemize}
Now $\angle BVU = \angle AEU = 90^\circ - \angle A / 2 = \angle BVP$, so $\ol{PUV}$ are collinear.
\begin{center}
\begin{asy}
unitsize(0.9inches);
size(600);
pair A, E, F, D, B, I, P, Q, U, V;
A = dir(90);
E = dir(191);
F = dir(349);
D = incenter(A, E, F);
I = dir(270);
B = extension(A, E, D, foot(D, A, F));
P = foot(B, A, A + E - F);
Q = extension(B, D, P, P + F - D);
U = extension(B, D, E, F);
V = extension(B, I, P, U);
draw(A--E--F--cycle, orange);
draw(circumcircle(A, E, F), red);
draw(incircle(A, E, F), heavyred);
draw(E--B--foot(D, A, F), orange);
draw(A--P--B, heavycyan);
draw(A--Q--B^^P--Q, lightblue);
draw(P--V, dotted+magenta);
draw(B--V, dotted+magenta);
draw(circumcircle(A, P, B), magenta);
draw(circumcircle(A, P, Q), purple + dashed);
dot("$A$", A, dir(60));
dot("$B$", B, dir(B));
dot("$E$", E, dir(160));
dot("$F$", F, dir(F));
dot("$D$", D, dir(330));
dot("$I$", I, dir(270));
dot("$P$", P, dir(135));
dot("$Q$", Q, dir(300));
dot("$U$", U, dir(270));
dot("$V$", V, dir(300));
dot(foot(D, A, F));
\end{asy}
\end{center}
From the tangency condition, we have that $\angle AQB = 180^\circ - \angle ABI$, which implies that
\[\angle AQU + \angle APU = \angle AQB + \angle APV = (180^\circ - \angle ABI) + \angle ABI = 180^\circ,\]
and so $APUQ$ is cyclic. Finally, note that $D$ is the orthocenter of $\triangle AUF$, which implies that
\[\angle APQ = \angle AUQ = \angle AUD = \angle AFD = \angle DFE.\]
This forces $\ol{PQ}\parallel \ol{DF}$, as desired.
\paragraph{Third solution by Pitchayut Saengrungkongka and Maxim Li.}
We provide yet another proof that $BP = BQ$.
\begin{center}
\begin{asy}
size(8cm);
import geometry;
real eps = 1.15104332322704; /* trololol */
real v = 52 + eps;
real v = 52 + eps;
real w = 150 + eps;
real w = 150 + eps;
pair V = dir(v);
pair W = dir(w);
pair A = 2*V*W/(V+W);
pair D = dir((v+w)/2);
pair B = (D/(V*V)-1/D+2/W)/(1/(V*V)+1/(W*W));
pair I = 0;
pair U = 2*foot(W,I,B)-W;
pair C = 2*U*V/(U+V);
pair P = foot(B,A,A+A*dir(90));
pair Q = B + dir(D-B)*(P-B)/dir(P-B);
pair X = extension(P,Q,A,incenter(A,I,V));
pair T = extension(U,W,D,D+A-P);
fill(P--A--Q--B--cycle, red+opacity(0.2));
fill(T--D--I--W--cycle, blue+opacity(0.2));
draw(A--B--C--cycle, linewidth(1.0));
draw(incircle(A,B,C), linewidth(0.8));
draw(A--I, linewidth(0.7));
draw(P--A--Q--B--cycle, red+linewidth(0.8));
draw(T--D--I--W--cycle, blue+linewidth(0.8));
draw(P--X, linewidth(0.7));
draw(T--U, blue+linewidth(0.8));
draw(Q--D, red+linewidth(0.7));
dot("$V$", V, dir(53));
dot("$W$", W, dir(180));
dot("$A$", A, dir(77));
dot("$D$", D, dir(54));
dot("$B$", B, dir(-130));
dot("$I$", I, dir(-54));
dot("$U$", U, dir(-90));
dot("$C$", C, dir(-19));
dot("$P$", P, dir(146));
dot("$Q$", Q, dir(-70));
dot("$X$", X, dir(-12));
dot("$T$", T, dir(-141));
\end{asy}
\end{center}
Let the incircle be $\omega$ and touch $BC$ and $AB$ at point $U$ and $W$.
Let the tangent to $\omega$ at $D$ meet $UW$ at $T$.
Notice that $T$ is the pole of $BD$ with respect to $\omega$, so $IT\perp BD$.
Now, we make the following critical claim, which in particular implies $BP = BQ$.
\begin{claim*}
Quadrilaterals $DIWT$ and $PBQA$ are inversely similar.
\end{claim*}
\begin{proof}
This follows from four angle relations.
\begin{itemize}
\item $\dang IDT = \dang BPA = 90^\circ$.
\item $\dang TIW = \dang ABQ$.
\item $\dang DIT = \dang IAC = \dang BAI = \dang ABP$.
\item $\dang ITW = \dang QBI = \dang QAB$. \qedhere
\end{itemize}
\end{proof}
With $BP = BQ$ obtained,
one finishes with the same angle chasing as in the first solution.
\pagebreak
\subsection{USA TST 2024/3, proposed by Ankan Bhattacharya}
\textsl{Available online at \url{https://aops.com/community/p29409068}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $n > k \ge 1$ be integers and let $p$ be a prime dividing $\tbinom nk$.
Prove that the $k$-element subsets of $\{1, \dots, n\}$ can be
split into $p$ classes of equal size, such that
any two subsets with the same sum of elements belong to the same class.
\end{mdframed}
Let $\sigma(S)$ denote the sum of the elements of $S$, so that
\[ P(x) \coloneqq \sum_{\substack{S\subseteq \{1, \dots, n\} \\ |S|=k}} x^{\sigma(S)} \]
is the generating function for the sums of $k$-element subsets of $\{1, \dots, n\}$.
By Legendre's formula,
\[ \nu_p\left(\binom{n}{k}\right) = \sum_{r=1}^{\infty}
\left(\left\lfloor\frac{n}{p^r}\right\rfloor - \left\lfloor\frac{k}{p^r}\right\rfloor
- \left\lfloor\frac{n-k}{p^r}\right\rfloor\right) \]
so there exists a positive integer $r$ with
\[ \left\lfloor\frac{n}{p^r}\right\rfloor - \left\lfloor\frac{k}{p^r}\right\rfloor
- \left\lfloor\frac{n-k}{p^r}\right\rfloor > 0. \]
The main claim is the following:
\begin{claim*}
$P(x)$ is divisible by
\[
\Phi_{p^r}(x) = x^{(p-1)p^{r-1}} + \dots + x^{p^{r-1}} + 1.
\]
\end{claim*}
Before proving this claim, we will show how it solves the problem. It implies
that there exists a polynomial $Q$ with integer coefficients satisfying
\begin{align*}
P(x) & = \Phi_{p^r}(x) Q(x)\\
& = (x^{(p-1)p^{r-1}} + \dots + x^{p^{r-1}} + 1) Q(x).
\end{align*}
Let $c_0,\ c_1,\ \dots$ denote the coefficients of $P$, and define
\[ s_i = \sum_{j \equiv i \pmod{p^r}} c_j. \]
Then it's easy to see that
\begin{alignat*}{4}
& s_0 && = s_{p^{r-1}} && = \cdots && = s_{(p-1)p^{r-1}}\\
& s_1 && = s_{p^{r-1}+1} && = \cdots && = s_{(p-1)p^{r-1}+1}\\
& && && \vdots &&\\
& s_{p^{r-1}-1} && = s_{2p^{r-1}-1} && = \cdots && = s_{p^r-1}.
\end{alignat*}
This means we can construct the $p$ classes by placing a set with sum $z$ in
class $\left\lfloor\frac{z\mod{p^r}}{p^{r-1}}\right\rfloor$.
Now we present two ways to prove the claim.
\paragraph{First proof of claim.}
There's a natural bijection between $k$-element subsets of $\{1, \dots, n\}$
and binary strings consisting of $k$ zeroes and $\ell$ ones:
the set $\{a_1, \dots, a_k\}$ corresponds to the string
which has zeroes at positions $a_1,\ \dots,\ a_k$.
Moreover, the inversion count of this string is simply $(a_1 + \dots + a_k) - \tfrac12k(k+1)$,
so we only deal with these inversion counts (equivalently, we are factoring
$x^{\frac{k(k+1)}{2}}$ out of $P$).
Recall that the generating function for these inversion counts is given by the
$q$-binomial coefficient
\[
P(x) = \frac{(x-1) \cdots (x^{k+\ell}-1)}
{\big[(x-1)\cdots(x^k-1)\big] \times \big[(x-1)\cdots(x^\ell-1)\big]}.
\]
By choice of $r$, the numerator of $P(x)$ has more factors of $\Phi_{p^r}(x)$
than the denominator, so $\Phi_{p^r}(x)$ divides $P(x)$.
\begin{remark*}
Here is a proof that $P(x)$ is divisible by $\Phi_{p^r}(x)$ for some $r$ using
the $q$-binomial formula, without explicitly identifying $r$. We know that
$P(x)$ is the product of several cyclotomic polynomials, and that $P(1)$ is a
multiple of $p$. Thus there is a factor $\Phi_q(x)$ for which $\Phi_q(1)$ is a
multiple of $p$, which is equivalent to $q$ being a power of $p$.
\end{remark*}
\paragraph{Second proof of claim.}
Note that $P(x)$ is the coefficient of $y^k$ in the polynomial
\[ Q(x, y) \coloneqq (1+xy)(1+x^2y)\dotsm(1+x^ny). \]
Let $a$ be the remainder when $n$ is divided by $p^r$, and let $b$ be the
remainder when $k$ is divided by $p^r$; then we have $a** 1$, while the distances
$P_iQ_j$ are $0.51\sqrt{2} < 1$. We may then perturb each point by a small
amount to ensure that the distance inequalities still hold and have the points
in general position.
\paragraph{Proof that odd $n$ do not work.}
The main claim is the following.
\begin{claim*}
For $1\leq i\leq n$, points $Q_i$ and $Q_{i+1}$ must lie on opposite sides of
line $P_1P_2$.
\end{claim*}
To isolate the geometry component of the problem,
we rewrite the claim in the following contrapositive form,
without referencing the points $Q_i$ and $Q_{i+1}$:
\begin{lemma*}
Suppose $A$ and $B$ are two points such that $\max(P_1A, P_1B, P_2A, P_2B) \le 1$,
and moreover $A$ and $B$ lie on the same side of line $P_1 P_2$.
Further assume no three of $\{P_1, P_2, A, B\}$ are collinear.
Then $AB < 1$.
\end{lemma*}
\begin{center}
\begin{asy}
size(13cm);
pair P_1 = (0,0);
pair P_2 = (1,0);
pair T = (0.5, 3^0.5/2);
pair A = P_1 + dir(20);
pair B = P_2 + 0.96*dir(145);
pair X = extension(P_1, A, P_2, B);
picture lp, rp;
filldraw(lp, arc(P_1, P_2, T)--P_1--cycle, opacity(0.1)+yellow, blue+1.2);
filldraw(lp, arc(P_2, T, P_1)--P_2--cycle, opacity(0.1)+yellow, blue+1.2);
draw(lp, A--B, red);
draw(lp, P_1--A, deepgreen);
draw(lp, P_2--B, deepgreen);
dot(lp, T);
dot(lp, "$X$", X, dir(-90));
dot(lp, "$P_1$", P_1, dir(-90));
dot(lp, "$P_2$", P_2, dir(-90));
dot(lp, "$A$", A, dir(A-P_1));
dot(lp, "$B$", B, dir(245));
pair A = P_1 + 0.9*dir(55);
pair B = (0.85,0.03);
filldraw(rp, arc(P_1, P_2, T)--P_1--cycle, opacity(0.1)+yellow, blue+1.2);
filldraw(rp, arc(P_2, T, P_1)--P_2--cycle, opacity(0.1)+yellow, blue+1.2);
draw(rp, A--B, red);
draw(rp, P_1--A--P_2, deepgreen);
draw(rp, P_1--B--P_2, dotted);
dot(rp, "$P_1$", P_1, dir(-90));
dot(rp, "$P_2$", P_2, dir(-90));
dot(rp, "$A$", A, dir(260));
dot(rp, "$B$", B, dir(65));
add(lp);
add(shift(1.2,0)*rp);
\end{asy}
\end{center}
\begin{proof}[Proof of lemma.]
Suppose for the sake of contradiction
that $A$ and $B$ lie on the same side of $P_1P_2$.
The convex hull of these four points is either a quadrilateral or a triangle.
\begin{itemize}
\ii If the convex hull is a quadrilateral,
assume WLOG that the vertices are $P_1P_2AB$ in order.
Let $X$ denote the intersection of segments $P_1A$ and $P_2B$.
Then \[ 1 + AB = P_1P_2 + AB < P_1X + XP_2 + AX + XB = P_1A + P_2B \leq 2. \]
\ii Otherwise, assume WLOG that $B$ is in the interior of triangle $P_1P_2A$.
Since $\angle P_1BA + \angle P_2BA = 360\dg-\angle P_1BP_2 > 180\dg$,
at least one of $\angle P_1BA$ and $\angle P_2BA$ is obtuse.
Assume WLOG the former angle is obtuse; then $AB < P_1A \leq 1$.
\qedhere
\end{itemize}
\end{proof}
\begin{remark*}
Another proof of the lemma can be found by replacing segment $AB$ with
the intersection of this line on the boundary of the blue region above,
which does not decrease the distance.
In other words, one can assume WLOG that $A$ and $B$ lie on either segment $AB$
or one of the two circular arcs.
One then proves that $AB \le 1$, and that for equality to occur,
one of $A$ and $B$ must lie on segment $P_1 P_2$
However, this approach seems to involve a fair bit more calculation.
Yet another clever approach uses the trivia-fact that a
\href{https://w.wiki/7VaD}{Reuleaux triangle} happens to have constant width.
In any case, it's important to realize that this claim is \emph{not trivial};
while it looks like it is easy to prove, it is not,
owing to the two near-equality cases.
\end{remark*}
It follows from the claim that $Q_i$ is on the same side of line $P_1P_2$
as $Q_1$ if $i$ is odd, and on the opposite side if $i$ is even.
Since $Q_1 = Q_{n+1}$, this means the construction is not possible when $n$ is odd.
\begin{remark*}
The fact that $n$ cannot be odd follows from Theorem 3 of
\href{https://arxiv.org/pdf/1803.01822.pdf}{EPTAS for Max Clique on Disks and
Unit Balls}. In the language of that paper, if $G$ is a unit ball graph, then
the \emph{induced odd cycle parking number} of $\bar G$ is at most 1.
In earlier versions of the proposed problem,
the points were not necessarily distinct to make the even $n$ case nicer,
but this resulted in annoying boundary conditions for the odd $n$ case.
\end{remark*}
\pagebreak
\subsection{USA TST 2024/5, proposed by Ray Li}
\textsl{Available online at \url{https://aops.com/community/p29642892}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Suppose $a_1 < a_2 < \dots < a_{2024}$ is an arithmetic sequence of positive integers,
and $b_1 < b_2 < \dots < b_{2024}$ is a geometric sequence of positive integers.
Find the maximum possible number of integers that could appear in both sequences,
over all possible choices of the two sequences.
\end{mdframed}
\paragraph{Answer.} $11$ terms.
\paragraph{Construction.} Let $a_i = i$ and $b_i = 2^{i-1}$.
\paragraph{Bound.}
We show a $\nu_p$-based approach communicated by Derek Liu,
which seems to be the shortest one.
At first, we completely ignore the geometric sequence $b_i$
and focus only on the arithmetic sequence.
\begin{claim*}
Let $p$ be any prime, and consider the sequence
\[ \nu_p(a_1), \; \nu_p(a_2), \; \dots, \; \nu_p(a_{2024}). \]
Set $C \coloneqq \left\lfloor \log_p(2023) \right\rfloor$.
Then there are at most $C+2$ different values in this sequence.
\end{claim*}
\begin{proof}
By scaling, assume the $a_i$ do not have a common factor,
so that $a_i = a + di$ where $\gcd(a,d) = 1$.
\begin{itemize}
\ii If $p \mid d$, then $p \nmid a$ and $\nu_p(a_i)$ is constant.
\ii Otherwise, assume $p \nmid d$.
We will in fact prove that every term in the sequence
is contained in $\{0, 1, \dots, C\}$ with at most one exception.
Define $M \coloneqq \max_i \nu_p(a_i)$.
If $M \le C$, there is nothing to prove.
Otherwise, fix some index $m$ such that $\nu_p(a_m) = M$.
We know $\nu_p(i-m) \le C$ since $|i-m| \le 2023$.
But now for any other index $i \neq m$;
\begin{align*}
\nu_p(d(i-m)) &= \nu_p(i-m) \le C < M = \nu_p(a_m) \\
\implies \nu_p(a_i) &= \nu_p(a_m + d(i-m)) = \nu_p(i-m) \le C.
\end{align*}
so $\nu_p(a_m)$ is the unique exceptional term of the sequence exceeding $C$.
\qedhere
\end{itemize}
\end{proof}
\begin{remark*}
The bound in the claim is best possible by taking
$a_i = p^M + (i-1)$ for any $M > C$.
Then indeed, the sequence $\nu_p(a_i)$ takes on values in $\{0,1,\dots,C\}$ for $i>1$
while $\nu_p(a_1) = M$.
\end{remark*}
Back to the original problem with $(b_i)$.
Consider the common ratio $r \in \QQ$ of the geometric sequence $(b_i)$.
If $p$ is any prime with $\nu_p(r) \neq 0$,
then every term of $(b_i)$ has a different $\nu_p$.
So there are two cases to think about.
\begin{itemize}
\ii Suppose any $p \ge 3$ has $\nu_p(r) \neq 0$.
Then there are at most
\[ 2 + \log_p(2023) = 2 + \log_3(2023) \approx 8.929 < 11 \]
overlapping terms, as needed.
\ii Otherwise, suppose $r$ is a power of $2$ (in particular, $r \ge 2$ is an integer).
We already have an upper bound of $12$; we need to improve it to $11$.
As in the proof before, we may assume WLOG by scaling down by a power of $2$
that the common difference of $a_i$ is odd.
(This may cause some $b_i$ to become rational non-integers, but that's OK.
However, unless $\nu_2(a_i)$ is constant, the $a_i$ will still be integers.)
Then in order for the bound of $12$ to be achieved,
the sequence $\nu_2(a_i)$ must be contained in $\{0,1,\dots,10,M\}$ for some $M \ge 11$.
In particular, we only need to work with $r = 2$.
Denote by $b$ the unique odd-integer term in the geometric sequence,
which must appear among $(a_i)$.
Then $2b$ appears too, so the common difference of $a_i$ is at most $b$.
But if $(a_i)$ is an arithmetic progression of integers that contains $b$
and has common difference at most $b$,
then no term of the sequence can ever exceed $b + 2023 \cdot b = 2024b$.
Hence $2^M b$ cannot appear for any $M \ge 11$. This completes the proof.
\end{itemize}
\begin{remark*}
There are several other approaches to the problem, but most take some time to execute.
The primary issue is that the common difference of the $a_i$'s could
share prime factors with the common ratio in the $b_i$'s,
which means that merely trying to write out a lot of modular arithmetic equations
leads to a lot of potential technical traps that are not pleasant to defuse.
One unusual thing is that many solutions end up proving a bound of $12$
(in the case the common ratio is $2$) and then having to adjust it to $11$ later.
\end{remark*}
\pagebreak
\subsection{USA TST 2024/6, proposed by Milan Haiman}
\textsl{Available online at \url{https://aops.com/community/p29642897}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Solve over $\RR$ the functional equation
\[ f(xf(y)) + f(y)=f(x+y)+f(xy). \]
\end{mdframed}
In addition to all constant functions, $f(x) \equiv x + 1$ clearly works too.
We prove these are the only solutions.
The solution that follows is by the original proposer.
Let $P(x,y)$ denote the given assertion.
\begin{claim}\label{periodic}
If $f$ is periodic, then $f$ is constant.
\end{claim}
\begin{proof}
Let $f$ have period $d \neq 0$.
From $P(x,y+d)$, we have
\[ f(x(y+d))=f(x+y+d)-f(y+d)-f(xf(y+d))=f(x+y)-f(y)-f(xf(y)). \]
Applying $P(x,y)$ gives
\[ f(x(y+d))=f(xy). \]
In particular, taking $y=0$ yields that $f(dx)=f(0)$.
Thus $f$ is constant, as $d\neq 0$.
\end{proof}
\begin{claim}\label{symmetry}
For all real numbers $x$ and $y$, we have $f(f(x)+y)=f(f(y)+x)$.
\end{claim}
\begin{proof}
Applying $P(f(x),y)$ and then $P(y,x)$ gives us
\begin{align*}
f(f(x)f(y)) &= f(f(x)+y)+f(f(x)y)-f(y) \\
&= f(f(x)+y)+f(x+y)+f(xy)-f(x)-f(y).
\end{align*}
Now swapping $x$ and $y$ gives us $f(f(x)+y)=f(f(y)+x)$.
\end{proof}
\begin{claim}\label{distribute}
If $f$ is nonconstant, then $f(f(x)+y)=f(x)+f(y)$ for all reals $x,y$.
\end{claim}
\begin{proof}
Let $x, y \in \RR$ and let $d \coloneqq f(f(x)+y)-f(x)-f(y)$.
Let $z$ be an arbitrary real number.
By repeatedly applying \Cref{symmetry}, we have
\begin{align*}
f(z+f(f(x)+y)) &= f(f(z)+f(x)+y) \\
&= f(f(x)+f(z)+y) \\
&= f(x+f(f(z)+y)) \\
&= f(x+f(f(y)+z)) \\
&= f(f(x)+f(y)+z) \\
&= f(z+f(x)+f(y)).
\end{align*}
If $d \neq 0$, then $f$ is periodic with period $d$, contradicting \Cref{periodic}.
\end{proof}
\begin{claim}\label{zero}
If $f$ is nonconstant, then $f(0)=1$ and $f(x+1)=f(x)+1$.
\end{claim}
\begin{proof}
From $P(z,0)$ we have $f(zf(0))=f(z)$ for all real $z$.
Then $P(xf(0),y)$ and $P(x,y)$ give us
\begin{align*}
f(xf(0)+y) &= f(y)+f(xf(0)f(y))-f(xf(0)y) \\
&=f(y)+f(xf(y))-f(xy)=f(x+y).
\end{align*}
If $f(0) \neq 1$, then $xf(0)-x$ is a period of $f$ for all $x$, violating \Cref{periodic}.
So we must have $f(0) = 1$.
Now putting $x=0$ in \Cref{distribute} gives $f(x+1)=f(x)+1$.
\end{proof}
\begin{claim}\label{additive}
If $f$ is nonconstant, then $f(x)+f(y)=f(x+y)+1$.
\end{claim}
\begin{proof}
From $P(x+1,y)$ and \Cref{zero}, we have
\[ f((x+1)f(y))=f(x+y+1)+f(xy+y)-f(y)=f(x+y)+f(xy+y)-f(y)+1. \]
Also, from \Cref{distribute} and $P(x,y)$, we have
\[ f((x+1)f(y))=f(xf(y))+f(y)=f(x+y)+f(xy). \]
Thus $f(xy)=f(xy+y)-f(y)+1$.
Replacing $x$ with $\frac{x}{y}$ gives the claim for all $y\ne 0$
(whereas $y=0$ follows from \Cref{zero}).
\end{proof}
\begin{claim}
If $f$ is nonconstant, then $f(x)\equiv x+1$.
\end{claim}
\begin{proof}
We apply \Cref{distribute}, \Cref{additive}, and \Cref{zero}:
\[ f(f(x)+y)=f(x)+f(y)=f(x+y)+1=f(x+y+1). \]
If $f(x) \neq x+1$ for some $x$, then \Cref{periodic} again gives a contradiction.
\end{proof}
\pagebreak
\end{document}
**