\documentclass[11pt]{scrartcl}
\usepackage[sexy]{evan}
\ihead{\footnotesize\textbf{\thetitle}}
\ohead{\footnotesize\theauthor}
\begin{document}
\title{USA TSTST 2019 Solutions}
\subtitle{United States of America --- TST Selection Test}
\author{Ankan Bhattacharya and Evan Chen}
\date{61\ts{st} IMO 2020 Russia and 9\ts{th} EGMO 2020 Netherlands}
\maketitle
\tableofcontents
\newpage
\addtocounter{section}{-1}
\section{Problems}
\begin{enumerate}[\bfseries 1.]
\item %% Problem 1
\def\di{\mathbin{\diamondsuit}}
Find all binary operations $\di \colon \RR_{>0} \times \RR_{>0} \to \RR_{>0}$
(meaning $\di$ takes pairs of
positive real numbers to positive real numbers)
such that for any real numbers $a,b,c > 0$,
\begin{itemize}
\ii the equation $a \di (b \di c) = (a \di b) \cdot c$ holds; and
\ii if $a \ge 1$ then $a \di a \ge 1$.
\end{itemize}
\item %% Problem 2
Let $ABC$ be an acute triangle with circumcircle $\Omega$
and orthocenter $H$.
Points $D$ and $E$ lie on segments $AB$ and $AC$
respectively, such that $AD = AE$.
The lines through $B$ and $C$ parallel to $\ol{DE}$
intersect $\Omega$ again at $P$ and $Q$, respectively.
Denote by $\omega$ the circumcircle of $\triangle ADE$.
\begin{enumerate}[(a)]
\ii Show that lines $PE$ and $QD$ meet on $\omega$.
\ii Prove that if $\omega$ passes through $H$,
then lines $PD$ and $QE$ meet on $\omega$ as well.
\end{enumerate}
\item %% Problem 3
On an infinite square grid we place finitely many \emph{cars},
which each occupy a single cell and face in one of the four cardinal directions.
Cars may never occupy the same cell.
It is given that the cell immediately in front of each car is empty,
and moreover no two cars face towards each other
(no right-facing car is to the left of a left-facing car within a row, etc.).
In a \emph{move}, one chooses a car and shifts it one cell forward to a vacant cell.
Prove that there exists an infinite sequence of valid moves
using each car infinitely many times.
\item %% Problem 4
Consider coins with positive real denominations not exceeding $1$.
Find the smallest $C>0$ such that the following holds:
if we are given any $100$ such coins
with total value $50$, then we can
always split them into two stacks
of $50$ coins each such that the absolute difference
between the total values of the two stacks is at most $C$.
\item %% Problem 5
Let $ABC$ be an acute triangle with orthocenter $H$ and circumcircle $\Gamma$.
A line through $H$ intersects segments $AB$ and $AC$ at $E$ and $F$, respectively.
Let $K$ be the circumcenter of $\triangle AEF$,
and suppose line $AK$ intersects $\Gamma$ again at a point $D$.
Prove that line $HK$ and the line through $D$
perpendicular to $\ol{BC}$ meet on $\Gamma$.
\item %% Problem 6
Suppose $P$ is a polynomial with integer coefficients
such that for every positive integer $n$,
the sum of the decimal digits of $|P(n)|$
is not a Fibonacci number.
Must $P$ be constant?
\item %% Problem 7
Let $f \colon \ZZ \to \{1, 2, \dots, 10^{100}\}$
be a function satisfying
\[ \gcd(f(x), f(y)) = \gcd(f(x), x-y) \]
for all integers $x$ and $y$.
Show that there exist positive integers $m$ and $n$ such that
$f(x) = \gcd(m + x, n)$ for all integers $x$.
\item %% Problem 8
Let $\mathcal{S}$ be a set of $16$ points in the plane, no three collinear.
Let $\chi(\mathcal{S})$ denote the number of ways to
draw $8$ line segments with endpoints in $\mathcal{S}$,
such that no two drawn segments intersect, even at endpoints.
Find the smallest possible value of $\chi(\mathcal{S})$
across all such $\mathcal{S}$.
\item %% Problem 9
Let $ABC$ be a triangle with incenter $I$.
Points $K$ and $L$ are chosen on segment $BC$
such that the incircles of $\triangle ABK$ and $\triangle ABL$ are tangent at $P$,
and the incircles of $\triangle ACK$ and $\triangle ACL$ are tangent at $Q$.
Prove that $IP = IQ$.
\end{enumerate}
\pagebreak
\section{Solutions to Day 1}
\subsection{TSTST 2019/1, proposed by Evan Chen}
\textsl{Available online at \url{https://aops.com/community/p12608849}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
\def\di{\mathbin{\diamondsuit}}
Find all binary operations $\di \colon \RR_{>0} \times \RR_{>0} \to \RR_{>0}$
(meaning $\di$ takes pairs of
positive real numbers to positive real numbers)
such that for any real numbers $a,b,c > 0$,
\begin{itemize}
\ii the equation $a \di (b \di c) = (a \di b) \cdot c$ holds; and
\ii if $a \ge 1$ then $a \di a \ge 1$.
\end{itemize}
\end{mdframed}
\def\di{\mathbin{\diamondsuit}}
The answer is only multiplication and division,
which both obviously work.
We present two approaches,
one appealing to theorems on Cauchy's functional equation,
and one which avoids it.
\paragraph{First solution using Cauchy FE}
We prove:
\begin{claim*}
We have $a \di b = a f(b)$ where $f$ is
some involutive and totally multiplicative function.
(In fact, this classifies all functions
satisfying the first condition completely.)
\end{claim*}
\begin{proof}
Let $P(a,b,c)$ denote the
assertion $a \di (b \di c) = (a \di b) \cdot c$.
\begin{itemize}
\ii Note that for any $x$,
the function $y \mapsto x \di y$ is injective,
because if $x \di y_1 = x \di y_2$ then take $P(1, x, y_i)$
to get $y_1 = y_2$.
\ii Take $P(1,x,1)$ and injectivity to get $x \di 1 = x$.
\ii Take $P(1,1,y)$ to get $1 \di (1 \di y) = y$.
\ii Take $P(x, 1, 1 \di y)$ to get
\[ x \di y = x \cdot (1 \di y). \]
\end{itemize}
Henceforth let us define $f(y) = 1 \di y$, so
$f(1) = 1$, $f$ is involutive and
\[ x \di y = xf(y). \]
Plugging this into the original condition now gives
$f(bf(c)) = f(b)c$,
which (since $f$ is an involution)
gives $f$ completely multiplicative.
\end{proof}
In particular, $f(1) = 1$.
We are now interested only in the second condition,
which reads $f(x) \ge 1/x$ for $x \ge 1$.
Define the function
\[ g(t) = \log f(e^t) \]
so that $g$ is additive,
and also $g(t) \ge -t$ for all $t \ge 0$.
We appeal to the following theorem:
\begin{lemma*}
If $h \colon \RR \to \RR$ is an additive function
which is not linear,
then it is \emph{dense} in the plane:
for any point $(x_0, y_0)$ and $\eps > 0$
there exists $(x,y)$ such that $h(x) = y$
and $\sqrt{(x-x_0)^2 + (y-y_0)^2} < \eps$.
\end{lemma*}
Applying this lemma with the fact
that $g(t) \ge -t$ implies readily that $g$ is linear.
In other words, $f$ is of the form $f(x) = x^r$
for some fixed real number $r$.
It is easy to check $r =\pm 1$ which finishes.
\paragraph{Second solution manually}
As before we arrive at $a \di b = af(b)$,
with $f$ an involutive and totally multiplicative function.
We prove that:
\begin{claim*}
For any $a > 0$, we have $f(a) \in \{1/a, a\}$.
\end{claim*}
\begin{proof}
WLOG $b > 1$, and suppose $f(b) = a \ge 1/b$ hence $f(a) = b$.
Assume that $ab > 1$; we show $a = b$.
Note that for integers $m$ and $n$ with $a^n b^m \ge 1$,
we must have
\[ a^m b^n = f(b)^m f(a)^n
= f(a^n b^m) \ge \frac{1}{a^n b^m} \implies (ab)^{m+n} \ge 1 \]
and thus we have arrived at the proposition
\[ m+n < 0 \implies n \log_b a + m < 0 \]
for all integers $m$ and $n$.
Due to the density of $\QQ$ in the real numbers,
this can only happen if $\log_b a = 1$ or $a = b$.
\end{proof}
\begin{claim*}
The function $f$ is continuous.
\end{claim*}
\begin{proof}
Indeed, it's equivalent to show
$g(t) = \log f(e^t)$ is continuous,
and we have that
\[
\left\lvert g(t)-g(s) \right\rvert
= \left\lvert \log f(e^{t-s}) \right\rvert
= \left\lvert t-s \right\rvert
\]
since $f(e^{t-s}) = e^{\pm |t-s|}$.
Therefore $g$ is Lipschitz.
Hence $g$ continuous, and $f$ is too.
\end{proof}
Finally, we have from $f$ multiplicative that
\[ f(2^q) = f(2)^q \]
for every rational number $q$, say.
As $f$ is continuous
this implies $f(x) \equiv x$ or $f(x) \equiv 1/x$ identically
(depending on whether $f(2) = 2$ or $f(2)=1/2$, respectively).
Therefore, $a \di b = ab$ or $a \di b = a \div b$, as needed.
\begin{remark*}
The Lipschitz condition is one of several other ways to proceed.
The point is that if $f(2) = 2$ (say),
and $x/2^q$ is close to $1$,
then $f(x)/2^q = f(x/2^q)$ is close to $1$,
which is enough to force $f(x) = x$ rather than $f(x) = 1/x$.
\end{remark*}
\begin{remark*}
Compare to AMC 10A 2016 \#23,
where the second condition is $a \di a = 1$.
\end{remark*}
\pagebreak
\subsection{TSTST 2019/2, proposed by Merlijn Staps}
\textsl{Available online at \url{https://aops.com/community/p12608478}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $ABC$ be an acute triangle with circumcircle $\Omega$
and orthocenter $H$.
Points $D$ and $E$ lie on segments $AB$ and $AC$
respectively, such that $AD = AE$.
The lines through $B$ and $C$ parallel to $\ol{DE}$
intersect $\Omega$ again at $P$ and $Q$, respectively.
Denote by $\omega$ the circumcircle of $\triangle ADE$.
\begin{enumerate}[(a)]
\ii Show that lines $PE$ and $QD$ meet on $\omega$.
\ii Prove that if $\omega$ passes through $H$,
then lines $PD$ and $QE$ meet on $\omega$ as well.
\end{enumerate}
\end{mdframed}
We will give one solution to (a),
then several solutions to (b).
\paragraph{Solution to (a)}
Note that $\dang AQP = \dang ABP = \dang ADE$
and $\dang APQ = \dang ACQ = \dang AED$,
so we have a spiral similarity $\triangle ADE \sim \triangle AQP$.
Therefore, lines $PE$ and $QD$ meet at the second
intersection of $\omega$ and $\Omega$ other than $A$.
Call this point $X$.
% (Note this does not even depend on $\omega$ passing through $H$.)
\paragraph{Solution to (b) using angle chasing}
Let $L$ be the reflection of $H$ across $\ol{AB}$,
which lies on $\Omega$.
\begin{claim*}
Points $L$, $D$, $P$ are collinear.
\end{claim*}
\begin{proof}
This is just angle chasing:
\begin{align*}
\dang CLD &= \dang DHL
= \dang DHA + \dang AHL = \dang DEA + \dang AHC \\
&= \dang ADE + \dang CBA = \dang ABP + \dang CBA
= \dang CBP = \dang CLP. \qedhere
\end{align*}
\end{proof}
\begin{center}
\begin{asy}
size(7cm);
pair A = dir(125);
pair B = dir(210);
pair C = dir(-30);
pair O = (0,0);
pair H =orthocenter(A,B,C);
pair I = incenter(A,B,C);
pair J = 2*foot(H,A,I) - H;
pair D = intersectionpoints(A--B,circumcircle(A,H,J))[1];
pair E = intersectionpoints(A--C,circumcircle(A,H,J))[1];
pair S = intersectionpoints(circumcircle(A,B,C),circumcircle(A,H,J))[0];
pair P = extension(S,E,D,J);
pair Q = extension(S,D,E,J);
pair X = extension(P,E,Q,D);
draw(B--foot(B,A,C),dotted+gray);
draw(A--foot(A,B,C),dotted+gray);
draw(C--foot(C,A,B),dotted+gray);
draw(circumcircle(A,B,C),purple);
draw(circumcircle(A,H,J),red);
draw(D--E,red);
draw(B--P,purple);
draw(C--Q,purple);
pair HH = 1.9*circumcenter(A,D,E)-1.1*D;
pair BB = -B;
pair K = extension(D,P,E,Q);
pair L = extension(P,D,C,H);
draw(Q--E,dotted+red);
draw(P--L,dashed+red);
draw(H--L, dotted);
draw(P--X--Q, orange+dashed);
draw(A--B--C--A);
dot("$A$", A, dir(A));
//dot("$Z$",Z,dir(-90));
dot("$B$",B,dir(225));
dot("$C$",C,dir(C));
dot("$H$",H,dir(225));
dot("$D$",D,2*dir(56));
dot("$E$",E,dir(30));
dot("$P$",P,dir(P));
dot("$Q$",Q,dir(Q));
dot("$L$",L,dir(L));
dot("$K$",K,dir(K-A));
dot("$X$",X,dir(X), red);
label("$\omega$",HH,red);
label("$\Omega$",-1.1*B,purple);
\end{asy}
\end{center}
Now let $K \in \omega$ such that $DHKE$ is an isosceles trapezoid,
i.e.\ $\dang BAH = \dang KAE$.
\begin{claim*}
Points $D$, $K$, $P$ are collinear.
\end{claim*}
\begin{proof}
Using the previous claim,
\[ \dang KDE = \dang KAE = \dang BAH = \dang LAB
= \dang LPB = \dang DPB = \dang PDE. \qedhere \]
\end{proof}
By symmetry, $\ol{QE}$ will then pass through the same $K$, as needed.
\begin{remark*}
These two claims imply each other,
so guessing one of them allows one to realize the other.
It is likely the latter is easiest to guess from the diagram,
since it does not need any additional points.
\end{remark*}
\paragraph{Solution to (b) by orthogonal circles (found by contestants)}
We define $K$ as in the previous solution,
but do not claim that $K$ is the desired intersection.
Instead, we note that:
\begin{claim*}
Point $K$ is the orthocenter of isosceles triangle $APQ$.
\end{claim*}
\begin{proof}
Notice that $AH = AK$ and $BC = PQ$.
Moreover from $\ol{AH} \perp \ol{BC}$
we deduce $\ol{AK} \perp \ol{PQ}$ by reflection
across the angle bisector.
In light of the formula ``$AH^2 = 4R^2 - a^2$'', this implies the conclusion.
\end{proof}
Let $M$ be the midpoint of $\ol{PQ}$.
Since $\triangle APQ$ is isosceles,
\[ \ol{AKM} \perp \ol{PQ} \implies MK \cdot MA = MP^2 \]
by orthocenter properties.
So to summarize
\begin{itemize}
\ii The circle with diameter $\ol{PQ}$ is orthogonal to $\omega$.
\ii The point $X = \ol{QD} \cap \ol{PE}$ is on $\omega$.
\end{itemize}
Combined with (a), this implies the result by Brokard theorem.
\paragraph{Solution to (b) by complex numbers (Yang Liu and Michael Ma)}
Let $M$ be the arc midpoint of $\widehat{BC}$.
We use the standard arc midpoint configuration.
We have that
\[ A = a^2, \; B = b^2, \; C = c^2, \; M = -bc, \;
H = a^2+b^2+c^2, \; P = \frac{a^2c}{b}, \; Q = \frac{a^2b}{c}, \]
where $M$ is the arc midpoint of $\widehat{BC}$.
By direct angle chasing we can verify that $\ol{MB} \parallel \ol{DH}$.
Also, $D \in \ol{AB}$.
Therefore, we can compute $D$ as follows.
\[ d + a^2b^2 \bar{d} = a^2+b^2 \text{ and }
\frac{d-h}{\bar{d} - \bar{h}} = -mb^2 = b^3c \implies
d = \frac{a^2(a^2c+b^2c+c^3-b^3)}{c(bc+a^2)}. \]
By symmetry, we have that
\[ e = \frac{a^2(a^2b+bc^2+b^3-c^3)}{b(bc+a^2)}. \]
To finish, we want to show that the angle
between $\ol{DP}$ and $\ol{EQ}$ is angle $A$.
To show this, we compute
$\frac{d-p}{e-q} \Big/ \ol{\frac{d-p}{e-q}}$.
First, we compute
\begin{align*}
d-p &= \frac{a^2(a^2c+b^2c+c^3-b^3)}{c(bc+a^2)} - \frac{a^2c}{b} \\
&= a^2 \left(\frac{a^2c+b^2c+c^3-b^3}{c(bc+a^2)} - \frac{c}{b} \right)
= \frac{a^2(a^2c-b^3)(b-c)}{bc(bc+a^2)}.
\end{align*}
By symmetry,
\[ \frac{d-p}{e-q} = -\frac{a^2c-b^3}{a^2b-c^3}
\implies \frac{d-p}{e-q} \Big/ \ol{\frac{d-p}{e-q}}
= \frac{a^2b^3c}{a^2bc^3} = \frac{b^2}{c^2} \]
as desired.
\paragraph{Solution to (b) using untethered moving points (Zack Chroman)}
We work in the real projective plane $\mathbb{RP}^2$,
and animate $C$ linearly on a fixed line through $A$.
Recall:
\begin{lemma*}
[Zack's lemma]
Suppose points $A$, $B$ have degree $d_1$, $d_2$,
and there are $k$ values of $t$ for which $A=B$.
Then line $AB$ has degree at most $d_1+d_2-k$.
Similarly, if lines $\ell_1$, $\ell_2$ have degrees $d_1$, $d_2$,
and there are $k$ values of $t$ for which $\ell_1=\ell_2$,
then the intersection $\ell_1 \cap \ell_2$ has degree at most $d_1+d_2-k$.
\end{lemma*}
Now, note that $H$ moves linearly in $C$ on line $BH$.
Furthermore, angles $\angle AHE$, $\angle AHF$ are fixed,
we get that $D$ and $E$ have degree $2$.
One way to see this is using the lemma; $D$ lies on line $AB$,
which is fixed, and line $HD$ passes through a point at infinity
which is a constant rotation of the point at infinity on line $AH$,
and therefore has degree $1$.
Then $D$, $E$ have degree at most $1+1-0=2$.
Now, note that $P,Q$ move linearly in $C$.
Both of these are because the circumcenter $O$ moves linearly in $C$,
and $P$, $Q$ are reflections of $B$, $C$ in a
line through $O$ with fixed direction, which also moves linearly.
So by the lemma, the lines $PD$, $QE$ have degree at most $3$.
I claim they actually have degree $2$;
to show this it suffices to give an example of a choice of $C$
for which $P=D$ and one for which $Q=E$.
But an easy angle chase shows that in the unique case when $P=B$,
we get $D=B$ as well and thus $P=D$. Similarly when $Q=C$, $E=C$.
It follows from the lemma that lines $PD$, $QE$ have degree at most $2$.
Let $\ell_\infty$ denote the line at infinity.
I claim that the points $P_1=PD \cap \ell_\infty$,
$P_2=QE \cap \ell_\infty$ are projective in $C$.
Since $\ell_\infty$ is fixed, it suffices to show by the lemma that there
exists some value of $C$ for which $QE=\ell_\infty$ and $PD = \ell_\infty$.
But note that as $C \to \infty$, all four points $P,D,Q,E$ go to infinity.
It follows that $P_1$, $P_2$ are projective in $C$.
Then to finish,
recall that we want to show that $\angle (PD, QE)$ is constant.
It suffices then to show that there's a constant rotation
sending $P_1$ to $P_2$. Since $P_1$, $P_2$ are projective,
it suffices to verify this for $3$ values of $C$.
We can take $C$ such that $\angle ABC=90$, $\angle ACB = 90$,
or $AB=AC$, and all three cases are easy to check.
\pagebreak
\subsection{TSTST 2019/3, proposed by Nikolai Beluhov}
\textsl{Available online at \url{https://aops.com/community/p12608769}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
On an infinite square grid we place finitely many \emph{cars},
which each occupy a single cell and face in one of the four cardinal directions.
Cars may never occupy the same cell.
It is given that the cell immediately in front of each car is empty,
and moreover no two cars face towards each other
(no right-facing car is to the left of a left-facing car within a row, etc.).
In a \emph{move}, one chooses a car and shifts it one cell forward to a vacant cell.
Prove that there exists an infinite sequence of valid moves
using each car infinitely many times.
\end{mdframed}
Let $S$ be any rectangle containing all the cars.
Partition $S$ into horizontal strips of height $1$,
and color them red and green in an alternating fashion.
It is enough to prove all the cars may exit $S$.
\begin{center}
\begin{asy}
size(10cm);
defaultpen(fontsize(12pt));
usepackage("amssymb");
picture base;
draw(base, box((0,0), (7,5)), black+1);
fill(base, box((0,0), (7,1)), rgb(1,0.9,0.9));
fill(base, box((0,2), (7,3)), rgb(1,0.9,0.9));
fill(base, box((0,4), (7,5)), rgb(1,0.9,0.9));
fill(base, box((0,1), (7,2)), rgb(0.9,1,0.9));
fill(base, box((0,3), (7,4)), rgb(0.9,1,0.9));
for (int i=1; i<7; ++i) {
draw(base, (i,0)--(i,5), grey);
}
for (int i=1; i<5; ++i) {
draw(base, (0,i)--(7,i), grey);
}
picture phase0;
add(phase0, base);
draw(phase0, (1.5,1.5)--(1.5,2.5), dashed+orange, EndArrow(TeXHead));
draw(phase0, (4.5,3.5)--(4.5,2.5), dashed+orange, EndArrow(TeXHead));
draw(phase0, (5.5,3.5)--(5.5,2.5), dashed+orange, EndArrow(TeXHead));
draw(phase0, (6.5,3.5)--(6.5,4.5), dashed+orange, EndArrow(TeXHead));
label(phase0, "$\blacktriangleright$", (1.5, 4.5));
label(phase0, "$\bigtriangledown$", (3.5, 4.5));
label(phase0, "$\blacktriangleright$", (1.5, 3.5));
label(phase0, "$\bigtriangledown$", (4.5, 3.5));
label(phase0, "$\bigtriangledown$", (5.5, 3.5));
label(phase0, "$\bigtriangleup$", (6.5, 3.5));
label(phase0, "$\blacktriangleright$", (0.5, 2.5));
label(phase0, "$\blacktriangleright$", (3.5, 2.5));
label(phase0, "$\bigtriangleup$", (2.5, 2.5));
label(phase0, "$\bigtriangleup$", (1.5, 1.5));
label(phase0, "$\blacktriangleleft$", (3.5, 1.5));
label(phase0, "$\blacktriangleleft$", (5.5, 1.5));
label(phase0, "$\blacktriangleright$", (6.5, 1.5));
label(phase0, "$\blacktriangleleft$", (4.5, 0.5));
label(phase0, "Step 1", (3.5,0), dir(-90));
picture phase1;
add(phase1, base);
draw(phase1, (5.5,1.5)--(0,1.5), dashed+orange, EndArrow(TeXHead));
draw(phase1, (6.5,1.5)--(7,1.5), dashed+orange, EndArrow(TeXHead));
draw(phase1, (1.5,3.5)--(7,3.5), dashed+orange, EndArrow(TeXHead));
label(phase1, "$\blacktriangleright$", (1.5, 4.5));
label(phase1, "$\bigtriangledown$", (3.5, 4.5));
label(phase1, "$\blacktriangleright$", (1.5, 3.5));
label(phase1, "$\bigtriangledown$", (4.5, 2.5), blue); // moved down
label(phase1, "$\bigtriangledown$", (5.5, 2.5), blue); // moved down
label(phase1, "$\bigtriangleup$", (6.5, 4.5), blue); // moved up
label(phase1, "$\blacktriangleright$", (0.5, 2.5));
label(phase1, "$\blacktriangleright$", (3.5, 2.5));
label(phase1, "$\bigtriangleup$", (2.5, 2.5));
label(phase1, "$\bigtriangleup$", (1.5, 2.5), blue); // moved up
label(phase1, "$\blacktriangleleft$", (3.5, 1.5));
label(phase1, "$\blacktriangleleft$", (5.5, 1.5));
label(phase1, "$\blacktriangleright$", (6.5, 1.5));
label(phase1, "$\blacktriangleleft$", (4.5, 0.5));
label(phase1, "Step 2", (3.5,0), dir(-90));
picture phase2;
add(phase2, base);
draw(phase2, (1.5,2.5)--(1.5,3.5), dashed+orange, EndArrow(TeXHead));
draw(phase2, (2.5,2.5)--(2.5,3.5), dashed+orange, EndArrow(TeXHead));
draw(phase2, (3.5,4.5)--(3.5,3.5), dashed+orange, EndArrow(TeXHead));
draw(phase2, (4.5,2.5)--(4.5,1.5), dashed+orange, EndArrow(TeXHead));
draw(phase2, (5.5,2.5)--(5.5,1.5), dashed+orange, EndArrow(TeXHead));
draw(phase2, (6.5,4.5)--(6.5,5), dashed+orange, EndArrow(TeXHead));
label(phase2, "$\blacktriangleright$", (1.5, 4.5));
label(phase2, "$\bigtriangledown$", (3.5, 4.5));
label(phase2, "$\bigtriangleup$", (6.5, 4.5));
label(phase2, "$\bigtriangledown$", (4.5, 2.5));
label(phase2, "$\bigtriangledown$", (5.5, 2.5));
label(phase2, "$\blacktriangleright$", (0.5, 2.5));
label(phase2, "$\blacktriangleright$", (3.5, 2.5));
label(phase2, "$\bigtriangleup$", (2.5, 2.5));
label(phase2, "$\bigtriangleup$", (1.5, 2.5));
label(phase2, "$\blacktriangleleft$", (4.5, 0.5));
label(phase2, "Step 3", (3.5,0), dir(-90));
picture phase3;
add(phase3, base);
draw(phase3, (1.5,4.5)--(7,4.5), dashed+orange, EndArrow(TeXHead));
draw(phase3, (0.5,2.5)--(7,2.5), dashed+orange, EndArrow(TeXHead));
draw(phase3, (4.5,0.5)--(0,0.5), dashed+orange, EndArrow(TeXHead));
label(phase3, "$\blacktriangleright$", (1.5, 4.5));
label(phase3, "$\bigtriangledown$", (3.5, 3.5), blue);
label(phase3, "$\bigtriangledown$", (4.5, 1.5), blue);
label(phase3, "$\bigtriangledown$", (5.5, 1.5), blue);
label(phase3, "$\blacktriangleright$", (0.5, 2.5));
label(phase3, "$\blacktriangleright$", (3.5, 2.5));
label(phase3, "$\bigtriangleup$", (2.5, 3.5), blue);
label(phase3, "$\bigtriangleup$", (1.5, 3.5), blue);
label(phase3, "$\blacktriangleleft$", (4.5, 0.5));
label(phase3, "Step 4", (3.5,0), dir(-90));
add(phase0);
add(shift(8,0)*phase1);
add(shift(0,-7)*phase2);
add(shift(8,-7)*phase3);
\end{asy}
\end{center}
To do so, we outline a five-stage plan for the cars.
\begin{enumerate}
\ii All vertical cars in a green cell may advance one cell into a red cell
(or exit $S$ altogether),
by the given condition.
(This is the only place where the hypothesis about empty space is used!)
\ii All horizontal cars on green cells may exit $S$,
as no vertical cars occupy green cells.
\ii All vertical cars in a red cell
may advance one cell into a green cell
(or exit $S$ altogether),
as all green cells are empty.
\ii All horizontal cars within red cells may exit $S$,
as no vertical car occupy red cells.
\ii The remaining cars exit $S$, as they are all vertical.
The solution is complete.
\end{enumerate}
\begin{remark*}[Author's comments]
The solution I've given for this problem is so short
and simple that it might appear at first
to be about IMO 1 difficulty. I don't believe that's true!
There are very many approaches that look perfectly plausible at first,
and then fall apart in this or that twisted special case.
\end{remark*}
\begin{remark*}[Higher-dimensional generalization by author]
The natural higher-dimensional generalization
is true, and can be proved in largely the same fashion.
For example, in three dimensions,
one may let $S$ be a rectangular prism
and partition $S$ into horizontal slabs
and color them red and green in an alternating fashion.
Stages 1, 3, and 5 generalize immediately,
and stages 2 and 4 reduce to an application of the two-dimensional problem.
In the same way, the general problem is handled by induction on the dimension.
\end{remark*}
\begin{remark*}
[Historical comments]
For $k > 1$, we could consider a variant of the problem
where cars are $1 \times k$ rectangles (moving parallel to the longer edge)
instead of occupying single cells.
In that case, if there are $2k-1$ empty spaces in front of each car,
the above proof works
(with the red and green strips having height $k$ instead).
On the other hand, at least $k$ empty spaces are necessary.
We don't know the best constant in this case.
\end{remark*}
\pagebreak
\section{Solutions to Day 2}
\subsection{TSTST 2019/4, proposed by Merlijn Staps}
\textsl{Available online at \url{https://aops.com/community/p12608513}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Consider coins with positive real denominations not exceeding $1$.
Find the smallest $C>0$ such that the following holds:
if we are given any $100$ such coins
with total value $50$, then we can
always split them into two stacks
of $50$ coins each such that the absolute difference
between the total values of the two stacks is at most $C$.
\end{mdframed}
The answer is $C = \frac{50}{51}$.
The lower bound is obtained
if we have $51$ coins of value $\frac{1}{51}$
and $49$ coins of value $1$.
(Alternatively, $51$ coins of value $1-\frac{\eps}{51}$
and $49$ coins of value $\frac{\eps}{49}$ works fine for $\eps > 0$.)
We now present two (similar)
proofs that this $C = \frac{50}{51}$ suffices.
\paragraph{First proof (original)}
Let $a_1 \le \dots \le a_{100}$ denote the values of the coins in ascending order.
Since the $51$ coins $a_{50}, \dots, a_{100}$ are worth at least $51 a_{50}$,
it follows that $a_{50} \le \tfrac{50}{51}$;
likewise $a_{51} \ge \tfrac{1}{51}$.
We claim that choosing the stacks with coin values
\[a_1, a_3, \dots, a_{49}, \quad a_{52}, a_{54}, \dots, a_{100}\]
and
\[a_2, a_4, \dots, a_{50}, \quad a_{51}, a_{53}, \dots, a_{99}\]
works.
Let $D$ denote the (possibly negative) difference between the two total values.
Then
\begin{align*}
D & = (a_1-a_2) + \dots + (a_{49}-a_{50}) - a_{51} + (a_{52}-a_{53}) + \dots + (a_{98}-a_{99}) + a_{100}\\
& \le 25 \cdot 0 - \frac{1}{51} + 24 \cdot 0 + 1 = \frac{50}{51}.
\end{align*}
Similarly, we have
\begin{align*}
D & = a_1 + (a_3-a_2) + \dots + (a_{49}-a_{48}) - a_{50} + (a_{52}-a_{51}) + \dots + (a_{100}-a_{99})\\
& \ge 0 + 24 \cdot 0 - \frac{50}{51} + 25 \cdot 0 = - \frac{50}{51}.
\end{align*}
It follows that $|D| \le \tfrac{50}{51}$, as required.
\paragraph{Second proof (Evan Chen)}
Again we sort the coins in increasing order
$0 < a_1 \le a_2 \le \dots \le a_{100} \le 1$.
A \emph{large gap} is an index $i \ge 2$
such that $a_i > a_{i-1} + \frac{50}{51}$;
obviously there is at most one such large gap.
\begin{claim*}
If there is a large gap,
it must be $a_{51} > a_{50} + \frac{50}{51}$.
\end{claim*}
\begin{proof}
If $i < 50$ then we get $a_{50}, \dots, a_{100} > \frac{50}{51}$
and the sum $\sum_1^{100} a_i > 50$ is too large.
Conversely if $i > 50$ then we get
$a_1, \dots, a_{i-1} < \frac{1}{51}$
and the sum $\sum_1^{100} a_i < 1/51 \cdot 51 + 49$ is too small.
\end{proof}
Now imagine starting with the coins $a_1$, $a_3$, \dots, $a_{99}$,
which have total value $S \le 25$.
We replace $a_1$ by $a_2$,
then $a_3$ by $a_4$, and so on,
until we replace $a_{99}$ by $a_{100}$.
At the end of the process we have $S \ge 25$.
Moreover, since we did not cross a large gap at any point,
the quantity $S$ changed by at most $C = \frac{50}{51}$ at each step.
So at some point in the process we need to have $25-C/2 \le S \le 25+C/2$,
which proves $C$ works.
\pagebreak
\subsection{TSTST 2019/5, proposed by Gunmay Handa}
\textsl{Available online at \url{https://aops.com/community/p12608496}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $ABC$ be an acute triangle with orthocenter $H$ and circumcircle $\Gamma$.
A line through $H$ intersects segments $AB$ and $AC$ at $E$ and $F$, respectively.
Let $K$ be the circumcenter of $\triangle AEF$,
and suppose line $AK$ intersects $\Gamma$ again at a point $D$.
Prove that line $HK$ and the line through $D$
perpendicular to $\ol{BC}$ meet on $\Gamma$.
\end{mdframed}
We present several solutions.
(There are more in the official packet; some are omitted here,
which explains the numbering.)
\paragraph{First solution (Andrew Gu)}
We begin with the following two observations.
\begin{claim*}
Point $K$ lies on the radical axis of $(BEH)$ and $(CFH)$.
\end{claim*}
\begin{proof}
Actually we claim $\ol{KE}$ and $\ol{KF}$ are tangents.
Indeed,
\[ \dang HEK = 90\dg - \dang EAF = 90\dg - \dang BAC = \dang HBE \]
implying the result.
Since $KE = KF$, this implies the result.
\end{proof}
\begin{claim*}
The second intersection $M$ of $(BEH)$ and $(CFH)$ lies on $\Gamma$.
\end{claim*}
\begin{proof}
By Miquel's theorem on $\triangle AEF$ with $H \in \ol{EF}$,
$B \in \ol{AE}$, $C \in \ol{AF}$.
\end{proof}
\begin{center}
\begin{asy}
pair A = dir(130);
pair B = dir(210);
pair C = dir(330);
pair H = orthocenter(A, B, C);
pair T = dir(285);
pair D = B*C/T;
pair X = -T;
pair E = extension(A, B, H, foot(H, A, T));
pair F = extension(E, H, A, C);
draw(A--B--C--cycle, deepcyan);
filldraw(unitcircle, opacity(0.1)+lightcyan, deepcyan);
draw(E--F, lightblue);
draw(A--D, lightblue);
draw(D--X, lightred);
draw(circumcircle(B, E, H), deepgreen);
draw(circumcircle(C, F, H), deepgreen);
pair M = foot(T, X, H);
pair K = circumcenter(A, E, F);
draw(E--K--F, deepgreen);
draw(M--X, orange+dashed);
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$H$", H, dir(270));
dot("$D$", D, dir(D));
dot("$X$", X, dir(X));
dot("$E$", E, dir(E));
dot("$F$", F, dir(F));
dot("$M$", M, dir(M));
dot("$K$", K, dir(K));
/* TSQ Source:
A = dir 130
B = dir 210
C = dir 330
H = orthocenter A B C R270
T := dir 285
D = B*C/T
X = -T
E = extension A B H foot H A T
F = extension E H A C
A--B--C--cycle deepcyan
unitcircle 0.1 lightcyan / deepcyan
E--F lightblue
A--D lightblue
D--X lightred
circumcircle B E H deepgreen
circumcircle C F H deepgreen
M = foot T X H
K = circumcenter A E F
E--K--F deepgreen
M--X orange dashed
*/
\end{asy}
\end{center}
In particular, $M$, $H$, $K$ are collinear.
Let $X$ be on $\Gamma$ with $\ol{DX} \perp \ol{BC}$;
we then wish to show $X$ lies on the line $MHK$ we found.
This is angle chasing: compute
\begin{align*}
\dang XMB &= \dang XDB = 90\dg - \dang DBC = 90\dg - \dang DAC \\
&= 90\dg - \dang KAF = \dang FEA = \dang HEB = \dang HMB
\end{align*}
as needed.
\paragraph{Second solution (Ankan Bhattacharya)}
We let $D'$ be the second intersection of $\ol{EF}$
with $(BHC)$ and redefine $D$ as the reflection of $D'$ across $\ol{BC}$.
We will first prove that this point $D$ coincides with the point $D$
given in the problem statement.
The idea is that:
\begin{claim*}
$A$ is the $D$-excenter of $\triangle DEF$.
\end{claim*}
\begin{proof}
We contend $BED'D$ is cyclic.
This follows by angle chasing:
\begin{align*}
\dang D'DB &= \dang BD'D
= \dang D'BC + 90\dg = \dang D'HC + 90\dg \\
&= \dang D'HC + \dang(HC,AB) = \dang(D'H, AB) = \dang D'EB.
\end{align*}
Now as $BD = BD'$, we obtain $\ol{BEA}$ externally
bisects $\angle DED' \cong \angle DEF$.
Likewise $\ol{FA}$ externally bisects $\angle DFE$,
so $A$ is the $D$-excenter of $\triangle DEF$.
\end{proof}
Hence, by the so-called ``Fact 5'', point $K$ lies on $\ol{DA}$,
so this point $D$ is the one given in the problem statement.
\begin{center}
\begin{asy}
unitsize(100);
pair A = dir(110), B = dir(210), C = dir(330), D = dir(280);
pair H = orthocenter(A, B, C), Dp = reflect(B, C) * D,
E = extension(A, B, H, Dp), F = extension(A, C, H, Dp),
K = circumcenter(A, E, F),
X = A + Dp - H;
draw(B--D--C--Dp--cycle, lightgreen);
draw(E--F, cyan);
draw(A--H, lightred);
draw(D--X, lightred);
draw(D--E^^D--F);
draw(D--K);
draw(A--X, cyan);
draw(K--A^^K--E^^K--F, purple);
draw(H--X, dashed);
draw(A--B--C--cycle);
draw(circumcircle(B, D, Dp)^^circumcircle(C, D, Dp), dotted);
draw(unitcircle);
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$D$", D, dir(D));
dot("$D'$", Dp, dir(130));
dot("$H$", H, dir(130));
dot("$E$", E, dir(H-C));
dot("$F$", F, dir(H-B));
dot("$K$", K, dir(160));
dot("$X$", X, dir(X));
\end{asy}
\end{center}
Now choose point $X$ on $(ABC)$ satisfying $\ol{DX} \perp \ol{BC}$.
\begin{claim*}
Point $K$ lies on line $HX$.
\end{claim*}
\begin{proof}
Clearly $AHD'X$ is a parallelogram.
By Ptolemy on $DEKF$,
\[\frac{KD}{KA} = \frac{KD}{KE} = \frac{DE + DF}{EF}.\]
On the other hand,
if we let $r_D$ denote the $D$-exradius of $\triangle DEF$ then
\[\frac{XD}{XD'}
= \frac{[DEX] + [DFX]}{[XEF]}
= \frac{[DEX] + [DFX]}{[AEF]}
= \frac{DE \cdot r_D + DF \cdot r_D}{EF \cdot r_D}
= \frac{DE + DF}{EF}. \]
Thus
\[[AKX] = \frac{KA}{KD} \cdot [DKX]
= \frac{KA}{KD} \cdot \frac{XD}{XD'} \cdot [KD'X]
= [D'KX].\]
This is sufficient to prove $K$ lies on $\ol{HX}$.
\end{proof}
The solution is complete: $X$ is the desired concurrency point.
\paragraph{Fourth solution, complex numbers with spiral similarity (Evan Chen)}
First if $\ol{AD} \perp \ol{BC}$ there is nothing to prove,
so we assume this is not the case.
%Also, if $D = B$ then $D = E = B$ and $F$ is the foot of the $D$-altitude,
%meaning $K$ is the midpoint of $\ol{AB}$,
%and so the concurrency point is the antipode of $C$.
%Thus we will assume none of these are the case.
Let $W$ be the antipode of $D$.
Let $S$ denote the second intersection of $(AEF)$ and $(ABC)$.
Consider the spiral similarity sending $\triangle SEF$ to $\triangle SBC$:
\begin{itemize}
\ii It maps $H$ to a point $G$ on line $BC$,
\ii It maps $K$ to $O$.
\ii It maps the $A$-antipode of $\triangle AEF$ to $D$.
\ii Hence (by previous two observations) it maps $A$ to $W$.
\ii Also, the image of line $AD$ is line $WO$,
which does not coincide with line $BC$
(as $O$ does not lie on line $BC$).
\end{itemize}
Therefore, $K$ is the \emph{unique} point on line $\ol{AD}$
for one can get a direct similarity
\[ \triangle AKH \sim \triangle WOG \qquad(\heartsuit) \]
for some point $G$ lying on line $\ol{BC}$.
\begin{center}
\begin{asy}
pair A = dir(130);
pair B = dir(210);
pair C = dir(330);
pair D = dir(265);
pair H = orthocenter(A, B, C);
pair X = -B*C/D;
pair K = extension(A, D, H, X);
pair O = origin;
pair E = extension(A, B, H, foot(H, A, -X));
pair F = extension(E, H, A, C);
draw(A--B--C--cycle, orange);
filldraw(unitcircle, opacity(0.1)+yellow, orange);
draw(A--D, red);
draw(D--X, red);
draw(E--F, orange);
pair S = (B*F-E*C)/(B+F-E-C);
filldraw(circumcircle(A, E, F), opacity(0.1)+lightcyan, lightblue);
draw(H--X, lightblue);
pair W = -D;
pair G = S+(H-S)*(C-S)/(F-S);
filldraw(S--A--K--H--cycle, opacity(0.1)+blue, blue+0.8);
filldraw(S--W--O--G--cycle, opacity(0.1)+orange, red+0.8);
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$D$", D, dir(D));
dot("$H$", H, dir(270));
dot("$X$", X, dir(X));
dot("$K$", K, dir(170));
dot("$O$", O, dir(315));
dot("$E$", E, dir(E));
dot("$F$", F, dir(F));
dot("$S$", S, dir(S));
dot("$W$", W, dir(W));
dot("$G$", G, dir(G));
/* TSQ Source:
A = dir 130
B = dir 210
C = dir 330
D = dir 265
H = orthocenter A B C R270
X = -B*C/D
K = extension A D H X R170
O = origin R315
E = extension A B H foot H A -X
F = extension E H A C
A--B--C--cycle orange
unitcircle 0.1 yellow / orange
A--D red
D--X red
E--F orange
S = (B*F-E*C)/(B+F-E-C)
circumcircle A E F 0.1 lightcyan / lightblue
H--X lightblue
W = -D
G = S+(H-S)*(C-S)/(F-S)
S--A--K--H--cycle 0.1 blue / blue+0.8
S--W--O--G--cycle 0.1 orange / red+0.8
*/
\end{asy}
\end{center}
On the other hand, let us re-define $K$ as $\ol{XH} \cap \ol{AD}$.
We will show that the corresponding $G$ making $(\heartsuit)$ true
lies on line $BC$.
We apply complex numbers with $\Gamma$ the unit circle,
with $a$, $b$, $c$, $d$ taking their usual meanings,
$H = a+b+c$, $X = -bc/d$, and $W = -d$.
Then point $K$ is supposed to satisfy
\begin{align*}
k + ad \ol k &= a+d \\
\frac{k+\frac{bc}{d}}{a+b+c+\frac{bc}{d}}
&= \frac{\ol k + \frac{d}{bc}}{\frac1a+\frac1b+\frac1c+\frac{d}{bc}} \\
\iff \frac{\frac1a+\frac1b+\frac1c+\frac{d}{bc}}{a+b+c+\frac{bc}{d}}
\left( k + \frac{bc}{d} \right)
&= \ol k + \frac{d}{bc}
\end{align*}
Adding $ad$ times the last line to the first line and cancelling $ad \ol k$ now gives
\[
\left( ad \cdot \frac{\frac1a+\frac1b+\frac1c+\frac{d}{bc}}%
{a+b+c+\frac{bc}{d}} + 1 \right) k
= a + d + \frac{ad^2}{bc} - abc \cdot
\frac{\frac1a+\frac1b+\frac1c+\frac{d}{bc}}{a+b+c+\frac{bc}{d}}
\]
or
\begin{align*}
\left( ad \left( \frac1a+\frac1b+\frac1c+\frac{d}{bc} \right)
+ a+b+c+\frac{bc}{d} \right) k
&= \left( a+b+c+\frac{bc}{d} \right)
\left( a + d + \frac{ad^2}{bc} \right) \\
&- abc \cdot \left( \frac1a+\frac1b+\frac1c+\frac{d}{bc} \right).
\end{align*}
We begin by simplifying the coefficient of $k$:
\begin{align*}
ad \left( \frac1a+\frac1b+\frac1c+\frac{d}{bc} \right)
+ a+b+c+\frac{bc}{d}
&= a+b+c+d + \frac{bc}{d}+\frac{ad}{b}+\frac{ad}{c} + \frac{ad^2}{bc} \\
&= a + \frac{bc}{d} + \left( 1 + \frac{ad}{bc} \right)(b+c+d) \\
&= \frac{ad+bc}{bcd} \left[ bc + d(b+c+d) \right] \\
&= \frac{(ad+bc)(d+b)(d+c)}{bcd}.
\end{align*}
Meanwhile, the right-hand side expands to
\begin{align*}
\text{RHS} &=
\left( a+b+c+\frac{bc}{d} \right)
\left( a + d + \frac{ad^2}{bc} \right)
- abc \cdot \left( \frac1a+\frac1b+\frac1c+\frac{d}{bc} \right) \\
&= \left( a^2+ab+ac+\frac{abc}{d} \right)
+ \left( da+db+dc+bc \right) \\
&\quad+ \left( \frac{a^2d^2}{bc} + \frac{ad^2}{c} + \frac{ad^2}{b} + ad \right)
- \left( ab+bc+ca+ad \right) \\
&= a^2 + d(a+b+c) + \frac{abc}{d} + \frac{a^2d^2}{bc}
+ \frac{ad^2}{b} + \frac{ad^2}{c} \\
&= a^2 + \frac{abc}{d} + d(a+b+c) \cdot \frac{ad+bc}{bc} \\
&= \frac{ad+bc}{bcd} \left[ abc+d^2(a+b+c) \right].
\end{align*}
Therefore, we get
\[ k = \frac{abc+d^2(a+b+c)}{(d+b)(d+c)}. \]
In particular,
\begin{align*}
k-a &= \frac{abc+d^2(a+b+c)-a(d+b)(d+c)}{(d+b)(d+c)} \\
&= \frac{d^2(b+c)-da(b+c)}{(d+b)(d+c)}
= \frac{d(b+c)(d-a)}{(d+b)(d+c)}.
\end{align*}
Now the corresponding point $G$ obeying $(\heartsuit)$ satisfies
\begin{align*}
\frac{g-(-d)}{0-(-d)} &= \frac{(a+b+c)-a}{k-a} \\
\implies g &= -d + \frac{d(b+c)}{k-a} \\
&= -d + \frac{(d+b)(d+c)}{d-a} = \frac{db+dc+bc+ad}{d-a}. \\
\implies bc \ol g &= \frac{bc \cdot \frac{ac+ab+ad+bc}{abcd}}{\frac{a-d}{ad}}
= -\frac{ab+ac+ad+bc}{d-a}. \\
\implies g + bc \ol g &= \frac{(d-a)(b+c)}{d-a} = b+c.
\end{align*}
Hence $G$ lies on $BC$ and this completes the proof.
\paragraph{Seventh solution using moving points (Zack Chroman)}
We state the converse of the problem as follows:
\begin{quote}
Take a point $D$ on $\Gamma$,
and let $G\in \Gamma$ such that $\ol{DG} \perp \ol{BC}$.
Then define $K$ to lie on $\ol{GH}, \ol{AD}$,
and take $L \in \ol{AD}$ such that $K$ is the midpoint of $\ol{AL}$.
Then if we define $E$ and $F$ as the projections of $L$ onto $\ol{AB}$ and $\ol{AC}$
we want to show that $E$, $H$, $F$ are collinear.
\end{quote}
%\begin{center}
% \includegraphics[scale=0.5]{DiagramNo}
%\end{center}
It's clear that solving this problem will solve the original.
In fact we will show later that each line $EF$ through $H$
corresponds bijectively to the point $D$.
We animate $D$ projectively on $\Gamma$
(hence $\deg D = 2$).
Since $D \mapsto G$ is a projective map $\Gamma \to \Gamma$,
it follows $\deg G = 2$.
By Zack's lemma, $\deg(\ol{AD}) \le 0 + 2 - 1 = 1$
(since $D$ can coincide with $A$),
and $\deg(\ol{HG}) \le 0 + 2 - 0 = 2$.
So again by Zack's lemma, $\deg K \le 1 + 2 - 1 = 2$,
since lines $AD$ and $GH$ can coincide once if $D$ is the reflection
of $H$ over $\ol{BC}$.
It follows $\deg L = 2$,
since it is obtained by dilating $K$ by a factor of $2$
across the fixed point $A$.
Let $\infty_C$ be the point at infinity
on the line perpendicular to $AC$, and similarly $\infty_B$.
Then \[ F = \ol{AC} \cap \ol{\infty_C L},
\quad E = \ol{AB} \cap \ol{\infty_B L}. \]
We want to use Zack's lemma again on line $\ol{\infty_B L}$.
Consider the case $G = B$;
we get $\ol{HG} \parallel \ol{AD}$,
so $ADGH$ is a parallelogram,
and then $K = L = \infty_B$.
Thus there is at least one $t$ where $L = \infty_B$
and by Zack's lemma we get
$\deg\left( \ol{\infty_B L} \right) \le 0 + 2 - 1 = 1$.
Again by Zack's lemma,
we conclude $\deg E \le 0 + 1 - 0 = 1$.
Similarly, $\deg F \le 1$.
We were aiming to show $E$, $F$, $H$ collinear
which is a condition of degree at most $1 + 1 + 0 = 2$.
So it suffices to verify the problem for three distinct choices of $D$.
\begin{itemize}
\item If $D=A$, then line $GH$ is line $AH$,
and $L = \ol{AD} \cap \ol{AH} = A$.
So $E=F=A$ and the statement is true.
\item If $D=B$, $G$ is the antipode of $C$ on $\Gamma$.
Then $K = \ol{HG} \cap \ol{AD}$ is the midpoint of $\ol{AB}$, so $L=B$.
Then $E=B$ and $F$ is the projection of $B$ onto $AC$,
so $E$, $H$, $F$ collinear.
\ii We finish similarly when $D=C$.
\end{itemize}
This completes the proof.
\begin{remark*}
Less careful approaches are possible
which give a worse bound on the degrees,
requiring to check (say) five choices of $D$ instead.
We present the most careful one showing $\deg D = 2$
for instructional reasons, but the others may be easier to find.
\end{remark*}
\pagebreak
\subsection{TSTST 2019/6, proposed by Nikolai Beluhov}
\textsl{Available online at \url{https://aops.com/community/p12608536}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Suppose $P$ is a polynomial with integer coefficients
such that for every positive integer $n$,
the sum of the decimal digits of $|P(n)|$
is not a Fibonacci number.
Must $P$ be constant?
\end{mdframed}
The answer is yes, $P$ must be constant.
By $S(n)$ we mean the sum of the decimal digits of $|n|$.
We need two claims.
\begin{claim*}
If $P(x) \in \ZZ[x]$ is nonconstant with
positive leading coefficient,
then there exists an integer polynomial $F(x)$
such that all coefficients of $P \circ F$
are positive except for the second one, which is negative.
\end{claim*}
\begin{proof}
We will actually construct a cubic $F$.
We call a polynomial \emph{good} if it has the property.
First, consider $T_0(x) = x^3+x+1$.
Observe that in $T_0^{\deg P}$,
every coefficient is strictly positive,
except for the second one, which is zero.
Then, let $T_1(x) = x^3 - \frac1D x^2 + x + 1$.
Using continuity as $D \to \infty$,
it follows that if $D$ is large enough (in terms of $\deg P$),
then $T_1^{\deg P}$ is good,
with $-\frac3D x^{3\deg P-1}$ being the only negative coefficient.
Finally, we can let $F(x) = CT_1(x)$
where $C$ is a sufficiently large multiple of $D$
(in terms of the coefficients of $P$);
thus the coefficients of $(CT_1(x))^{\deg P}$ dominate
(and are integers), as needed.
\end{proof}
\begin{claim*}
There are infinitely many Fibonacci numbers
in each residue class modulo $9$.
\end{claim*}
\begin{proof}
Note the Fibonacci sequence is periodic modulo $9$
(indeed it is periodic modulo any integer).
Moreover (allowing negative indices),
\begin{align*}
F_{0} = 0 &\equiv 0 \pmod 9 \\
F_{1} = 1 &\equiv 1 \pmod 9 \\
F_{3} = 2 &\equiv 2 \pmod 9 \\
F_{4} = 3 &\equiv 3 \pmod 9 \\
F_{7} = 13 &\equiv 4 \pmod 9 \\
F_{5} = 5 &\equiv 5 \pmod 9 \\
F_{-4} = -3 &\equiv 6 \pmod 9 \\
F_{9} = 34 &\equiv 7 \pmod 9 \\
F_{6} = 8 &\equiv 8 \pmod 9. \qedhere
\end{align*}
\end{proof}
We now show how to solve the problem with the two claims.
WLOG $P$ satisfies the conditions of the first claim,
and choose $F$ as above.
Let
\[ P(F(x)) = c_N x^N - c_{N-1} x^{N-1} + c_{N-2} x^{N-2} + \dots + c_0 \]
where $c_i > 0$ (and $N = 3 \deg P$).
Then if we select $x = 10^e$ for $e$ large enough
(say $x > 10\max_i c_i$),
the decimal representation $P(F(10^e))$ consists of the concatenation of
\begin{itemize}
\ii the decimal representation of $c_N-1$,
\ii the decimal representation of $10^e-c_{N-1}$
\ii the decimal representation of $c_{N-2}$,
with several leading zeros,
\ii the decimal representation of $c_{N-3}$,
with several leading zeros,
\ii \dots
\ii the decimal representation of $c_0$, with several leading zeros.
\end{itemize}
(For example,
if $P(F(x)) = 15x^3 - 7x^2 + 4x + 19$,
then $P(F(1000)) = 14{,}993{,}004{,}019$.)
Thus, the sum of the digits of this expression
is equal to
\[ S(P(F(10^e))) = 9e + k \]
for some constant $k$ depending only on $P$ and $F$,
independent of $e$.
But this will eventually hit a Fibonacci number by the second claim,
contradiction.
\begin{remark*}
It is important to control the number of negative coefficients
in the created polynomial.
If one tries to use this approach on a polynomial $P$
with $m > 0$ negative coefficients,
then one would require that the Fibonacci sequence
is surjective modulo $9m$ for any $m > 1$,
which is not true:
for example the Fibonacci sequence avoids all numbers
congruent to $4 \mod{11}$ (and thus $4 \mod{99}$).
In bases $b$ for which surjectivity modulo $b-1$ fails,
the problem is false.
For example, $P(x) = 11x+4$ will avoid all Fibonacci
numbers if we take sum of digits in base $12$,
since that base-$12$ sum is necessarily $4 \pmod{11}$,
hence not a Fibonacci number.
\end{remark*}
\pagebreak
\section{Solutions to Day 3}
\subsection{TSTST 2019/7, proposed by Ankan Bhattacharya}
\textsl{Available online at \url{https://aops.com/community/p12608512}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $f \colon \ZZ \to \{1, 2, \dots, 10^{100}\}$
be a function satisfying
\[ \gcd(f(x), f(y)) = \gcd(f(x), x-y) \]
for all integers $x$ and $y$.
Show that there exist positive integers $m$ and $n$ such that
$f(x) = \gcd(m + x, n)$ for all integers $x$.
\end{mdframed}
Let $\mathcal{P}$ be the set of primes not exceeding $10^{100}$.
For each $p \in \mathcal{P}$, let $e_p = \max_x \nu_p(f(x))$
and let $c_p \in \opname{argmax}_x \nu_p(f(x))$.
We show that this is good enough to compute all values of $x$,
by looking at the exponent at each individual prime.
\begin{claim*}
For any $p \in \mathcal P$, we have
\[ \nu_p(f(x)) = \min(\nu_p(x - c_p), e_p). \]
\end{claim*}
\begin{proof}
Note that for any $x$, we have
\[ \gcd(f(c_p), f(x)) = \gcd(f(c_p), x - c_p). \]
We then take $\nu_p$ of both sides
and recall $\nu_p(f(x)) \le \nu_p(f(c_p)) = e_p$;
this implies the result.
\end{proof}
This essentially determines $f$, and so now we just follow through.
Choose $n$ and $m$ such that
\begin{align*}
n &= \prod_{p \in \mathcal P} p^{e_p} \\
m &\equiv -c_p \pmod{p^{e_p}} \quad \forall p \in \mathcal P
\end{align*}
the latter being possible by Chinese remainder theorem.
Then, from the claim we have
\begin{align*}
f(x) &= \prod_{p \in \mathcal P} p^{\nu_p(f(x))}
= \prod_{p \mid n} p^{\min(\nu_p(x-c_p), e_p)} \\
&= \prod_{p \mid n} p^{\min(\nu_p(x+m), \nu_p(n))}
= \gcd\left( x+m, n \right)
\end{align*}
for every $x \in \ZZ$, as desired.
\begin{remark*}
The functions $f(x) = x$ and
$f(x) = |2x - 1|$ are examples satisfying the gcd equation
(the latter always being strictly positive).
Hence the hypothesis $f$ bounded cannot be dropped.
\end{remark*}
\begin{remark*}
The pair $(m, n)$ is essentially unique:
every other pair is obtained by
shifting $m$ by a multiple of $n$.
Hence there is not really any choice in choosing $m$ and $n$.
\end{remark*}
\pagebreak
\subsection{TSTST 2019/8, proposed by Ankan Bhattacharya}
\textsl{Available online at \url{https://aops.com/community/p12608780}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $\mathcal{S}$ be a set of $16$ points in the plane, no three collinear.
Let $\chi(\mathcal{S})$ denote the number of ways to
draw $8$ line segments with endpoints in $\mathcal{S}$,
such that no two drawn segments intersect, even at endpoints.
Find the smallest possible value of $\chi(\mathcal{S})$
across all such $\mathcal{S}$.
\end{mdframed}
The answer is $1430$.
In general, we prove that with $2n$ points
the answer is the $n$\ts{th} Catalan number
$C_n = \tfrac{1}{n+1}\tbinom{2n}{n}$.
First of all, it is well-known that if $\mathcal{S}$ is a convex $2n$-gon,
then $\chi(\mathcal{S}) = C_n$.
It remains to prove the lower bound.
We proceed by (strong) induction on $n$,
with the base case $n = 0$ and $n = 1$ clear.
Suppose the statement is proven for $0, 1, \dots, n$
and consider a set $\mathcal{S}$ with $2(n+1)$ points.
Let $P$ be a point on the convex hull of $\mathcal{S}$,
and label the other $2n+1$ points $A_1, \dots, A_{2n+1}$
in order of angle from $P$.
Consider drawing a segment $\ol{PA_{2k+1}}$.
This splits the $2n$ remaining points
into two halves $\mathcal{U}$ and $\mathcal{V}$,
with $2k$ and $2(n-k)$ points respectively.
\begin{center}
\begin{asy}
unitsize(50);
pair P = (0, 0);
pair[] A = {2*dir(200), 1.7*dir(215), 2.5*dir(230), 1.8*dir(240), 1.6*dir(260), 2.3*dir(275), 2.4*dir(285), 1.7*dir(295), 2.2*dir(310), 2.2*dir(330), 1.9*dir(345)};
dot(P);
for (int i = 0; i < A.length; ++i) dot(A[i]);
draw(P--A[4]);
draw(A[4]--(3*A[4]-2*P), dashed);
label("$P$", P, dir(90));
for (int i = 0; i < A.length; ++i) label("$A_{" + string(i+1) + "}$", A[i], dir(A[i]));
clip(box((-2.5, -3), (2.5, 2)));
\end{asy}
\end{center}
Note that by choice of $P$,
no segment in $\mathcal{U}$ can intersect a segment in $\mathcal{V}$.
By the inductive hypothesis,
\[\chi(\mathcal{U}) \ge C_k \quad \text{and} \quad \chi(\mathcal{V}) \ge C_{n-k}.\]
Thus, drawing $\ol{PA_{2k+1}}$, we have at least $C_k C_{n-k}$ ways to complete the drawing.
Over all choices of $k$, we obtain
\[\chi(\mathcal{S}) \ge C_0 C_n + \dots + C_n C_0 = C_{n+1}\]
as desired.
\begin{remark*}
It is possible to show directly from the lower bound proof
that convex $2n$-gons achieve the minimum:
indeed, every inequality is sharp,
and no segment $\ol{PA_{2k}}$ can be drawn
(since this splits the rest of the points into
two halves with an odd number of points,
and no crossing segment can be drawn).
Bobby Shen points out that in the case of $6$ points,
a regular pentagon with its center also achieves equality,
so this is not the only equality case.
\end{remark*}
\begin{remark*}
The result that $\chi(S) \ge 1$ for all $S$ is known
(consider the choice of $8$ segments with smallest sum),
and appeared on Putnam 1979.
However, it does not seem that knowing this
gives an advantage for this problem,
since the answer is much larger than $1$.
\end{remark*}
\pagebreak
\subsection{TSTST 2019/9, proposed by Ankan Bhattacharya}
\textsl{Available online at \url{https://aops.com/community/p12608472}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $ABC$ be a triangle with incenter $I$.
Points $K$ and $L$ are chosen on segment $BC$
such that the incircles of $\triangle ABK$ and $\triangle ABL$ are tangent at $P$,
and the incircles of $\triangle ACK$ and $\triangle ACL$ are tangent at $Q$.
Prove that $IP = IQ$.
\end{mdframed}
We present two solutions.
\paragraph{First solution, mostly elementary (original)}
Let $I_B$, $J_B$, $I_C$, $J_C$ be the incenters
of $\triangle ABK$, $\triangle ABL$,
$\triangle ACK$, $\triangle ACL$ respectively.
\begin{center}
\begin{asy}
unitsize(15);
real r1, r2;
path w1, w2;
pair J1 = (-0.5, 2.7);
pair J2 = (1, 3);
real r1 = abs(J1.y);
real r2 = abs(J2.y);
path w1 = CR(J1, r1);
path w2 = CR(J2, r2);
pair X1 = intersectionpoints(w1, w2)[0];
pair X2 = reflect(J1, J2)*X1;
pair H = extension((1.9, 0), (2, 1), X1, X2);
pair P = intersectionpoints(CR(H, sqrt(abs(H-X1)*abs(H-X2))), w1)[1];
pair Q = intersectionpoints(CR(H, sqrt(abs(H-X1)*abs(H-X2))), w2)[0];
pair I = extension(J1, P, J2, Q);
pair B = extension(J1, P, (0, 0), (1, 0));
pair C = extension(J2, Q, (0, 0), (1, 0));
pair A = extension(B, reflect(B, I) * C, C, reflect(C, I) * B);
pair K = extension(B, C, A, reflect(A, J2) * C);
pair L = extension(B, C, A, reflect(A, J1) * B);
pair I_B = incenter(A, B, K);
pair J_B = incenter(A, B, L);
pair I_C = incenter(A, C, K);
pair J_C = incenter(A, C, L);
pair R = extension(P, Q, B, C);
filldraw(A--B--C--cycle, opacity(0.1)+lightcyan, blue);
draw(incircle(A, B, K)^^incircle(A, C, L), deepcyan);
draw(L--A--K, blue);
draw(w1^^w2, deepcyan);
draw(I--P^^I--Q, red);
draw(B--P^^C--Q, orange);
draw(Q--R--B, deepgreen);
draw(J_C--R, deepgreen+dashed);
draw(I_C--R, deepgreen+dashed);
dot("$A$", A, dir(A-I));
dot("$B$", B, dir(230));
dot("$C$", C, dir(310));
dot("$I$", I, dir(2*I-P-Q));
dot("$K$", K, dir(270));
dot("$L$", L, dir(270));
dot("$P$", P, dir(80));
dot("$Q$", Q, dir(20));
dot("$R$", R, dir(-90));
dot("$I_B$", I_B, dir(-90));
dot("$I_C$", I_C, dir(-90));
dot("$J_B$", J_B, dir(-90));
dot("$J_C$", J_C, dir(-90));
\end{asy}
\end{center}
We begin with the following claim which does not depend
on the existence of tangency points $P$ and $Q$.
\begin{claim*}
Lines $BC$, $I_BJ_C$, $J_BI_C$ meet at a point $R$
(possibly at infinity).
\end{claim*}
\begin{proof}
By rotating by $\half \angle A$ we have the equality
\[ A(BI; I_B J_B) = A(IC;I_C J_C). \]
It follows $(BI; I_B J_B) = (IC; I_C J_C) = (CI; J_C I_C)$.
(One could also check directly that both cross ratios equal
$\frac{\sin \angle BAK/2}{\sin \angle CAK/2}
\div \frac{\sin \angle BAL/2}{\sin \angle CAL/2}$,
rather than using rotation.)
Therefore, the concurrence follows from the so-called
\emph{prism lemma} on $\ol{I B I_B J_B}$ and $\ol{I C J_C I_C}$.
\end{proof}
%\[ (B I; I_B J_B)
% = \frac{\sin \angle I_B A B}{\sin \angle I_B A I}
% \div \frac{\sin \angle J_B A B}{\sin \angle J_B A I}
% = \frac{\sin \tfrac12 \angle BAK}{\sin \tfrac12 \angle CAK}
% \div \frac{\sin \tfrac12 \angle BAL}{\sin \tfrac12 \angle CAL}.
% \]
% Similarly
% \[ (C I; J_C I_C)
% = \frac{\sin \angle J_C A C}{\sin \angle J_C A I}
% \div \frac{\sin \angle I_C A C}{\sin \angle I_C A I}
% = \frac{\sin \tfrac12 \angle CAL}{\sin \tfrac12 \angle BAL}
% \div \frac{\sin \tfrac12 \angle CAK}{\sin \tfrac12 \angle BAK}.
% \]
%
%\begin{proof}
% Note $\angle BAI_B = \angle IAI_C$
% and $\angle I_BAI = \angle I_CAC$.
% Then
% \[\frac{BI_B}{I_BI} \div \frac{II_C}{I_CC}
% = \left(\frac{BA}{AI} \cdot \frac{\sin \angle BAI_B}{\sin \angle I_BAI}\right)
% \div \left(\frac{IA}{AC} \cdot \frac{\sin \angle IAI_C}{\sin \angle I_CAC}\right)\\
% = \frac{BA \cdot AC}{AI^2}.\]
% In the same way,
% we obtain
% \[\frac{BI_B}{I_BI} \div \frac{II_C}{I_CC}
% = \frac{BJ_B}{J_BI} \div \frac{IJ_C}{J_CC}
% \implies
% \frac{BI_B}{I_BI} \cdot \frac{IJ_C}{J_CC}
% = \frac{BJ_B}{J_BI} \cdot \frac{II_C}{I_CC}\]
% and we're done by Menelaus.
%\end{proof}
\begin{remark*}[Nikolai Beluhov]
This result is known;
it appears as {4.5.32} in Akopyan's \emph{Geometry in Figures}.
The cross ratio is not necessary to prove this claim:
it can be proven by length chasing
with circumscribed quadrilaterals.
(The generalization mentioned later also admits a trig-free proof
for the analogous step.)
\end{remark*}
We now bring $P$ and $Q$ into the problem.
\begin{claim*}
Line $PQ$ also passes through $R$.
\end{claim*}
\begin{proof}
Note $(BP; I_BJ_B) = -1 = (CQ; J_CI_C)$,
so the conclusion again follows by prism lemma.
\end{proof}
% \begin{corollary*}
% The inversion at $R$
% swapping the incircles
% of $\triangle ABK$ and $\triangle ACL$
% also swaps $P$ and $Q$.
% \end{corollary*}
We are now ready to complete the proof.
Point $R$ is the exsimilicenter of
the incircles of $\triangle ABK$ and $\triangle ACL$,
so $\tfrac{PI_B}{RI_B} = \tfrac{QJ_C}{RJ_C}$.
Now by Menelaus,
\[\frac{I_BP}{PI} \cdot \frac{IQ}{QJ_C} \cdot \frac{J_CR}{RI_B} = -1
\implies IP = IQ.\]
\begin{remark*}[Author's comments on drawing the diagram]
Drawing the diagram directly is quite difficult.
If one draws $\triangle ABC$ first,
they must locate both $K$ and $L$,
which likely involves some trial and error
due to the complex interplay between the two points.
There are alternative simpler ways.
For example, one may draw $\triangle AKL$ first;
then the remaining points $B$ and $C$ are not related
and the task is much simpler
(though some trial and error is still required).
In fact, by breaking symmetry,
we may only require one application of guesswork.
Start by drawing $\triangle ABK$ and its incircle;
then the incircle of $\triangle ABL$ may be constructed,
and so point $L$ may be drawn.
Thus only the location of point $C$ needs to be guessed.
I would be interested in a method
to create a general diagram without any trial and error.
\end{remark*}
\paragraph{Second solution, inversion (Nikolai Beluhov)}
As above, the lines $BC$, $I_BJ_C$, $J_BI_C$ meet at some point $R$
(possibly at infinity).
Let $\omega_1$, $\omega_2$, $\omega_3$, $\omega_4$ be the incircles
of $\triangle ABK$, $\triangle ACL$, $\triangle ABL$, and $\triangle ACK$.
\begin{claim*}
There exists an inversion $\iota$ at $R$
swapping $\{\omega_1, \omega_2\}$
and $\{\omega_3, \omega_4\}$.
\end{claim*}
\begin{proof}
Consider the inversion at $R$
swapping $\omega_1$ and $\omega_2$.
Since $\omega_1$ and $\omega_3$ are tangent,
the image of $\omega_3$ is tangent to $\omega_2$
and is also tangent to $BC$.
The circle $\omega_4$ is on the correct side of $\omega_3$
to be this image.
\end{proof}
\begin{claim*}
Circles $\omega_1$, $\omega_2$, $\omega_3$, $\omega_4$
share a common radical center.
\end{claim*}
\begin{proof}
Let $\Omega$ be the circle with center $R$
fixed under $\iota$,
and let $k$ be the circle through $P$
centered at the radical center of $\Omega$, $\omega_1$, $\omega_3$.
Then $k$ is actually orthogonal to $\Omega$, $\omega_1$, $\omega_3$,
so $k$ is fixed under $\iota$
and $k$ is also orthogonal to $\omega_2$ and $\omega_4$.
Thus the center of $k$ is the desired radical center.
\end{proof}
The desired statement immediately follows.
Indeed, letting $S$ be the radical center,
it follows that $\ol{SP}$ and $\ol{SQ}$
are the common internal tangents to $\{\omega_1, \omega_3\}$ and $\{\omega_2, \omega_4\}$.
Since $S$ is the radical center,
$SP = SQ$.
In light of $\angle SPI = \angle SQI = 90^{\circ}$,
it follows that $IP = IQ$, as desired.
\begin{remark*}[Nikolai Beluhov]
There exists a circle tangent to all four incircles,
because circle $k$ is orthogonal to all four,
and line $BC$ is tangent to all four;
thus the inverse of line $BC$ in $k$ is a circle
tangent to all four incircles.
The amusing thing here is that Casey's theorem is completely unhelpful
for proving this fact:
all it can tell us is that there is a line or circle tangent to these incircles,
and line $BC$ already satisfies this property.
\end{remark*}
\begin{remark*}[Generalization by Nikolai Beluhov]
The following generalization holds:
\begin{quote}
Let $ABCD$ be a quadrilateral
circumscribed about a circle with center $I$.
A line through $A$ meets $\overrightarrow{BC}$ and $\overrightarrow{DC}$
at $K$ and $L$;
another line through $A$ meets $\overrightarrow{BC}$ and $\overrightarrow{DC}$
at $M$ and $N$.
Suppose that the incircles of $\triangle ABK$ and $\triangle ABM$ are tangent at $P$,
and the incircles of $\triangle ACL$ and $\triangle ACN$ are tangent at $Q$.
Prove that $IP = IQ$.
\end{quote}
The first approach can be modified to the generalization.
There is an extra initial step required:
by Monge, the exsimilicenter of the incircles of $\triangle ABK$ and $\triangle ADN$
lies on line $BD$;
likewise for the incircles of $\triangle ABL$ and $\triangle ADM$.
Now one may prove using the same trig approach that these pairs of incircles
have a common exsimilicenter,
and the rest of the solution plays out similarly.
The second approach can also be modified in the same way,
once we obtain that a common exsimilicenter exists.
(Thus in the generalization, it seems we also get
there exists a circle tangent to all four incircles.)
\end{remark*}
\pagebreak
\end{document}