Say $0\leq a<b<c$. Let $d = \gcd(ab+1,bc+1,ca+1)$. We have $d \mid (ca+1) - (ab+1) = a(c-b)$, and since $\gcd(a,ab+1)=1$ it follows $d \mid c-b$. Similarly $d \mid b-a$, so $b=a+kd$, $c=b+\ell d$, thus $b\geq a+d$ and $c\geq b+d \geq a+2d$. It follows $\frac {a+b+c} {3} \geq a+d \geq d$. Equality can only occur if $a=0$, and then $d \mid a^2+1 = 1$, so $(a,b,c)=(0,1,2)$.

another solution it's easy to prove that $d||b-c|,|c-a|,|a-b|$, let us suppose $a<b<c$,consider the contrary side and obtain $b-a,c-b>\frac{a+b+c}{3}$ adding them yields $c>5a+2b$,on the other hand, $2b>4a+c$ so $c>5a+2b>9a+c$,a contradiction!

Here is yet a third solution to this very interesting problem. Let $\gcd(ab+1,ac+1,bc+1)=k$. Then $ab, bc, ca\equiv -1\pmod k$, so $(abc)^2\equiv -1\pmod k$. Now suppose $-1$ is a quadratic residue modulo $k$. Then there exists an integer $0\leq x\leq k-1$ such that $abc\equiv x\pmod k$. Since $ab\equiv -1\pmod k$, we have $abc\equiv -c\pmod k$, and as $k\nmid ab$ it follows that $c\equiv -x\pmod k$. Similarly, $a$ and $b$ are both congruent to $-x\pmod k$, so $a\equiv b\equiv c\pmod k$. Now WLOG let $a<b<c$. Then $b\geq a+k$ and $c\geq a+2k$, so \[a+b+c\geq a+(a+k)+(a+2k)=3a+3k\geq 3k,\] as desired.

Same as #4; posting for storage. Let $d=\gcd(ab+1,ac+1,bc+1)$ and WLOG let $a<b<c.$ Notice $$ab\equiv ac\equiv bc\equiv -1\pmod{d}$$so $a(b-c)\equiv 0\pmod{d}.$ We see $$\gcd(a,d)=\gcd(a,ab-1,ac-1,bc-1)=1$$so $b\equiv c\pmod{d}.$ Similarly, $a\equiv b\equiv c\pmod{d}$ and $a\le b+d\le c+2d.$ Substituting into $a+b+c$ yields the desired result. $\square$

The problem is wrong!!!!! It should ask you to prove that the left side is strictly less than the right side, since, if the equality occurs, the smallest of the three numbers has to be 0, but 0 is not a natural number

zuat.e wrote: The problem is wrong!!!!! It should ask you to prove that the left side is strictly less than the right side, since, if the equality occurs, the smallest of the three numbers has to be 0, but 0 is not a natural number But it don't makes problem wrong... If $x<y$ then condition $x \leq y$ is also right!

Thanks, I didn't think about that, but come on, it's an olympiad, it should ask you to squeeze the problem to its maximum.

I think in Russia $0$ is considered a natural number (I'm not entirely sure, so don't quote me on this)

Small variation to #2: $$d \mid c(ab+1)-b(ac+1)=c-b.$$

Let $g = \gcd(ab+1, ac+1, bc+1)$, and assume WLOG $a < b < c$. Note that $g \mid a-b, b-c$. If the statement doesn't hold, then we must have $2b> 4a+c, 2c>4b+a$ by $b-a, c-b > \frac{a+b+c}{3}$. But then $$2c > 4b+a = 2(2b)+a > 2(4a+c)+a = 2c+9a,$$contradiction. $\square$