\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<b$ by the choice of $r$.
Let $q = \lfloor n/p^r\rfloor$ so $n=p^rq+a$.
Consider taking $x$ to be a primitive $p^r$th root of unity, say $\omega$. Then
\[
  Q(\omega, y) = \left[(1+\omega y)(1+\omega^2y)\cdots (1+\omega^{p^r}y)\right]^q
  (1+\omega y)(1+\omega^2y)\dots (1+\omega^a y).
\]
Now $\omega$, $\omega^2$, \dots, $\omega^{p^r}$ are all the $p^r$th roots of unity,
each exactly once; then we can see that
\begin{align*}
  & (1+\omega y)(1+\omega^2y)\cdots (1+\omega^{p^r}y) \\
  &= (1-\omega(-y))(1-\omega^2(-y))\cdots (1-\omega^{p^r}(-y)) \\
  &= 1-(-y)^{p^r},
\end{align*}
so
\[ Q(\omega,y) = (1-(-y)^{p^r})^q (1+\omega y)(1+\omega^2y)\dots (1+\omega^ay). \]
In particular, for any $m$, if the coefficient of $y^m$ in $Q(w,x)$ is nonzero,
then $m$ must be congruent to one of $0,1, \dots, a \pmod{p^r}$.
Therefore the coefficient of $y^k$ in $Q(\omega, y)$ is zero.
This means that $P(\omega)=0$ whenever $\omega$ is a primitive $p^r$th root
of unity, which proves the claim.
\pagebreak

\section{Solutions to Day 2}
\subsection{USA TST 2024/4, proposed by Ray Li}
\textsl{Available online at \url{https://aops.com/community/p29643081}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
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}
\end{mdframed}
\paragraph{Answer.}
Even integers only.

\paragraph{Proof that even $n$ work.}
If we ignore the conditions that the points are pairwise distinct and form no
collinear triples, we may take
\[
  P_{2i+1}=(0.51, 0), \quad P_{2i}=(-0.51, 0), \quad
  Q_{2i+1}=(0, 0.51), \quad Q_{2i}=(0,-0.51).
\]
The distances $P_iP_{i+1}$ and $Q_iQ_{i+1}$ are $1.02 > 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}
