Maths Olympiad Prep

Library / /112 of 520

Number theory Difficulty 5.8 AIME, harder Prove it

Let SS be a set of 100 positive integers 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 each of the other 99 numbers of SS.

Solution

Alternative Solution by PSC. Order the elements of SS as x1<x2<⋯<x100x_{1}<x_{2}<\cdots<x_{100}.

For 2⩽k⩽972 \leqslant k \leqslant 97, looking at the quadruples (x1,xk,xk+1,xk+2)\left(x_{1}, x_{k}, x_{k+1}, x_{k+2}\right) and (x1,xk,xk+1,xk+3)\left(x_{1}, x_{k}, x_{k+1}, x_{k+3}\right), we get that x1∣xkx_{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 5⩽k⩽1005 \leqslant k \leqslant 100, looking at the quadruples (x1,xk−2,xk−1,xk)\left(x_{1}, x_{k-2}, x_{k-1}, x_{k}\right) and (x1,xk−3,xk−1,xk)\left(x_{1}, x_{k-3}, x_{k-1}, x_{k}\right) we get that x1∣xkx_{1} \mid x_{k} as alternatively, we would have xk=x1+xk−2+xk−1=x1+xk−3+xk−1x_{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.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.