Maths Olympiad Prep

Library / /21 of 43

Number theory Difficulty 5.8 AIME, harder Prove it JBMO

Problem:

Let SS be a set of 100 positive integer numbers having the following property:
"Among every four numbers of SS, there is a number which divides each of the other three or there is a number which is equal to the sum of the other three."
Prove that the set SS contains a number which divides all other 99 numbers of SS.

Solutions — 3

Solution 1

Solution:

Let a<ba < b be the two smallest numbers of SS and let dd be the largest number of SS. Consider any two other numbers x<yx < y of SS. For the quadruples (a,b,x,d)(a, b, x, d) and (a,b,y,d)(a, b, y, d) we cannot get both of d=a+b+xd = a + b + x and d=a+b+yd = a + b + y, since a+b+x<a+b+ya + b + x < a + b + y. From here, we get aba \mid b and ada \mid d.

Consider any number ss of SS different from a,b,da, b, d. From the condition of the problem, we get d=a+b+sd = a + b + s or aa divides b,sb, s and dd. But since we already know that aa divides bb and dd anyway, we also get that asa \mid s, as in the first case we have s=dabs = d - a - b. This means that aa divides all other numbers of SS.

Solution 2

Solution:

Order the elements of SS as x1<x2<<x100x_{1} < x_{2} < \cdots < x_{100}.

For 2k972 \leqslant k \leqslant 97, looking at the quadruples (x1,xk,xk+1,xk+2)(x_{1}, x_{k}, x_{k+1}, x_{k+2}) and (x1,xk,xk+1,xk+3)(x_{1}, x_{k}, x_{k+1}, x_{k+3}), we get that x1xkx_{1} \mid x_{k} as alternatively, we would have xk+2=x1+xk+xk+1=xk+3x_{k+2} = x_{1} + x_{k} + x_{k+1} = x_{k+3}, a contradiction.

For 5k1005 \leqslant k \leqslant 100, looking at the quadruples (x1,xk2,xk1,xk)(x_{1}, x_{k-2}, x_{k-1}, x_{k}) and (x1,xk3,xk1,xk)(x_{1}, x_{k-3}, x_{k-1}, x_{k}) we get that x1xkx_{1} \mid x_{k} as alternatively, we would have xk=x1+xk2+xk1=x1+xk3+xk1x_{k} = x_{1} + x_{k-2} + x_{k-1} = x_{1} + x_{k-3} + x_{k-1}, a contradiction.

So x1x_{1} divides all other elements of SS.

Solution 3

Solution:

The condition that one element is the sum of the other three cannot be satisfied by all quadruples. So we have four elements such that one divides the other three. Suppose inductively that we have a subset SS' of SS with S=k4|S'| = k \geqslant 4 such that there is xSx \in S' with xyx \mid y for every ySy \in S'. Pick sSSs \in S \setminus S' and y,zSy, z \in S' different from xx. Considering (s,x,y,z)(s, x, y, z) either sxs \mid x, or xsx \mid s or one of the four is a sum of the other three. In the last case we have s=±x±y±zs = \pm x \pm y \pm z and so xsx \mid s. In any case either xx or ss divides all elements of S{s}S' \cup \{s\}.

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.