\documentclass[11pt]{scrartcl}
\usepackage[sexy]{evan}
\ihead{\footnotesize\textbf{\thetitle}}
\ohead{\footnotesize\theauthor}
\begin{document}
\title{USA TSTST 2024 Solutions}
\subtitle{United States of America --- TST Selection Test}
\author{Andrew Gu, Evan Chen, Gopal Goel, Luke Robitaille}
\date{66\ts{th} IMO 2025 Australia and 14\ts{th} EGMO 2025 Kosovo}
\maketitle
\tableofcontents
\newpage
\addtocounter{section}{-1}
\section{Problems}
\begin{enumerate}[\bfseries 1.]
\item %% Problem 1
For every ordered pair of integers $(i,j)$, not necessarily positive,
we wish to select a point $P_{i,j}$ in the Cartesian plane
whose coordinates lie inside the unit square defined by
\[ i < x < i+1, \qquad j < y < j+1. \]
Find all real numbers $c > 0$ for which it's possible to choose these points
such that for all integers $i$ and $j$,
the (possibly concave or degenerate) quadrilateral
$P_{i,j} P_{i+1,j} P_{i+1,j+1} P_{i,j+1}$
has perimeter strictly less than $c$.
\item %% Problem 2
Let $p$ be an odd prime number. Suppose $P$ and $Q$ are polynomials with integer
coefficients such that $P(0)=Q(0)=1$, there is no nonconstant polynomial
dividing both $P$ and $Q$, and
\[
1 + \cfrac{x}{1 + \cfrac{2x}{1 + \cfrac{\ddots}{1 +
(p-1)x}}}=\frac{P(x)}{Q(x)}.
\]
Show that all coefficients of $P$ except for the constant coefficient are
divisible by $p$, and all coefficients of $Q$ are \emph{not} divisible by $p$.
\item %% Problem 3
Let $A = \{a_1, \dots, a_{2024}\}$ be a set of $2024$ pairwise distinct real numbers.
Assume that there exist positive integers $b_1, b_2,\dotsc,b_{2024}$
such that \[ a_1b_1 + a_2b_2 + \dots + a_{2024}b_{2024} = 0. \]
Prove that one can choose $a_{2025}, a_{2026}, a_{2027}, \dots$ such that
$a_k \in A$ for all $k \ge 2025$ and, for every positive integer $d$,
there exist infinitely many positive integers $n$ satisfying
\[ \sum_{k=1}^n a_k k^d = 0. \]
\item %% Problem 4
Let $ABCD$ be a quadrilateral inscribed in a circle with center $O$ and $E$ be
the intersection of segments $AC$ and $BD$. Let $\omega_1$ be the circumcircle
of $ADE$ and $\omega_2$ be the circumcircle of $BCE$. The tangent to
$\omega_1$ at $A$ and the tangent to $\omega_2$ at $C$ meet at $P$. The
tangent to $\omega_1$ at $D$ and the tangent to $\omega_2$ at $B$ meet at $Q$.
Show that $OP=OQ$.
\item %% Problem 5
For a positive integer $k$,
let $s(k)$ denote the number of $1$s in the binary representation of $k$.
Prove that for any positive integer $n$,
\[ \sum_{i=1}^{n}(-1)^{s(3i)} > 0. \]
\item %% Problem 6
Determine whether there exists a function $f \colon \ZZ_{> 0} \to \ZZ_{>0}$
such that for all positive integers $m$ and $n$,
\[ f(m+nf(m))=f(n)^m+2024! \cdot m. \]
\item %% Problem 7
An infinite sequence $a_1$, $a_2$, $a_3$, \dots\ of real numbers satisfies
\[ a_{2n-1} + a_{2n} > a_{2n+1} + a_{2n+2} \qquad
\mbox{and} \qquad a_{2n} + a_{2n+1} < a_{2n+2} + a_{2n+3} \]
for every positive integer $n$.
Prove that there exists a real number $C$ such
that $a_{n} a_{n+1} < C$ for every positive integer $n$.
\item %% Problem 8
Let $ABC$ be a scalene triangle,
and let $D$ be a point on side $BC$ satisfying $\angle BAD=\angle DAC$.
Suppose that $X$ and $Y$ are points inside $ABC$
such that triangles $ABX$ and $ACY$ are similar and quadrilaterals $ACDX$ and $ABDY$ are cyclic.
Let lines $BX$ and $CY$ meet at $S$ and lines $BY$ and $CX$ meet at $T$.
Prove that lines $DS$ and $AT$ are parallel.
\item %% Problem 9
Let $n \ge 2$ be a fixed integer. The cells of an $n \times n$ table are
filled with the integers from $1$ to $n^2$ with each number appearing exactly once.
Let $N$ be the number of unordered quadruples of cells on this board
which form an axis-aligned rectangle,
with the two smaller integers being on opposite vertices of this rectangle.
Find the largest possible value of $N$.
\end{enumerate}
\pagebreak
\section{Solutions to Day 1}
\subsection{TSTST 2024/1, proposed by Karthik Vedula}
\textsl{Available online at \url{https://aops.com/community/p31006977}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
For every ordered pair of integers $(i,j)$, not necessarily positive,
we wish to select a point $P_{i,j}$ in the Cartesian plane
whose coordinates lie inside the unit square defined by
\[ i < x < i+1, \qquad j < y < j+1. \]
Find all real numbers $c > 0$ for which it's possible to choose these points
such that for all integers $i$ and $j$,
the (possibly concave or degenerate) quadrilateral
$P_{i,j} P_{i+1,j} P_{i+1,j+1} P_{i,j+1}$
has perimeter strictly less than $c$.
\end{mdframed}
\paragraph{Answer.} $c\geq 4$.
\paragraph{Proof $c < 4$ is not possible.}
Let $n$ be an arbitrary positive integer. We take an $n\times n$ subgrid of unit
squares (i.e. $P_{i, j}$ for $1\leq i, j\leq n$), and compute a lower bound on
the average of all possible quadrilaterals from this subgrid.
Consider the average length of the ``top side'' of all possible quadrilaterals
in this grid. Note that this is equal to:
\[
\frac{1}{(n-1)^2}\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}P_{i,j}P_{i+1,j}
\geq \frac{1}{(n-1)^2}\sum_{j=1}^{n-1}P_{1,j}P_{n,j}
> \frac{n-2}{n-1}.
\]
We can apply this bound to all four sides of the quadrilateral
(the left, right, bottom, and top sides)
to find that the average perimeter of all possible quadrilaterals is greater than
\[ \frac{4(n-2)}{n-1}=4-\frac{4}{n-1}. \]
This means we can always find a quadrilateral whose perimeter is at least $4-\frac{4}{n-1}$.
By taking sufficiently large $n$, this lower bound will exceed $c$.
\paragraph{Proof $c = 4$ is possible.}
We'll place point $P_{i, j}$ at the coordinates $(f(i), f(j))$
for some function $f\colon \ZZ \to \RR$.
The perimeter of $P_{i, j}P_{i+1, j}P_{i+1,j+1}P_{i, j+1}$ is then
\[ 2\big(|f(i+1)-f(i)| + |f(j+1)-f(j)|\big). \]
Therefore we have a valid construction for $c = 4$
if $f$ satisfies $n < f(n) < n+1$ and $|f(n+1)-f(n)| < 1$ for all $n$.
This is achieved by
\[
f(n) = n + 0.5 + \begin{cases}
-\sum_{i=1}^{n} \frac{1}{10^i} & \text{if } n \geq 0, \\
\sum_{i=1}^{-n} \frac{1}{10^i} & \text{if } n < 0. \\
\end{cases}
\]
Let's check the conditions.
The sum is bounded by $\sum_{i=1}^{\infty}\frac{1}{10^i}=\frac{1}{9}$ in magnitude,
so $n < f(n) < n+1$.
Furthermore, we can verify that
\[
f(n+1)-f(n) = 1 - \begin{cases}
\frac{1}{10^{n+1}} & \text{if } n \geq 0, \\
\frac{1}{10^{-n}} & \text{if } n < 0
\end{cases}
< 1.
\]
\pagebreak
\subsection{TSTST 2024/2, proposed by Andrew Gu}
\textsl{Available online at \url{https://aops.com/community/p31006985}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $p$ be an odd prime number. Suppose $P$ and $Q$ are polynomials with integer
coefficients such that $P(0)=Q(0)=1$, there is no nonconstant polynomial
dividing both $P$ and $Q$, and
\[
1 + \cfrac{x}{1 + \cfrac{2x}{1 + \cfrac{\ddots}{1 +
(p-1)x}}}=\frac{P(x)}{Q(x)}.
\]
Show that all coefficients of $P$ except for the constant coefficient are
divisible by $p$, and all coefficients of $Q$ are \emph{not} divisible by $p$.
\end{mdframed}
\paragraph{Solution 1.}
We first make some general observations about rational functions represented
through continued fractions.
\begin{claim*}
Let $a_1$, $a_2$, \dots, be a sequence of nonzero integers. Define the
sequence of polynomials $P_1(x) = 1$, $P_2(x) = 1 + a_1x$, and
\[P_{k+1}(x) = P_k(x) + a_kxP_{k-1}(x)\]
for $k\geq 1$.
Then the following properties hold for all $k\geq 0$:
\begin{itemize}
\item $P_k(0) = 1$,
\item $\gcd(P_{k+1}, P_{k}) = 1$, and
\item $\deg P_k = \left\lfloor k/2\right\rfloor$.
\item \(
1 + \cfrac{a_kx}{1 + \cfrac{a_{k-1}x}{1 + \cfrac{\ddots}{1 + a_1x}}}=\dfrac{P_{k+1}(x)}{P_k(x)}.
\)
\end{itemize}
\end{claim*}
\begin{proof}
These all follow by induction.
\end{proof}
With the setup of the claim, the polynomials $P$ and $Q$ in the problem are
exactly $P_{p}$ and $P_{p}$ for the sequence $a_1=p-1$, $a_2=p-2$, \dots, $a_{p-1}=1$.
From here, we will define $P$ and $Q$ in terms of this recurrence
and make two transformations on the $a_i$.
First, subtract $p$ from each $a_i$ so we now have $a_1 = -1$, $a_2 = -2$,
\dots, $a_{p-1} = -(p-1)$. The coefficients of $P$ and $Q$ only have changed
by a multiple of $p$. The claim also shows that $P(0)=Q(0)=1$, $\gcd(P, Q)=1$,
and the degrees of $P$ and $Q$ have not changed, i.e.\ no leading terms have been
added or removed. Therefore it is equivalent to work with this sequence instead.
Similarly, we can multiply $a_i$ by $-1$ to get $a_1 = 1$, $a_2 = 2$, $\dots$,
$a_{p-1} = p-1$. This is equivalent to replacing $x$ with $-x$, so some
coefficients of $P$ and $Q$ are negated by this. The key conditions still remain
unchanged.
\begin{remark*}
For rigor, it's important to prove the facts about continued fractions first
rather than going straight to the coefficient replacement as the requirements
imposed by the problem statement on $P$ and $Q$ are not always preserved
modulo $p$.
\end{remark*}
At this point, we are ready to directly calculate the polynomials $P_n$.
\begin{claim*}
For all $n$, we have
\[P_n(x) = \sum_{k\geq 0} \frac{n!}{2^kk!(n-2k)!}x^k.\]
Here, we define $\frac{n!}{(n-2k)!} = n(n-1)\dots(n-2k+1)$ so the sum actually stops at $k=\lfloor n/2\rfloor$.
\end{claim*}
\begin{proof}
We use induction. The base cases are clear, and
\begin{align*}
P_n + nxP_{n-1} & = \sum_{k \ge 0} \frac1{2^k k!} \frac{n!}{(n-2k)!} x^k
+ nx \sum_{k \ge 0} \frac1{2^k k!} \frac{(n-1)!}{(n-2k-1)!} x^k\\
& = \sum_{k \ge 0} \frac1{2^k k!} \frac{n!}{(n-2k)!} x^k
+ \sum_{k \ge 0} \frac1{2^k k!} \frac{n!}{(n-2k-1)!} x^{k+1}\\
& = \sum_{k \ge 0} \frac1{2^k k!} \frac{n!}{(n-2k)!} x^k
+ \sum_{k \ge 1} \frac1{2^{k-1} (k-1)!} \frac{n!}{(n-2k+1)!} x^k\\
& = 1 + \sum_{k \ge 1} \left[\frac1{2^k k!} \frac{n!}{(n-2k)!}
+ \frac1{2^{k-1} (k-1)!} \frac{n!}{(n-2k+1)!}\right] x^k\\
& = 1 + \sum_{k \ge 1} \frac1{2^k k!} \frac{n!}{(n-2k+1)!}
\left[(n - 2k + 1) + 2k\right] x^k\\
& = 1 + \sum_{k \ge 1} \frac1{2^k k!} \frac{(n + 1)!}{(n-2k+1)!} x^k\\
& = \sum_{k \ge 0} \frac1{2^k k!} \frac{(n + 1)!}{(n-2k+1)!} x^k\\
& = P_{n+1}. \qedhere
\end{align*}
\end{proof}
At this point we can directly check the coefficients of $P$ and $Q$. We have
\[P(x) = P_p(x) = \sum_{k\geq 0} \frac{p!}{2^kk!(p-2k)!}x^k.\]
For $k=0$, we get a coefficient of $1$. For $k\geq 1$, the denominator is not a
multiple of $p$, so the remaining coefficients are multiples of $p$. Meanwhile,
the coeffiicents for $Q$ are $\frac{(p-1)!}{2^kk!(p-1-2k)!}$. None of these are
divisible by $p$ because $(p-1)!$ is not divisible by $p$.
\begin{remark*}
This problem was created from the identity
\[
\cfrac{1}{1-\cfrac{x}{1-\cfrac{2x}{1-\cfrac{3x}{1-\dotsc}}}} = \sum_{i=0}^{\infty}(2i-1)!!x^i.
\]
You can use this to solve the problem. However, the proof of the identity as
well as the details to convert this into the given problem are very lengthy so
this is only left as a remark.
\end{remark*}
\paragraph{Solution 2.}
\begin{lemma*}
Define a series of polynomials $A_n$, $B_n$, $C_n$, $D_n$ by letting
$A_1 = 1$, $B_1 = x$, $C_1 = 1$, and $D_1 = 0$, and for $n \geq 2$,
\begin{align*}
A_n &= A_{n-1} + B_{n-1} &
B_n &= nxA_{n-1} \\
C_n &= C_{n-1} + D_{n-1} &
D_n &= nxC_{n-1}.
\end{align*}
Then, if we define $f_k(t) = 1 + \frac{kx}{t}$, then
\[( f_1 \circ f_2 \circ \dotsb \circ f_n)(t) = \frac{A_n t + B_n}{C_n t + D_n}. \]
\end{lemma*}
\begin{proof}
Straightforward by induction: the $n=1$ case is true and for $n \geq 2$,
\[ \frac{A_{n-1} f_n(t) + B_{n-1}}{C_{n-1} f_n(t) + D_{n-1}} =
\frac{A_{n-1} (t + nx) + B_{n-1} t}{C_{n-1}(t + nx) + D_{n-1} t} =
\frac{(A_{n-1} + B_{n-1})t + nxA_{n-1}}{(C_{n-1} + D_{n-1})t + nxD_{n-1}}. \qedhere \]
\end{proof}
It is possible to solve these recurrences algebraically,
but there is in fact a nice combinatorial interpretation of these polynomials:
\begin{lemma*}
Let $\mathcal{I}_n$ be the set of involutions on $\{1,2,\dotsc,n\}$
and for $\pi \in \mathcal{I}_n$, let $a(\pi)$ denote the number of transpositions in $\pi$.
Let $\mathcal{J}_n \subseteq \mathcal{I}_n$ be the set of involutions $\pi$
where the minimal fixed point is less than the minimal $x$ with $\pi(x) < x$.
Then, for all $k \geq 1$, we have
\begin{align*}
A_n &= \sum_{\pi \in \mathcal{I}_n} x^{a(\pi)} &
B_n &= \sum_{\substack{\pi \in \mathcal{I}_{n+1} \\\pi(n+1)\neq n+1}} x^{a(\pi)} \\
C_n &= \sum_{\pi \in \mathcal{J}_n} x^{a(\pi)} &
D_n &= \sum_{\substack{\pi \in \mathcal{J}_{n+1} \\\pi(n+1)\neq n+1}} x^{a(\pi)}.
\end{align*}
\end{lemma*}
\begin{proof}
We use induction on $n$, with the case $n=1$ being easily verified.
For $n \geq 2$, note that
\[A_n - B_{n-1} = \sum_{\substack{\pi \in \mathcal{I}_{k+1} \\\pi(k+1)= k+1}} x^{a(\pi)} = A_{n-1}.\]
Moreover, every $\pi \in \mathcal{I}_{n+1}$ swapping $n+1$ with something else
can be characterized by one of $n$ choices for $\pi(n+1)$
and an involution on the remaining $n-1$ elements.
Therefore $B_n = nxA_{n-1}$.
A similar proof holds for the $C_n$ and $D_n$.
\end{proof}
We now note that
\[ \frac{P(x)}{Q(x)} = (f_1 \circ f_2 \circ \dotsb \circ f_{p-1})(1)
= \frac{A_{p-1} + B_{p-1}}{C_{p-1} + D_{p-1}} = \frac{A_p}{C_p}. \]
It suffices to show that all nonconstant coefficients of $A_p$ are divisible by $p$
and that all coefficients of $C_p$ are not divisible by $p$.
If we show this, then any nonconstant factor dividing $A_p$
must have a leading coefficient divisible by $p$
(proof: reduce the factorization mod $p$),
then any nonconstant factor dividing $C_p$ cannot have a leading coefficient divisible by $p$.
Moreover, since $A_p$ and $C_p$ have constant terms of $1$,
they are relatively prime and thus $P = A_p$ and $Q = C_p$ (up to sign).
We now evaluate the coefficients of $A_p$ and $C_p$.
We observe that
\[A_p = \sum_{k=0}^{\frac{p-1}{2}}\binom{p}{2k} (2k-1)!! x^k,\]
and it is easy to see that $A_p \equiv 1 \pmod{p}$.
Computing the coefficients of $C_n$ is a bit harder.
Consider elements of $\mathcal{J}_p$ with $0 \leq k \leq \frac{p-1}{2}$ swaps
and a minimal fixed point of $a+1$ (for $0 \leq a \leq k$).
Everything in $\{1,\dotsc,a\}$ must be paired with something greater than $a+1$,
and there are $k-a$ swaps among the remaining elements.
It follows that
\begin{align*}
C_p &= \sum_{k=0}^{\frac{p-1}{2}} \sum_{a=0}^k \frac{(p-a-1)!}{(p-2a-1)!} \binom{p-2a-1}{2k-2a}(2k-2a-1)!! \cdot x^k \\
&= \sum_{k=0}^{\frac{p-1}{2}} \sum_{a=0}^k \frac{(p-a-1)!}{(p-2k-1)! 2^{k-a} (k-a)!} x^k \\
&= \sum_{k=0}^{\frac{p-1}{2}} \frac{(p-1)!}{(p-2k-1)!} \left(\sum_{a=0}^k \frac{1}{2^{k-a} (k-a)! \prod_{j=1}^a (p-j)}\right) x^k \\
&\equiv \sum_{k=0}^{\frac{p-1}{2}} \frac{(p-1)!}{(p-2k-1)!} \left(\sum_{a=0}^k \frac{(-1)^a}{2^{k-a} (k-a)! a!}\right) x^k \\
&= \sum_{k=0}^{\frac{p-1}{2}} \frac{(p-1)!}{(p-2k-1)!k!} \left(\sum_{a=0}^k \binom{k}{a}\frac{(-1)^a}{2^{k-a}}\right) x^k \\
&= \sum_{k=0}^{\frac{p-1}{2}} \frac{(p-1)!}{(p-2k-1)!k!} \left(-1+\frac{1}{2}\right)^k x^k.
\end{align*}
The result follows.
\begin{remark*}
It is not hard to see that $C_p$ simplifies further mod $p$ to
\[ \sum_{k=0}^{\frac{p-1}{2}}(-1)^k (2k-1)!! x^k. \]
\end{remark*}
\pagebreak
\subsection{TSTST 2024/3, proposed by Daniel Zhu}
\textsl{Available online at \url{https://aops.com/community/p31006991}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $A = \{a_1, \dots, a_{2024}\}$ be a set of $2024$ pairwise distinct real numbers.
Assume that there exist positive integers $b_1, b_2,\dotsc,b_{2024}$
such that \[ a_1b_1 + a_2b_2 + \dots + a_{2024}b_{2024} = 0. \]
Prove that one can choose $a_{2025}, a_{2026}, a_{2027}, \dots$ such that
$a_k \in A$ for all $k \ge 2025$ and, for every positive integer $d$,
there exist infinitely many positive integers $n$ satisfying
\[ \sum_{k=1}^n a_k k^d = 0. \]
\end{mdframed}
It will be convenient to use $0$-based indexing here,
i.e.\ $A = \{a_0, \dotsc, a_{2023}\}$ and so on.
Let $m = \sum_{i=0}^{2023} b_i$.
By appending $b_i-1$ copies of $a_i$ for each $i$,
we may extend the sequence to $a_0, \dotsc, a_{m-1}$ such that $a_0+\dotsb+a_{m-1} = 0$.
\paragraph{Solution by direct construction.}
Let $s_m(n)$ be the sum of the base-$m$ digits of $n$, reduced modulo $m$.
We now claim that $a_k = a_{s_m(k)}$ works.
It is clear that this extends the original sequence in a valid way.
\begin{claim*}
Fix $d$.
Then the sum
\[\sum_{k=0}^{n-1}a_k(k+1)^d\]
is zero when $n = cm^{d+1}$ for any positive integer $c$.
\end{claim*}
If we prove this, then the problem is solved as there are infinitely many possible $c$.
We have two proofs of this.
\begin{proof}[Proof of claim by expansion (Andrew Gu)]
We only need to show that each block of $m^{d+1}$ terms sums to zero. Each
block takes the form
\[ S = \sum_{k=cm^{d+1}}^{(c+1)m^{d+1}-1}a_{s_m(k)}(k+1)^d. \]
We group terms based on the value of $s_m(k)$.
The values of $k$ in this sum are given by
\[\left\{ cm^{d+1}+\sum_{i=0}^{d}e_im^i
\mid (e_0, \dotsc, e_d) \in \{0, \dotsc, m-1\}^{d+1}\right\}.\]
In this form, the sum of the base-$m$ digits is $s_m(c)+e_0+\dotsb+e_d$.
Therefore we can write
\[ S = \sum_{i=0}^{m-1}a_i
\underbrace{\Bigg(\sum_{
\substack{(e_0, \dotsc, e_d) \in \{0, \dotsc, m-1\}^{d+1} \\
e_0+\dots+e_d\equiv i-s_m(c)\pmod{m}}}
\underbrace{\Big(cm^{d+1}+1+\sum_{j=0}^{d}e_jm^j\Big)^d}_{(2)}\Bigg)}_{(1)}. \]
Since $\sum a_i=0$, it suffices to show that the value of the coefficient
given by (1) is independent of $i$.
Expand the term (2) with the multinomial theorem.
Each monomial in the expansion is a product of terms $c$, $m$, $e_j$.
Since the exponent is $d$, no monomial is divisible by the whole product $e_0e_1\dotsm e_d$.
Since the tuples $(e_0, \dotsc, e_d)$ are uniformly distributed
over all possible tuples when one or more coordinates are removed,
that means that the sum of each monomial term is independent of $i$.
We conclude that the sum (1) is independent of $i$ as well.
\end{proof}
\begin{proof}[Proof of claim by Fourier transform]
Let $\omega \neq 1$ be an $m$\ts{th} root of unity.
Then, define the operator
\[\Delta^{(\omega)}_a f(x) = \sum_{i=0}^{m-1} \omega^i f(x + ia).\]
By looking at the leading coefficients, one can see that $\Delta^{(\omega)}_a$
lowers the degree of a polynomial by at least $1$.\footnote{In fact the degree
decreases by exactly $1$, but this is not that important.}
As a consequence, by letting $f(x) = (x+1)^d$ we conclude that
\[ \sum_{k \in [0, m_e)} \omega^{s_m(k)} (k+1)^d
= (\Delta^{(\omega)}_{m^{e-1}} \dotsb \Delta^{(\omega)}_{m} \Delta^{(\omega)}_{1} f)(0) = 0.\]
Since $a_1 + \dotsb + a_m = 0$, by a discrete Fourier transform we may write
$a_i = \sum_{j=1}^{m-1} c_j e^{2\pi ij/m}$ for some
$c_1, \dots, c_{m-1} \in \CC$.
Therefore
\[ \sum_{k=0}^{m^e-1} a_k (k+1)^d
= \sum_{j=1}^{m-1} c_j \sum_{k=0}^{m^e-1} (e^{2\pi ij/m})^{s_m(k)} (k+1)^d
= 0. \qedhere \]
\end{proof}
\paragraph{Inductive solution.}
Define $m$ and extend the sequence to $a_{m-1}$ as before.
For $d \geq 0$, let $\Sigma_d(S)$ denote $\sum_{k \in S} k^d$.
Also, for $d \geq 0$ call a tuple of sets $(S_0,\dotsc,S_{m-1})$
to be \emph{$d$-uniform} if for all $0 \leq d' \leq d$
we have $\Sigma_{d'}(S_0) = \Sigma_{d'}(S_1) = \dots = \Sigma_{d'}(S_{m-1})$.
\begin{lemma}
\label{lemma:fix}
Suppose $(S_0,\dotsc,S_{m-1})$ is $d$-uniform.
Then for all $0 \leq d' \leq d+1$, $x \in \RR$, and $0 \leq i, j < m$,
the quantity $\Sigma_{d'}(S_i+x) - \Sigma_{d'}(S_j + x)$ is independent of $x$.
\end{lemma}
\begin{proof}
We may expand
\[\Sigma_{d'}(S_i + x) = \sum_{k=0}^{d'} \binom{d'}{k} x^{d'-k} \Sigma_k(S_i).\]
By $d$-uniformity, the terms with $k\leq d$ are independent of $i$ and go away
in the subtraction. The only term left is when $k = d' = d+1$. However, this
term is independent of $x$, as desired.
\end{proof}
\begin{lemma}
\label{lemma:induct}
Suppose $(S_0,\dotsc,S_{m-1})$ is a $d$-uniform partition of $[0, n)$.
Then there exists a $(d+1)$-uniform partition $(S'_0,\dotsc,S'_{m-1})$ of $[0, mn)$
such that $S_i \subseteq S'_i$ for all $i$.
\end{lemma}
\begin{proof}
We let $S'_i = \bigcup_{k=0}^{m-1} (S_{(i+k) \bmod m} + kn)$.
Then, for every $0 \leq d' \leq d+1$ and $0 \leq i,j < m$, we have
\begin{align*}
\Sigma_{d'}(S'_i) - \Sigma_{d'}(S'_j)
&= \sum_{k=0}^{m-1}\Sigma_{d'}(S_{(i+k) \bmod m}+ kn) - \Sigma_{d'}(S_{(j+k) \bmod m} + kn) \\
&= \sum_{k=0}^{m-1}\Sigma_{d'}(S_{(i+k) \bmod m}) - \Sigma_{d'}(S_{(j+k) \bmod m}) \\
&= 0. \qedhere
\end{align*}
\end{proof}
Consider the $0$-uniform partition of $[0, m)$ given by $(\{0\}, \{1\}, \dotsc, \{m-1\})$.
By repeatedly applying \Cref{lemma:induct},
we get $d$-uniform partitions $(S^{(d)}_0, \dotsc, S^{(d)}_{m-1})$ of $[0, m^{d+1})$
such that $S^{(d)}_i \subseteq S^{(d+1)}_i$ for all $d$ and $i$.
For every $k$, let $i$ be the unique index such that $k \in S^{(d)}_i$ for some $d$,
and let $a_k = a_i$.
(This doesn't redefine $a_0$, \dots, $a_{m-1}$ as for $k < m$, we have $k \in S^{(0)}_k$.)
Then, for each $e \geq d$, we find that
\[ \sum_{k=0}^{m^{e+1}-1} a_k (k+1)^d = \sum_{i=0}^{m-1} a_i \sum_{k \in S^{(e)}_i} (k+1)^d
= \sum_{i=0}^{m-1} a_i \sum_{j=1}^d \binom{d}{j} \Sigma_j(S^{(e)}_i) = 0. \]
\begin{remark*}
The construction here is essentially the same as the sum-of-digits construction
(in fact it would be exactly the same if we replace $(i+k) \bmod m$ in the proof
of \Cref{lemma:induct} with $(i-k) \bmod m$).
However, it hints at some flexibility in the construction which is less apparent with other approaches.
For example, if $G$ is any transitive subgroup of permutations on $[0, m)$ and
$\pi_0 = \id$, $\pi_1$, \dots, $\pi_{\abs{G}-1}$ is an enumeration of the elements of $G$,
one can turn a $d$-uniform partition $(S_0,\dotsc,S_{m-1})$ of $[0, n)$
into a $(d+1)$-uniform partition $(S'_0,\dotsc,S'_{m-1})$ of $[0, \abs{G}n)$ by
letting $S'_i = \bigcup_{k=0}^{\abs{G}-1} (S_{\pi_k(i)} + kn)$.
Here we used the special case $\pi_k(i) = (i+k) \bmod m$;
it may also be natural to let $G$ be the set of all $m!$ permutations.
\end{remark*}
\begin{remark*}
The construction in the solution has appeared a number of times in the literature; see
\begin{itemize}
\frenchspacing
\ii D. H. Lehmer, The Tarry-Escott problem, \emph{Scripta Math.} \textbf{13}, 37–41, 1947;
\ii E. Prouhet, Mémoire sur quelques relations entre les puissances des nombres,
\emph{C. R. Acad. Sci. Paris} \textbf{33}, 225, 1851;
\ii E. M. Wright, \href{https://doi.org/10.1017/S0013091500002698}{Equal sums of like powers},
\emph{Proc. Edinburgh Math. Soc.} 2nd series \textbf{8}, 138–142, 1949;
\ii E. M. Wright, \href{https://doi.org/10.2307/2309513}{Prouhet’s 1851 solution of the Tarry-Escott problem of 1910},
\emph{Amer. Math. Monthly} \textbf{66}, 199–201, 1959.
\nonfrenchspacing
\end{itemize}
\end{remark*}
\pagebreak
\section{Solutions to Day 2}
\subsection{TSTST 2024/4, proposed by Merlijn Staps}
\textsl{Available online at \url{https://aops.com/community/p31007004}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $ABCD$ be a quadrilateral inscribed in a circle with center $O$ and $E$ be
the intersection of segments $AC$ and $BD$. Let $\omega_1$ be the circumcircle
of $ADE$ and $\omega_2$ be the circumcircle of $BCE$. The tangent to
$\omega_1$ at $A$ and the tangent to $\omega_2$ at $C$ meet at $P$. The
tangent to $\omega_1$ at $D$ and the tangent to $\omega_2$ at $B$ meet at $Q$.
Show that $OP=OQ$.
\end{mdframed}
\paragraph{Solution 1.}
Let $R = \ol{AD} \cap \ol{BC}$ (possibly at infinity,
but we'll see it's an Euclidean point later).
\begin{center}
\begin{asy}
size(12cm);
pair A = dir(190), B = dir(350), C = dir(80), D = dir(120), O = (0, 0);
pair E = extension(A, C, B, D), R = extension(A, D, B, C);
pair P = reflect(O, (A+C)/2) * R;
pair Q = reflect(O, (B+D)/2) * R;
draw(A--C^^B--D, gray(0.5));
draw(A--R^^C--P^^B--Q, heavycyan);
draw(B--R^^D--Q^^A--P, heavymagenta);
draw(O--P^^O--Q^^O--R, brown);
filldraw(circumcircle(A, D, E), yellow+opacity(0.1), gray(0.5));
filldraw(circumcircle(B, C, E), yellow+opacity(0.1), gray(0.5));
draw(unitcircle);
dot("$A$", A, dir(200));
dot("$B$", B, dir(340));
dot("$C$", C, dir(C));
dot("$D$", D, dir(D));
dot("$E$", E, 1.5*dir(190));
dot("$O$", O, dir(270));
dot("$P$", P, dir(P));
dot("$Q$", Q, dir(Q));
dot("$R$", R, dir(R));
\end{asy}
\end{center}
\begin{claim*}
$ACRP$ is an isosceles trapezoid with $\ol{AC} \parallel \ol{PR}$.
Consequently, $R$ is an Euclidean point, and $OP = OR$.
\end{claim*}
\begin{proof}
It is equivalent to show that $\triangle PAC \stackrel{-}{\cong} \triangle RCA$,
or without using $R$, that
\[
\dang PAC = \dang ACR = \dang ACB, \quad \text{and} \quad
\dang PCA = \dang CAR = \dang CAD.
\]
Indeed, we have
\[ \dang PAC = \dang ADE = \dang ADB = \dang ACB \]
and likewise $\dang PCA = \dang CAD$, as requested.
\end{proof}
Similarly $OQ = OR$, so we're done.
\paragraph{Solution 2.}
\begin{center}
\begin{asy}
unitsize(70);
pair A = dir(130);
pair B = dir(83);
pair C = dir(-40);
pair D = dir(-140);
pair O = 0;
pair E = extension(A,C,B,D);
pair O1 = circumcenter(A,E,D);
pair O2 = circumcenter(B,E,C);
pair P = extension(A, (O1-A)*dir(90)+A, C, (O2-C)*dir(90)+C);
pair Q = extension(D, (O1-D)*dir(90)+D, B, (O2-B)*dir(90)+B);
pair Ap = 2*foot(O,A,P)-A;
pair Bp = 2*foot(O,B,Q)-B;
draw(unitcircle, lightblue);
draw(A--C, green);
draw(B--D, green);
draw(circumcircle(A,E,D), dotted);
draw(circumcircle(B,E,C), dotted);
draw(A--P--C, red);
draw(B--Q--D, red);
draw(Bp--O--D, dashed+red);
draw(Ap--O--C, dashed+red);
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$D$", D, dir(-100));
dot("$O$", O, 1.5*dir(-90));
dot("$E$", E, dir(180));
dot("$P$", P, dir(-90));
dot("$Q$", Q, dir(-90));
dot("$A'$", Ap, 1.5*dir(55));
dot("$B'$", Bp, dir(Bp));
\end{asy}
\end{center}
Let $PA$ intersect $(ABCD)$ again at $A'$ and let $QB$ intersect $(ABCD)$ again at $B'$.
The problem follows from the following claim.
\begin{claim*}
$OA'PC\cong ODQB'$.
\end{claim*}
\begin{proof}
We use directed angles mod $\pi$. Note that
\[\dang ODQ = \dang ODA + \dang ADQ = \dang DAO + \dang PAD = \dang PAO = \dang OA'P,\]
and similarly $\dang OCP = \dang OB'Q$. Furthermore,
\[\dang A'AD = \dang AED = \dang CEB = \dang CBB',\]
so $A'D = CB'$, i.e. $A'CDB'$ is an isosceles trapezoid.
This means $\dang A'OC = \dang DOB'$.
Combined with $OA'=OB'=OD=DC$, these three angle equalities imply the congruency.
\end{proof}
\paragraph{Solution 3 using complex numbers (Noah Walsh).}
Use complex numbers with $(ABCD)$ as the unit circle.
Because $PA$ is tangent to $(ADE)$, we have $\angle PAC = \angle ADB = \frac{1}{2}\angle AOB$,
and therefore
\begin{align*}
\frac{\frac{p-a}{c-a}}{\frac{\ol{p} - a^{-1}}{c^{-1} - a^{-1}}} &= \frac{a}{b}\\
\implies b\frac{p-a}{c-a} &= a\frac{ac\ol{p} - c}{a-c}\\
\implies bp + a^2c\ol{p} &= ab + ac.\\
\end{align*}
The condition that $PC$ is tangent to $(BCE)$ can be expressed
by swapping $a$ with $c$ and $b$ with $d$, so we get
\begin{align*}
bp + a^2c\ol{p} &= ab + ac\\
dp + ac^2\ol{p} &= cd + ac \\
\implies p(ad-bc) &= acd + a^2c - abc - ac^2\\
\implies p &= \frac{ac(a+d-b-c)}{ad-bc}.
\end{align*}
Similarly,
\[ q = \frac{bd(a+d-b-c)}{ad-bc}. \]
It is now obvious that $p$ and $q$ have the same magnitude.
\begin{remark*}
One possible trick one might use to compute $p$ is to compute the coordinates
of the points $A', C' \in (ABCD)$ such that $AA'$ and $CC'$ are tangent
to $(ADE)$ and $(BCE)$ respectively, and then use the chords intersection formula.
If one does this, one gets $a' = ac/b$ and $c' = ac/d$.
At this point, one can simply recognize that $A'$ and $C'$
are the reflection of $B$ and $D$ over the perpendicular bisector of $AC$,
reflect everything over said perpendicular bisector,
and suddenly realize that one has solved the problem synthetically.
\end{remark*}
\paragraph{Solution 4 by linearity (Noah Walsh).}
If $AE = DE$ the problem is true by symmetry, so we assume $AE \neq DE$.
Fix $A$, $D$, and $E$, and move $B$ linearly along line $DE$.
By e.g.\ Reim's theorem, $C$ moves linearly as well.
How do we compute $O$? It lies on the perpendicular bisector of $AD$, which is fixed.
It also lies on the perpendicular bisector of $BC$,
which is parallel to a fixed line, and passes through the midpoint of $BC$, which moves linearly.
Therefore, $O$ moves linearly as well.
Point $P$ is the intersection of the tangent to $(ADE)$ at $A$, which is fixed,
and the tangent to $(BCE)$ at $C$, which moves linearly, and therefore is linear.
Similarly, $Q$ moves linearly.
Therefore, to verify that
$\ray{OP} \times \ray{OP} = \ray{OQ} \times \ray{OQ}$,
it suffices to check three cases.
The two cases where $EA = EB$ are trivial by symmetry.
We can also check that
$\lim_{B \to \infty_{DE}} \frac{\ray{OP}\times\ray{OP}}{\ray{OQ}\times\ray{OQ}} = 1$.
Indeed, obviously
$\lim_{B \to \infty_{DE}} \frac{|OP|}{|AP|} = \lim_{B \to \infty_{DE}} \frac{|OQ|}{|DQ|} = 1$.
In addition,
\begin{align*}
\frac{dAP}{dDQ}
&= \frac{dAP}{dAC} \times \frac{dAC}{dBD} \times \frac{dBD}{dBQ} \\
&= \frac{\sin \angle ACP}{\sin \angle APC}
\times \frac{dEC}{dEB} \times \frac{\sin \angle BQD}{\sin \angle BDQ} \\
&= \frac{\sin \angle ACP}{\sin (\angle ACP + \angle CAP)}
\times \frac{\sin \angle EBC}{\sin \angle ECB}
\times \frac{\sin (\angle BDQ + \angle DBQ)}{\sin \angle BDQ} \\
&= \frac{\sin\angle BCE}{\sin(\angle BCE + \angle ADE)}
\times \frac{\sin\angle DAE}{\sin\angle ADE}
\times \frac{\sin(\angle DAE + \angle ECB)}{\sin\angle EAD} \\
&=\frac{\sin(\angle DAE + \angle ECB)}{\sin(\angle BCE + \angle ADE)} \\
&= 1.
\end{align*}
It follows that $\lim_{B \to \infty_{DE}}\frac{|AP|}{|DQ|} = 1$.
Therefore,
\begin{align*}
\lim_{B \to \infty_{DE}}\frac{|OP|}{|OQ|}
&= \lim_{B \to \infty_{DE}}\frac{|OP|}{|AP|}
\times \lim_{B \to \infty_{DE}}\frac{|AP|}{|DQ|}
\times \lim_{B \to \infty_{DE}} \frac{|DQ|}{|OQ|}\\
&= 1,
\end{align*}
which completes the $B \to \infty_{DE}$ case, and we are done.
\pagebreak
\subsection{TSTST 2024/5, proposed by Holden Mui}
\textsl{Available online at \url{https://aops.com/community/p31007010}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
For a positive integer $k$,
let $s(k)$ denote the number of $1$s in the binary representation of $k$.
Prove that for any positive integer $n$,
\[ \sum_{i=1}^{n}(-1)^{s(3i)} > 0. \]
\end{mdframed}
\paragraph{Solution 1.}
Given a set of positive integers $S$, define
\begin{align*}
f(S) = \sum_{k\in S}(-1)^{s(k)}.
\end{align*}
We also define
\begin{align*}
S_{\mathrm{even}} &= \{k\in S \mid k\text{ is even}\} \\
S_{\mathrm{odd}} &= \{k\in S \mid k\text{ is odd}\}
\end{align*}
and apply functions on sets pointwise, e.g.
\[ \frac{S-1}{2} = \left\{\frac{k-1}{2}\mid k \in S\right\}. \]
The problem follows from the first bullet of the following claim.
\begin{claim*}
For every positive integer $n$,
\begin{itemize}
\item $f(\{3, 6, \dots, 3n\}) > 0$
\item $f(\{1, 4, \dots, 3n-2\}) < 0$
\item $f(\{2, 5, \dots, 3n-1\}) \leq 0$
\end{itemize}
\end{claim*}
\begin{proof}
Induct on $n$. The base case $n=1$ is easy to check.
\begin{itemize}
\item For $S = \{3, 6, \dots, 3n\}$,
\begin{align*}
f(S) &= f(S_{\mathrm{even}}) + f(S_{\mathrm{odd}}) \\
&= f(S_{\mathrm{even}}/2) - f((S_{\mathrm{odd}}-1)/2) > 0
\end{align*}
since the elements of $S_{\mathrm{even}}/2$ are $0 \bmod 3$
and the elements of $(S_{\mathrm{odd}}-1)/2$ are $1 \bmod 3$.
\item For $S = \{1, 4, \dots, 3n-2\}$,
\begin{align*}
f(S) &= f(S_{\mathrm{even}}) + f(S_{\mathrm{odd}}) \\
&= f(S_{\mathrm{even}}/2) - f((S_{\mathrm{odd}}-1)/2) < 0
\end{align*}
since the elements of $S_{\mathrm{even}}/2$ are $2 \bmod 3$
and the elements of $(S_{\mathrm{odd}}-1)/2$ are $0 \bmod 3$.
(Note that $(S_{\mathrm{odd}}-1)/2$ has multiples of $3$ starting at $0$ rather than $3$,
but this is fine because $f(\{3, \dotsc, 3n\}) > 0$ clearly implies $f(\{0, \dotsc, 3n\}) > 0$ as well.)
\item For $S= \{2, 5, \dots, 3n-1\}$, there are two cases.
\begin{itemize}
\item Case 1: $2^{2k-1} \leq 3n-1 < 2^{2k}$. Define
\begin{align*}
S_{\mathrm{small}} &= \{s \in S \mid s < 2^{2k-1}\} \\
S_{\mathrm{big}} &= \{s \in S \mid s \geq 2^{2k-1}\}.
\end{align*}
Then
\begin{align*}
f(S) &= f(S_{\mathrm{small}}) + f(S_{\mathrm{big}}) \\
&= f(S_{\mathrm{small}}) - f(S_{\mathrm{big}} - 2^{2k-1}) < 0
\end{align*}
since $S_{\mathrm{big}} - 2^{2k-1} = \{0, \dots, 3n-1-2^{2k-1}\}$
consists of a prefix of the $0\pmod 3$ positive integers in addition to $0$.
\item Case 2: $2^{2k} < 3n-1 < 2^{2k+1}$.
Note that if $a+b = 2^{2k+1}-1$, then $f(\{a, b\}) = 0$.
If we use this to cancel out all pairs of numbers in $S$ which add to $2^{2k+1}-1$,
then we find
\[ f(S) = f(\{2, 5, \dots, 2^{2k+1}-3n-2\}) \leq 0. \]
\end{itemize}
\end{itemize}
This completes the induction.
\end{proof}
\paragraph{Solution 2.}
Let
\[ f(n) = \sum_{i=0}^n (-1)^{s(3i)}, \qquad g(n) = \sum_{i=0}^n (-1)^{s(i)}. \]
Note that the problem is equivalent to showing $f(n) \geq 2$ for all $n \geq 1$.
\begin{lemma*}
$|g(n)| \leq 1$ for all $n$.
\end{lemma*}
\begin{proof}
Note that $s(2i+1) = -s(2i)$, so $g(2n+1) = 0$ and $g(2n) = (-1)^{s(2n)}$ by pairing terms.
\end{proof}
We will now prove that $f(n)\geq 2$ for all $n\geq 1$ by strong induction.
We can manually verify $n\leq 5$ as a base case.
For the inductive step, let $m = \lfloor\frac{3n-3}{4}\rfloor$ so that $4m+3\leq n$.
Let $S = \{0, 3, \dots, 3n\}$.
Given $0\leq k\leq m$, we can append two digits to the binary representation of $k$
(equivalently, $4k+r$ for $0\leq r < 4$) to get a number in $S$.
If $k$ is a multiple of $3$, we can append $00$ or $11$.
Otherwise, we can append one of $01$ or $10$ depending on $k\pmod{3}$.
Almost all elements of $S$ can be covered uniquely in this way,
except for at most one missing element.
Note that appending $00$ or $11$ will preserve the parity of the number of $1$s
while appending $01$ or $10$ will change the parity. Therefore we can write
\[
f(n)\geq 2\sum_{\substack{0\leq i\leq m \\ i\equiv 0\pmod{3}}} (-1)^{s(i)}
- \sum_{\substack{0\leq i\leq m \\ i\not\equiv 0\pmod{3}}} (-1)^{s(i)} - 1\]
(the $-1$ is to account for the possible missing element). Let
\[
x = \sum_{\substack{0\leq i\leq m \\ i\equiv 0\pmod{3}}} (-1)^{s(i)},
\qquad y = \sum_{\substack{0\leq i\leq m \\ i\not\equiv 0\pmod{3}}} (-1)^{s(i)}.
\]
According to the lemma, $|x+y|\leq 1$. By the inductive hypothesis, $x\geq 2$. Therefore
\[ f(n)\geq 2x-y-1 = 3x - (x+y) - 1\geq 6-1-1 > 2 \]
as desired.
\paragraph{Solution 3.}
For $r \in \{0, 1, 2\}$, define
\[ S_r(a,b) = \sum_{\substack{i\in [a,b) \\ i\equiv r \bmod 3}} (-1)^{s(i)}, \]
where $s(i)$ denotes the number of 1s in $i$'s binary representation.
The problem is equivalent to proving $S_0(0, 3n+1) > 1$ for all $n \geq 1$.
\begin{lemma*}
For any integer $d$, $S_r(0, 2^d)$ is given by:
\[
\renewcommand{\arraystretch}{1.3}
\begin{array}{c|ccc}
d & S_0(0, 2^d) & S_1(0, 2^d) & S_2(0, 2^d) \\ \hline
\text{d odd} & 3^{\frac{d-1}{2}} & -3^{\frac{d-1}{2}} & 0 \\
\text{d even} & 2 \cdot 3^{\frac{d-2}{2}} & -3^{\frac{d-2}{2}} & -3^{\frac{d-2}{2}}
\end{array}
\]
\end{lemma*}
\begin{proof}
Induction with $d \le 2$ being clear. For the inductive step, observe that
\begin{align*}
S_0(0, 2^d) &= S_0(0, 2^{d-1}) + S_0(2^{d-1}, 2^d) = S_0(0, 2^{d-1}) - S_{2^{d-1}}(0, 2^{d-1}) \\
S_1(0, 2^d) &= S_1(0, 2^{d-1}) + S_1(2^{d-1}, 2^d) = S_1(0, 2^{d-1}) - S_{1+2^{d-1}}(0, 2^{d-1}) \\
S_2(0, 2^d) &= S_2(0, 2^{d-1}) + S_2(2^{d-1}, 2^d) = S_2(0, 2^{d-1}) - S_{2+2^{d-1}}(0, 2^{d-1}).
\end{align*}
Using
\[ 2^{d-1} \equiv \begin{cases}
1 \bmod 3 & \text{$d$ odd} \\
2 \bmod 3 & \text{$d$ even}
\end{cases} \]
and applying the inductive hypothesis gives the desired result.
\end{proof}
This proves the problem for powers of $2$.
To prove the problem for general $n$, split $[0, 3n+1)$ into blocks
\[
[0, 3n+1) = [0, 2^{d_1}) \sqcup [2^{d_1}, 2^{d_1} + 2^{d_2})
\sqcup [2^{d_1} + 2^{d_2}, 2^{d_1} + 2^{d_2} + 2^{d_3}), \dots\]
whose lengths are decreasing powers of $2$.
By the lemma,
\begin{align*}
S_0(0, 2^{d_1})
&\geq \begin{cases}
3^{\frac{d_1-1}{2}} & \text{$d_1$ odd} \\
2 \cdot 3^{\frac{d_1-2}{2}} & \text{$d_1$ even}
\end{cases} \\
S_0(2^{d_1}, 2^{d_1}+2^{d_2}) &= -S_{2^{d_1}}(0, 2^{d_2}) \geq 0
\end{align*}
and for all $i$,
\begin{align*}
S_0(2^{d_1} + \dotsb + 2^{d_{i-1}}, 2^{d_1} + \dotsb + 2^{d_{i}})
&= (-1)^{i-1}S_{2^{d_1} + \dotsb + 2^{d_{i-1}}}(0, 2^{d_i}) \\
&\geq \begin{cases}
-2 \cdot 3^{\frac{d_i-2}{2}} & \text{$d_i$ even} \\
-1 \cdot 3^{\frac{d_i-1}{2}} & \text{$d_i$ odd}.
\end{cases}
\end{align*}
Let $D= d_1$; assume $D \geq 4$ since checking $D \in \{1, 2, 3\}$ is easy.
Summing over all intervals gives
\[
S_0(0, 3n+1) \geq 2 \cdot 3^{\frac{D-2}{2}} + 0 - \left(2 \cdot 3^{\frac{D-4}{2}}
+ 3^{\frac{D-4}{2}} + 2 \cdot 3^{\frac{D-6}{2}} + 3^{\frac{D-6}{2}} + \dotsb\right)
= 3^{\frac{D-2}{2}} > 1
\]
when $D$ is even, and
\[
S_0(0, 3n+1) \geq 3^{\frac{D-1}{2}} + 0 - \left(3^{\frac{D-3}{2}} + 2 \cdot 3^{\frac{D-5}{2}}
+ 3^{\frac{D-5}{2}} + 2 \cdot 3^{\frac{D-7}{2}} + \dotsb\right)
= \tfrac{1}{2} \cdot 3^{\frac{D-3}{2}} > 1
\]
when $D$ is odd.
\begin{remark*}
The following Python code calculates $\sum_{i=0}^{n}(-1)^{s(3i)}$ in $O(\log n)$ time
using digit DP (and in $O(K \log n)$ time if $3$ is replaced by $K$):
\begin{lstlisting}[language=Python,numbers=none]
import functools
K = 3
def sgn(n: int) -> int:
return -1 if bin(n).count('1') % 2 else 1
@functools.lru_cache(maxsize=None)
def f(n: int) -> list[int]:
# Returns an array of size K where arr[i] = sum of sgn(j) over 0 <= j <= n with j % K = i
ans = [0] * K
if n == 0:
ans[0] += 1
return ans
x = f(n // 2)
for i in range(K):
ans[2 * i % K] += x[i]
ans[(2 * i + 1) % K] -= x[i]
if n % 2 == 0:
ans[(n + 1) % K] -= sgn(n + 1)
return ans
\end{lstlisting}
\end{remark*}
\begin{remark*}
Define
\[f(n) = \sum_{i=0}^{\lfloor n/3\rfloor} (-1)^{s(3i)}.\]
Then there exist constants $0 < c_1 < c_2$ such that
\[
\liminf_{n\to\infty} \frac{f(n)}{n^{\log_4(3)}} = c_1,
\qquad \limsup_{n\to\infty}\frac{f(n)}{n^{\log_4(3)}} = c_2.
\]
The upper constant is $c_2 = \frac{2}{3}$, achieved when $n$ is a power of $4$.
\end{remark*}
\pagebreak
\subsection{TSTST 2024/6, proposed by Jaedon Whyte}
\textsl{Available online at \url{https://aops.com/community/p31007016}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Determine whether there exists a function $f \colon \ZZ_{> 0} \to \ZZ_{>0}$
such that for all positive integers $m$ and $n$,
\[ f(m+nf(m))=f(n)^m+2024! \cdot m. \]
\end{mdframed}
The answer is no. Let $P(m,n)$ denote the given FE.
\paragraph{Solution 1 (Gopal Goel).}
Suppose there was a function $f$, and let $r=f(1)$. Note that $P(1,n)$ gives
\[ f(1+rn) = f(n)+2024!. \]
Iterating this result gives
\[ f(1+r+\dotsb+r^k) = r+k\cdot 2024! \]
for all $k \in \ZZ_{\ge 0}$.
If $r=1$, this implies $f(k+1) = 1 + k\cdot 2024!$, which isn't a valid solution, so $r\ge 2$.
Let $m = 1 + r + \dotsb + r^{r^2(r-1)}$. Note that
\[ 1+r+\dotsb+r^k = m + nf(m) \iff \frac{r^{k+1}-r^{r^2(r-1)+1}}{r-1} = n[r+r^2(r-1)2024!]. \]
This has a positive integer solution for $n$ as long as $k$ is sufficiently large in terms of $r$ and
\[ k\equiv r^2(r-1) \pmod{\phi(1+r(r-1) \cdot 2024!)}. \]
For such $k$, $P(m,n)$ implies
\[ r + k\cdot 2024! = f(n)^m + 2024!\cdot m. \]
In particular, $r + (k-m)\cdot 2024!$ is a perfect $m$th power.
This has to be true for all $k$ sufficiently large in an arithmetic progression,
which is clearly impossible, as desired.
\paragraph{Solution 2 (Carl Schildkraut).}
As in the previous solution, we have
\[ f(1+r+\dotsb+r^k) = r+k\cdot 2024! \]
for all $k \in \ZZ_{\ge 0}$, where $r=f(1)\ge 2$.
\begin{claim*}
We have $f(a)\ge\frac{2^a-1}{2024!\cdot a}$ for $a\in\mathbb{Z}_{>0}$.
\end{claim*}
\begin{proof}
Let $c = a+af(a)$, $b = f(c)+a$, and $d=f(a)$, so that
\[ a + bf(a) = a + af(a) + f(a)f(c) = c + df(c). \]
Comparing $P(a,b)$ and $P(c,d)$ tells us
\[ f(b)^a + 2024!\cdot a = f(d)^c + 2024!\cdot c, \]
so
\[ f(b)^a - \left(f(d)^{1+f(a)}\right)^a = 2024!\cdot af(a). \]
Since the left side of the above equation is positive,
it must be at least $2^a-1$, which implies the claim.
\end{proof}
Plugging in $a=1+r+\dotsb+r^k$ into the above claim immediately
gives the desired contradiction, for sufficiently large $k$.
\paragraph{Solution 3 (students).}
If $f$ existed, then for any $k \in \ZZ_{>0}$ we would have
\begin{align*}
f(f(3))^{3+kf(3)} + 2024!(3+kf(3)) &= f(3+kf(3)+f(3)f(3+kf(3))) \\
&= f(3+(k+f(3+kf(3))f(3))) \\
&= f(k+f(3+f(3)k))^3 + 2024!\cdot 3.
\end{align*}
Choosing $k=27(2024!)^2f(3)^2$ gives
\[ f\left(k+f(3+f(3)k)\right)^3 = \left(f(f(3))^{1+9(2024!)^2f(3)^3}\right)^3+ (3\cdot 2024!f(3))^{3} \]
which contradicts Fermat's last theorem (no two perfect cubes may sum to a perfect cube).
Hence $f$ cannot exist.
\pagebreak
\section{Solutions to Day 3}
\subsection{TSTST 2024/7, proposed by Merlijn Staps}
\textsl{Available online at \url{https://aops.com/community/p31007023}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
An infinite sequence $a_1$, $a_2$, $a_3$, \dots\ of real numbers satisfies
\[ a_{2n-1} + a_{2n} > a_{2n+1} + a_{2n+2} \qquad
\mbox{and} \qquad a_{2n} + a_{2n+1} < a_{2n+2} + a_{2n+3} \]
for every positive integer $n$.
Prove that there exists a real number $C$ such
that $a_{n} a_{n+1} < C$ for every positive integer $n$.
\end{mdframed}
It suffices to solve the problem for sufficiently large $n$.
Let $d_n = (-1)^{n-1}(a_{n+2}-a_n)$.
The assertion simply says that $d_1,d_2,\dotsc$ is strictly increasing.
We consider the following cases.
\begin{itemize}
\ii Suppose that $d_k > 0$ for some $k$. Then,
\[ a_{2n+1} = a_1 + (d_1+d_3+\dotsb+d_{2n-1}) \]
clearly diverges to $+\infty$, and
\[ a_{2n} = a_2 - (d_2+d_4+\dotsb+d_{2n-2}) \]
clearly diverges to $-\infty$, so taking $C=0$ works.
\ii Now assume that $d_k \le 0$ for all $k$.
This implies that $(a_{2n+1})_{n\ge 0}$ is weakly decreasing
and $(a_{2n})_{n\ge 1}$ is weakly increasing.
Adding the two expressions above together, we see that
\[ d_1 + a_1 + a_2 < a_{2n} + a_{2n+1} < a_1 + a_2. \]
Since $(a_{2n+1})_{n\ge 0}$ is weakly decreasing,
it either diverges to $-\infty$ or has a finite limit.
Similarly, $(a_{2n})_{n\ge 1}$ either diverges to $+\infty$ or has a finite limit.
\begin{itemize}
\ii If $(a_{2n+1})_{n\ge 0}$ diverges to $-\infty$,
then the first inequality above implies
that $(a_{2n})_{n\ge 1}$ must diverge to $+\infty$,
in which case $C=0$ works.
\ii If $(a_{2n})_{n\ge 1}$ diverges to $+\infty$,
then the second inequality implies that $(a_{2n+1})_{n\ge 0}$
must diverge to $-\infty$, so again $C=0$ works.
\ii Finally assume that both $\lim_{n\to\infty} a_{2n+1}$ and $\lim_{n\to\infty} a_{2n}$ exist,
so the limit $L = \lim_{n\to\infty} a_{2n}a_{2n+1}$ also exists.
The result follows taking $C > L$.
\end{itemize}
\end{itemize}
\pagebreak
\subsection{TSTST 2024/8, proposed by Michael Ren}
\textsl{Available online at \url{https://aops.com/community/p31007038}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $ABC$ be a scalene triangle,
and let $D$ be a point on side $BC$ satisfying $\angle BAD=\angle DAC$.
Suppose that $X$ and $Y$ are points inside $ABC$
such that triangles $ABX$ and $ACY$ are similar and quadrilaterals $ACDX$ and $ABDY$ are cyclic.
Let lines $BX$ and $CY$ meet at $S$ and lines $BY$ and $CX$ meet at $T$.
Prove that lines $DS$ and $AT$ are parallel.
\end{mdframed}
\paragraph{Solution by characterizing $\boldsymbol X$ and $\boldsymbol Y$.}
We first state an important property of $X$ and $Y$.
\begin{claim*}
Points $X$ and $Y$ are isogonal conjugates with respect to $\triangle ABC$.
\end{claim*}
\begin{center}
\begin{asy}
unitsize(120);
pair A = dir(125);
pair C = dir(-35);
pair B = dir(-145);
pair D = extension(A,incenter(A,B,C),B,C);
pair gammaB = extension(0, B+C, B, -A);
pair gammaC = extension(0, B+C, C, -A);
pair omegaB = circumcenter(A,B,D);
pair omegaC = circumcenter(A,C,D);
pair Y = 2*foot(B,omegaB,gammaC) - B;
pair X = 2*foot(C,omegaC,gammaB) - C;
pair E = 2*foot(gammaB, A, C) - C;
pair F = extension(B,E,A,D);
pair S = extension(B,X,C,Y);
pair T = extension(B,Y,C,X);
pair Cp = 2*foot(omegaC,B,X)-X;
pair Bp = 2*foot(omegaB,C,Y)-Y;
draw(A--B--C--A, red);
draw(A--D, red);
draw(circumcircle(A,B,D),blue);
draw(circumcircle(A,C,D),blue);
draw(B--E,dotted);
draw(circumcircle(A,E,F),dotted);
draw(B--Y,dashed+heavygreen);
draw(C--X,dashed+heavygreen);
draw(B--Cp,dashed+heavygreen);
draw(C--Bp,dashed+heavygreen);
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$D$", D, dir(-90));
dot("$X$", X, dir(X)*dir(10));
dot("$Y$", Y, 1.5*dir(20));
dot("$E$", E, dir(E));
dot("$F$", F, 1.5*dir(150));
dot("$S$", S, 1.5*dir(100));
dot("$T$", T, dir(T));
dot("$B'$", Bp, dir(Bp));
dot("$C'$", Cp, dir(Cp));
\end{asy}
\end{center}
Here are two proofs of the claim.
\begin{proof}[First proof of claim by Maxim Li]
We prove an equivalent statement that $S$ and $T$ are isogonal conjugates
with respect to $\triangle ABC$.
First, we note that $\angle YBC = \angle YAD = \angle XAD = \angle XCB$, so $BT=TC$.
Now, let $T'$ be the isogonal conjugate of $S$ w.r.t. $\triangle ABC$.
Since $\angle ABS = \angle ACS$, it follows that $T'B=T'C$.
Thus, both $T$ and $T'$ lies on perpendicular bisector of $BC$.
Moreover, since $AX$ and $AY$ are isogonal with respect to $\angle BAC$,
by DDIT on point $A$ and $BXCY$, we get that
$AS$ and $AT$ are isogonal with respect to $\angle BAC$.
Hence, $A, T, T'$ are collinear.
Since $\triangle ABC$ is scalene, combining this with the previous
paragraph gives $T=T'$, or $S$ and $T$ are isogonal conjugates.
\end{proof}
\begin{proof}[A second different proof of the claim.]
Let $\gamma_B$ be the circle through $B$ and $C$ tangent to $AB$,
and define $\gamma_C$ similarly.
We claim that $X \in \gamma_B$ and $Y \in \gamma_C$.
Let $E$ be the second intersection of $\gamma_B$ with $AC$,
and let $F$ be the intersection of $BE$ and $AD$.
Consider the transformation $\tau$ that is the
composition of a reflection across $AD$ and a homothety at $A$ with ratio $\frac{AB}{AC}$.
Note that $\tau$ maps $Y \mapsto X$, $B \mapsto E$, and $D \mapsto F$.
Thus, $X$ lies on $\tau(\odot(ABD)) = \odot(AEF)$,
so $X$ is the second intersection of $\odot(AEF)$ and $\odot(ADC)$,
i.e.\ it is the Miquel point of quadrilateral $CDFE$.
Thus, $X$ lies on $\odot(BEC) = \gamma_B$, as claimed.
Finally, the main claim follows from $\angle BCX = \angle ABX = \angle ACY$.
\end{proof}
Here are two ways to finish after the claim.
\subparagraph{Finish with isosceles trapezoid.}
We compute
\[\angle AXB = 360\dg-\angle BXC-\angle CXA = 360\dg-\angle BEC-\angle CDA
= 180\dg-\frac{\angle A}{2}.\]
Thus, if $BX$ meets $\odot(ACD)$ again at $C'$, then
\[ \angle ADC' = \angle AXC' = \frac{\angle A}2 = \angle CAD, \]
so $ADCC'$ is an isosceles trapezoid.
Similarly, if $CY$ meets $\odot(ABD)$ again at $B'$, then $ADBB'$ is an isosceles trapezoid.
Hence, $BCC'B'$ is an isosceles trapezoid whose diagonals meet at $S$, so we have that $SA=SD$.
However, by the claim, $S$ and $T$ are isogonal conjugates in $ABC$. Thus,
\[ \angle ADS = \angle SAD = \angle DAT, \]
which completes the proof.
\subparagraph{Finish with angle chasing (Pitchayut Saengrungkongka).}
By the claim, let $\angle DAX = \angle DAY = \angle ABX = \angle ACY = \theta$.
Then,
\begin{align*}
\angle XSY &= \angle A + 2\theta \\
\angle XDY &= \angle BDY + \angle CDX - 180\dg = 180\dg - (\angle BAY + \angle CAX) \\
&= 180\dg - (\angle A + 2\theta),
\end{align*}
so $XSYD$ is cyclic. Moreover,
\[ \angle XTY = 180\dg - \angle YBC - \angle XCB
= 180\dg - 2\theta = 180\dg - \angle XAY, \]
so $AXTY$ is also cyclic. Finally,
\begin{align*}
\dang(AT,AX)
&= \dang TYX = \dang BYD + \dang DYX \\
&= \dang BAD + \dang DSX = \dang BXA + \dang DSX \\
&= \dang(DS,AX).
\end{align*}
\paragraph{Solution 2 (Ruben Carpenter).}
Let $M$ be the midpoint of $BC$, and $S'$, $T'$ the reflections of $S$, $T$ over $M$.
In what follows, DDIT is short for the dual of Desargues' involution theorem.
\begin{claim*}
$S'$ lies on $AT$.
\end{claim*}
\begin{proof}
From $\triangle ABX \overset{-}{\sim} \triangle AYC$,
reflection along the angle bisector of $\angle ABC$ is an involution on the pencil of
lines through $A$ with pairs $(AB, AC)$, $(AX, AY)$ and $(A\infty_{BS}, A\infty_{CS})$.
By DDIT from $A$ onto complete quadrilateral $XYSTBC$, $AS$ is sent to $AT$.
By DDIT from $A$ onto $BC\infty_{BX}\infty_{CY}SS'$, $(AS, AS')$
is also an involutive pair, so $AS' \equiv AT$.
\end{proof}
\begin{claim*}
$T'$ lies on $DS$.
\end{claim*}
\begin{proof}
Using the circles $(ACDX)$, $(ABDY)$ we obtain
\[\angle BDT=\angle DAY=\angle DAC-\angle YAC = \angle BAD-\angle BAX=\angle XAD=\angle TCB,\]
so $T$ lies on the perpendicular bisector of $BC$. Furthermore
\[\angle CDY=\angle BAY=\angle XAC=\angle XDB,\]
so by DDIT from $D$ onto $XSYTBC$ shows $\angle CDT = \angle SDB$.
The conclusion follows.
\end{proof}
Finally, since $STS'T'$ is a parallelogram we immediately have $DS \parallel AT$.
\begin{remark*}
This problem was discovered by taking a degenerate case of IMO 2018/6 in which
three of the vertices of the quadrilateral are collinear. Nevertheless, this
origin is very obscured in the problem statement and does not seem to help with
the solution at all. The original statement asked to show that the midpoints of
$AD$, $BC$, and $XY$ are collinear. However, it was found that this is a
straightforward consequence of a high-powered result about isogonal conjugates,
so the statement was changed.
\end{remark*}
\pagebreak
\subsection{TSTST 2024/9}
\textsl{Available online at \url{https://aops.com/community/p31007051}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $n \ge 2$ be a fixed integer. The cells of an $n \times n$ table are
filled with the integers from $1$ to $n^2$ with each number appearing exactly once.
Let $N$ be the number of unordered quadruples of cells on this board
which form an axis-aligned rectangle,
with the two smaller integers being on opposite vertices of this rectangle.
Find the largest possible value of $N$.
\end{mdframed}
The largest possible value of $N$ is $\tfrac1{12}n^2(n^2-1)$.
Call these rectangles \emph{wobbly}.
We defer the construction until the proof is complete,
since the proof suggests the construction.
\paragraph{Proof of bound.}
Call a triple of integers $(a,b,c)$ an \emph{elbow}
if $a$ and $b$ are in the same row, $b$ and $c$ are in the same column,
and $a < b > c$.
Observe that the wobbly rectangles are exactly the ones with $2$ elbows.
\begin{claim*}
Every axis-aligned rectangle has at least $1$ elbow.
\end{claim*}
\begin{proof}
The smallest integer in any rectangle is the center of an elbow.
\end{proof}
\begin{remark*}
In fact, it is true that any rectangle must have exactly $1$ or $2$ elbows.
However, this fact is not needed in the proof.
\end{remark*}
Let $E$ be the number of elbows and $M$ be the number of non-wobbly rectangles.
Then, the number of elbows is at least $M + 2N = \tbinom n2^2 + N$, so
\[ E \ge \binom n2^2 + N \iff N \le E - \binom n2^2. \]
To this end, we will provide an upper bound on $E$.
For each cell $c$, define:
\begin{itemize}
\ii $f(c)$ to be the number of cells in $c$'s row which are smaller than $c$, and
\ii $g(c)$ to be the number of cells in $c$'s column which are smaller than $c$.
\end{itemize}
Then, the number of elbows centered at $c$ equals $f(c) g(c)$.
Thus, the number of elbows satisfies
\begin{align*}
E &= \sum_c f(c) g(c) \\
&\le \sum_c \frac12 \big[f(c)^2 + g(c)^2] \\
&= n(0^2 + \dots + (n-1)^2) \\
&= \frac{n^2(n-1)(2n-1)}{6}.
\end{align*}
It follows that the number of wobbly rectangles satisfies
\begin{align*}
N &\le E - \binom n2^2 \\
&\le \frac{n^2(n-1)(2n-1)}6 - \frac{n^2(n-1)^2}4 \\
&= \frac{n^2(n^2-1)}{12}
\end{align*}
as desired.
\paragraph{Construction.}
From the proof above, equality holds if and only if $f(c) = g(c)$ everywhere.
Select any $n \times n$ Latin square on symbols $0$, \dots, $n-1$,
and replace the $n$ copies of symbol $k$ with the integers $kn + 1$, \dots, $kn + n$ in some order.
This construction is valid, because for each cell $c$,
$f(c)$ and $g(c)$ both equal the symbol originally placed in $c$.
Here is an example for $n = 6$.
The left grid is the Latin square,
and the right grid is one possible table that can be derived from it.
\begin{center}
\begin{asy}
unitsize(24);
defaultpen(fontsize(14pt));
pen[] colors = {palered, mediumyellow, lightgreen, lightcyan, paleblue, pink};
int n = colors.length;
transform t0 = shift(-0.5, -0.5);
transform t1 = scale(1, -1);
transform t2 = shift(n+2, 0) * t1;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
int k = (i-j) % n;
fill(t1 * t0 * shift(i, j) * unitsquare, colors[k]);
fill(t2 * t0 * shift(i, j) * unitsquare, colors[k]);
label((string) k, t1 * (i, j));
label((string) (n*k + j + 1), t2 * (i, j));
}
for (int i = 0; i <= n; ++i) {
draw(t1 * t0 * ((i, 0)--(i, n) ^^ (0, i)--(n, i)), gray(0.6));
draw(t2 * t0 * ((i, 0)--(i, n) ^^ (0, i)--(n, i)), gray(0.6));
}
\end{asy}
\end{center}
\begin{remark*}[Structure of optimal tables]
In fact, any optimal table must lead to a Latin square in a similar way,
by reversing the above idea: replace each cell $c$ with $f(c) = g(c)$.
This suggests how to construct all optimal tables:
choose any Latin square on $0$, \dots, $n-1$,
and fill in the cells so that the relative order of cells in every row and column is preserved.
\end{remark*}
\begin{remark*}
If the grid is filled out in a random order,
the expected number of wobbly rectangles is $\frac{1}{12}n^2(n-1)^2$.
This is asymptotically equal to the maximum value.
\end{remark*}
\pagebreak
\end{document}