IMO 1990 SL 13

Origin: IRE

Problem

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.

Solution

We will call the ground the “zeroth” rung. We will prove that the minimum n is n = a+b−(a, b). It is plain that if (a, b) = k > 1, the scientist can climb

only onto the rungs divisible by k and we can just observe these rungs to obtain the situation equivalent to a′ = a/k, b′ = b/k, and n′ = a′ + b′ −1. Thus let us assume that (a, b) = 1 and show that n = a + b −1. We obviously have n > a. Consider n = a + b −k, k \geq1, and let us assume without loss of generality that a > b (otherwise, we can reverse the problem starting from the top rung in our round trip). Then we can uniquely define the numbers ri, 0 \leqri < b, by ri \equivia (mod b). We now describe the only possible sequence of moves. From a position 0 \leqp \leqb−k we can move only a rungs upward and for p > b −1 we can move only b rungs downward. If we end up at b −k < p \leqb −1, we are stuck. Hence, given that we are at ri, if ri \leqb −k, we can move to a + ri, and when we descend as far as we can go we will end up at ri+1 \equiva + ri (mod b). If the mathematician climbs to the highest rung and then comes back to ri = 0, then we deduce b | ia, so i \geqb. But since (a, b) = 1, there exists 0 < j < b such that rj \equivja \equivb −1 (mod b). Thus the mathematician has visited the position b −1. For him not to get stuck we must have k \leq1 and n \geqa + b −1. For n = a + b −1 by induction he can come to any position ri, i \geq0, so he eventually comes to rj = b −1, climbs to the highest rung, and then continues until he gets to rb = 0. Hence the answer to the problem is n = a + b −1.