Maths Olympiad Prep

Library / /16 of 41

Number theory Difficulty 8.2 Shortlist Prove it Slovenia

Let nn be a positive integer. n3n \ge 3. There are nn pairwise different numbers written on a blackboard. Show that we can choose two of those numbers so that no number from the blackboard multiplied by 33 is equal to a multiple of their sum.

Solution

Denote the numbers by a1,a2,,ana_1, a_2, \dots, a_n. Without loss of generality we may assume that a1>a2>>ana_1 > a_2 > \dots > a_n. Let us show we may also assume that not all of these numbers are divisible by 33. If b1,,bnb_1, \dots, b_n are all divisible by 33, then there exists a positive integer kk such that 3k3^k divides bjb_j for all j=1,,nj = 1, \dots, n, as well as a positive integer ll such that 3k+13^{k+1} does not divide blb_l. If this is the case, then a1=b13k,,an=bn3ka_1 = \frac{b_1}{3^k}, \dots, a_n = \frac{b_n}{3^k} are pairwise different positive integers, which are not all divisible by 33. Assume that there exist two among them, such that ai+aja_i + a_j does not divide any of the numbers 3a1,,3an3a_1, \dots, 3a_n. Then 3k(ai+aj)=bi+bj3^k(a_i + a_j) = b_i + b_j does not divide 3k(3a1)=3b1,,3k(3an)=3bn3^k(3a_1) = 3b_1, \dots, 3^k(3a_n) = 3b_n.

Let a1>a2>>ana_1 > a_2 > \dots > a_n and assume a1,,ana_1, \dots, a_n are not all divisible by 33. We will prove the claim by contradiction. If the claim is not true, then for every sum ai+aja_i + a_j there exists an index kijk_{ij} such that 3akij3a_{k_{ij}} is a multiple of this sum. In particular, this holds for i=1i = 1, so ai+a1a_i + a_1 divides 3aki13a_{k_{i1}} for some kk. If ai+a1a_i + a_1 is not divisible by 33, then ai+a1a_i + a_1 divides aki1a_{k_{i1}}. This is impossible since ai+a1>aki1a_i + a_1 > a_{k_{i1}}. So, 33 divides ai+a1a_i + a_1 for all 2in2 \le i \le n. At least one of the numbers is not divisible by 33 which implies none of them are and a2,,ana_2, \dots, a_n all give the same remainder when divided by 33.

This remainder is non-zero, so ai+a2a_i + a_2 is not divisible by 33 for i=3,,ni = 3, \dots, n. Now, ai+a2a_i + a_2 divides 3aki23a_{k_{i2}}, so ai+a2a_i + a_2 divides aki2a_{k_{i2}}. This is only possible if ki2=1k_{i2} = 1. Hence, a3+a2,,an+a2a_3 + a_2, \dots, a_n + a_2 all divide a1a_1.

We know that (a1+a2)l=3am(a_1 + a_2)l = 3a_m for some mm and some positive integer ll. Obviously, l3l \ge 3 implies (a1+a2)l>3a1>3am(a_1 + a_2)l > 3a_1 > 3a_m, so l=1l = 1 or l=2l = 2. If l=2l = 2, then 3am=2(a1+a2)>4a23a_m = 2(a_1 + a_2) > 4a_2, which would imply m=1m = 1 and a1=2a2a_1 = 2a_2. We have shown that a2+a3a_2 + a_3 divides a1a_1 and when a1=2a2a_1 = 2a_2 we have 2(a2+a3)=a1+2a3>a12(a_2 + a_3) = a_1 + 2a_3 > a_1, so a2+a3=a1=2a2a_2 + a_3 = a_1 = 2a_2 or a2=a3a_2 = a_3. This is not possible since all the numbers on the blackboard are different. We conclude that l=1l = 1.

We have shown that a1+a2=3ama_1 + a_2 = 3a_m for some mm. Since
3am=a1+a2a2+a3+a3>3a3 3a_m = a_1 + a_2 \ge a_2 + a_3 + a_3 > 3a_3
we have m<3m < 3. If m=1m = 1 then a1=2a2a_1 = 2a_2, but this is not possible since a1>a2a_1 > a_2. Hence m=2m = 2 and a1=2a2a_1 = 2a_2. As above, since 2(a2+a3)=a1+2a3>a12(a_2 + a_3) = a_1 + 2a_3 > a_1 and a2+a3a_2 + a_3 divides a1a_1, we have a2+a3=a1=2a2a_2 + a_3 = a_1 = 2a_2 or a2=a3a_2 = a_3. This contradicts the assumption that all numbers are different.

We have arrived at a contradiction and we can conclude that it is always possible to choose two of the numbers so that any other number from the board multiplied by 33 is different from their sum.

Want a route through all this instead of 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 reproduced verbatim; metadata (topic, difficulty) added by this project.