Olympiad Maths Prep

Library / /23 of 45

Number theory Difficulty 6.0 National olympiad Prove it Ukraine

Positive integers a1,a2,...,a101a_1, a_2, ..., a_{101} are such that ai+1a_i + 1 are divisible by ai+1a_{i+1} for 1i1011 \le i \le 101 (we assume that a102=a1a_{102} = a_1). What is the largest value that the maximum of these numbers can attain?

Solution

Without loss of generality, let a101a_{101} be the largest of these numbers (or one of the largest). It is clear that ai+1ai+1a_i + 1 \ge a_{i+1} for any i=1,100i = 1, 100. If we add all these 100 inequalities, we get a1+a2+...+a100+100a2+a3+...+a101a_1 + a_2 + ... + a_{100} + 100 \ge a_2 + a_3 + ... + a_{101}, that is a1a101100a_1 \ge a_{101} - 100. From the condition a101+1a_{101} + 1 is divisible by a1a_1, and from the fact that a101a_{101} is the largest we have a101+1>a1a_{101} + 1 > a_1, so a101+12a12(a101100)=2a101200a_{101} + 1 \ge 2a_1 \ge 2(a_{101} - 100) = 2a_{101} - 200, therefore a101201a_{101} \le 201. It remains to show that there is an example where the maximum is equal to 201. Indeed, consider the set 101, 102, ..., 201, for it ai+1=ai+1a_i + 1 = a_{i+1} for i=1,100i = 1, 100 and a101+1=2a1a_{101} + 1 = 2a_1, so this example satisfies the problem.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.