## Task A-3.5.

Determine the smallest natural number $n$ such that in every set consisting of $n$ integers, there exist three distinct elements $a, b$, and $c$ such that $a b + b c + c a$ is divisible by 3.
## Solution.

Consider the maximum number of elements a set can have in which there do not exist three distinct elements $a, b$, and $c$ such that $a b + b c + c a$ is divisible by 3. Let $S$ be such a set with the maximum number of elements.

If the set $S$ contained two numbers that are divisible by 3, let's call them $a$ and $b$, then for any third number $c$ in the set, the expression $a b + b c + c a$ would be divisible by 3. Therefore, $S$ can contain at most one number divisible by 3.

1 point

Now consider three numbers $a, b$, and $c$ none of which are divisible by 3. If all three numbers give the same remainder when divided by 3, then the expression $a b + b c + c a$ is divisible by 3.

This means that at most two elements of the set $S$ can give a remainder of 1 when divided by 3, and at most two elements can give a remainder of 2.

Therefore, $S$ can have at most 5 elements.

It remains to verify that it is possible for $S$ to have exactly 5 elements (i.e., that our bound is not too loose).

Consider a set where one number is divisible by 3, two give a remainder of 1, and two give a remainder of 2 when divided by 3. Let $a, b$, and $c$ be three numbers from this set.

If exactly one of the numbers $a$, $b$, and $c$ is divisible by 3, then the expression $a b + b c + c a$ is not divisible by 3.

If two of these three numbers give a remainder of 1 and the third gives a remainder of 2, or if two of these three numbers give a remainder of 2 and the third gives a remainder of 1, then $a b + b c + c a$ gives a remainder of 2 when divided by 3, i.e., the expression $a b + b c + c a$ is not divisible by 3. This completes the verification.

We conclude that the smallest desired $n$ is 6.