\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Shortlist 1990/13}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 22}
\maketitle
\section*{Problem}
Fix positive integers $a$ and $b$.
An eccentric mathematician has a ladder with $n$
rungs that he always ascends and descends in the following way:
when he ascends, each step he takes covers $a$ rungs of the ladder,
and when he descends, each step he takes covers $b$ rungs of the ladder.
By a sequence of ascending and descending steps he can climb from ground level
to the top rung of the ladder and come back down to ground level again.
Find, with proof, the minimum value of $n$, expressed in terms of $a$ and $b$.
\section*{Video}
\href{https://www.youtube.com/watch?v=cJeiPzJcVog&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/cJeiPzJcVog}}
\section*{External Link}
\url{https://aops.com/community/p1225228}
\newpage
\section*{Solution}
The answer is $a + b - \gcd(a,b)$.
We will only solve the case where $\gcd(a,b) = 1$
because the general answer follows by a suitable homothety on the ladder.
In other words, we will assume $\gcd(a,b)=1$
and show the answer is $a+b-1$.
To prove $n=a+b-1$ is possible, we use the following algorithm
to ascend to the top of the ladder
(the descent is symmetric).
\begin{itemize}
\ii The mathematician goes up by $a$ if possible.
\ii Otherwise he goes down by $b$;
this must be possible since there are at least $n-(a-1)=b$ rungs below him.
\ii To show this works,
note that if the mathematician ever visits the same rung twice,
then he must have had at least $a$ descents (and at least $b$ ascents).
Since $\gcd(a,b)=1$, this means the mathematician
visited a rung in every residue class modulo $a$.
But if they had visited the rung which was $b-1 \pmod a$,
then they reach the top of the ladder.
\end{itemize}
We now prove that $n < a+b-1$ isn't possible by contradiction.
Given a trip with total displacement $0$, again,
this means that the mathematician took at least $a$ descents and $b$ ascents,
and hit every residue class modulo $a$ or $b$.
WLOG, let's assume $a \ge b$, and consider the rung $n-a+1$.
It is the only rung which is $n-1 \pmod a$, so it must have been visited
but there are no legal moves from this rung, a contradiction.
\end{document}