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, where $ a$ and $ b$ are fixed positive integers. 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.$
Problem
Source: IMO ShortList 1990, Problem 13 (IRE)
Tags: number theory, relatively prime, recurrence relation, counting, Frobenius, IMO Shortlist
tjhance
17.08.2008 04:03
I claim the answer is $ a+b-\gcd(a,b)$. First we will cover the case with $ a$ and $ b$ being relatively prime, so we wish to prove that the answer is $ a+b-1$.
Assume there are $ n$ rungs, with $ n<a+b-1$. Then there are $ n+1$ total possible spots for the mathematician, (we include the "ground floor" as a spot). below the rungs. Now suppose there exists a cycle for this mathematician, such that he can start at one rung and end up back at that rung, and consider the smallest such cycle. If he makes $ x$ ascending steps and $ y$ descending steps, then $ xa=yb$. We assume $ a$ and $ b$ are relatively prime here, so the minimum possible value of $ x$ is $ b$, and the minimum possible value of $ y$ is $ a$. Thus this cycle includes at least $ a+b$ steps. If $ n<a+b-1$, then there are at most $ a+b-1$ possible spots for the mathematician. Hence he must have visited one of these places twice, but that means there is a smaller subcycle within his path, but this subcycle cannot exists as we are assuming this cycle is minimal, a contradiction.
So we must have $ n\ge a+b-1$. Now I will show that it is indeed possible to have $ n=a+b-1$. On a ladder with $ a+b-1$ rungs, there are $ a+b$ possible spots for the mathematician (again, this includes the ground floor). It is always possible for the mathematician to make a move no matter what rung he is on; to see this, suppose he is on the $ i^{th}$ rung. If $ i\le b-1$, then he can ascend $ a$ rungs, and if $ i\ge b$, then he can descend $ b$ rungs. Since he can move indefinitely, there must be some cycle he can make. As proven above, there cannot be a cycle within at most $ a+b-1$ spots, so this cycle must include the ground floor and the top $ (a+b-1)^{th}$ rung. This path is the one we wished to find.
Now suppose $ a$ and $ b$ are not relatively prime. Then we know that $ \gcd(a,b)|n$, and we can think of each set of $ \gcd(a,b)$ rungs as a single rung, so it is like we have $ \frac{n}{\gcd(a,b)}$ total rungs, and each ascending step is $ \frac{a}{\gcd(a,b)}$ rungs and each descending step is $ \frac{b}{\gcd(a,b)}$ rungs. Then the minimum number of these "big rungs" is $ \frac{a}{\gcd(a,b)}+\frac{b}{\gcd(a,b)}-1$. To find the total number of rungs, we just multiply back the $ \gcd(a,b)$ to get $ a+b-\gcd(a,b)$ as the minimum number of rungs.
yunustuncbilek
02.03.2013 01:14
tjhance wrote: Now suppose there exists a cycle for this mathematician, such that he can start at one rung and end up back at that rung, and consider the smallest such cycle. If he makes $ x$ ascending steps and $ y$ descending steps, then $ xa=yb$. We assume $ a$ and $ b$ are relatively prime here, so the minimum possible value of $ x$ is $ b$, But, what if such a cycle doesn't exist?
Arc_archer
22.05.2018 14:27
yunustuncbilek wrote: tjhance wrote: Now suppose there exists a cycle for this mathematician, such that he can start at one rung and end up back at that rung, and consider the smallest such cycle. If he makes $ x$ ascending steps and $ y$ descending steps, then $ xa=yb$. We assume $ a$ and $ b$ are relatively prime here, so the minimum possible value of $ x$ is $ b$, But, what if such a cycle doesn't exist? Eventually,if he wants to get back
L567
19.11.2021 12:57
Solved with Aayuu We claim that the answer is $\boxed{a+b-\gcd (a,b)}$. By bezout's lemma we may find $x,y \geq 0$ with $ax-by=\gcd(a,b)$. Then we have $b(y+1)-a(x-1)=a+b-\gcd(a,b)$, and it is clear that we can perform such a sequence of moves (if we are ever "stuck" then we would have $ka<b$ which is obviously impossible). This shows that the answer works. Suppose now that we have $n<a+b-1$. Considering all the moves in total, we have $ax=by$ for some $x,y \in\mathbb{Z}$, which implies that we move down atleast $a$ times and similarly move up atleast $b$ times. Since $\gcd(a,b)=1$, $b \cdot k$ (for $k \in \{0,1,\dots,a-1\})$ forms a complete residue system modulo $a$, so we would necessarily have the height be $b-1 \pmod a$ at some point. But since $n<a+b-1$, we have no legal move at this point which is obviously a contradiction. This completes the proof and we are done. $\blacksquare$
v_Enhance
26.04.2023 01:00
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). The mathematician goes up by $a$ if possible. Otherwise he goes down by $b$; this must be possible since there are at least $n-(a-1)=b$ rungs below him. 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. 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.