5. Zadatak

Promotrimo koliko najviše elemenata može imati skup u kojem ne postoje tri različita elementa $a$, $b$ i $c$ takva da je $ab+bc+ca$ djeljivo sa $3$. Neka je $S$ takav skup s najviše elemenata.

Ako bi skup $S$ sadržavao dva broja koja su djeljiva sa $3$, nazovimo ih $a$ i $b$, onda bi uz izbor bilo kojeg trećeg broja $c$ iz tog skupa izraz $ab+bc+ca$ bio djeljiv sa $3$. Dakle, $S$ može sadržavati najviše jedan broj djeljiv sa $3$.

Promotrimo tri broja $a$, $b$ i $c$ od kojih nijedan broj nije djeljiv sa $3$. Ako sva tri broja daju isti ostatak pri dijeljenju sa $3$, onda je izraz $ab+bc+ca$ djeljiv s $3$.

To znači da najviše dva elementa skupa $S$ mogu davati ostatak $1$ pri dijeljenju sa $3$ i najviše dva elementa mogu davati ostatak $2$.

Dakle, $S$ može imati najviše $5$ elemenata.

Ostaje provjeriti da je moguće da $S$ ima točno $5$ elemenata (tj. da naša ograda nije pregruba).

Promotrimo skup u kojem je jedan broj djeljiv sa $3$, dva daju ostatak $1$, te dva daju ostatak $2$ pri dijeljenju sa $3$. Neka su $a$, $b$ i $c$ tri broja iz tog skupa.

Ako među brojevima $a$, $b$ i $c$ ima točno jedan broj koji je djeljiv sa $3$, onda izraz $ab+bc+ca$ nije djeljiv sa $3$.

Ako dva od ta tri broja daju ostatak $1$, a treći broj daje ostatak $2$ ili ako dva od ta tri broja daju ostatak $2$, a treći broj daje ostatak $1$, onda $ab+bc+ca$ daje ostatak $2$ pri dijeljenju sa $3$, tj. izraz $ab+bc+ca$ nije djeljiv sa $3$. Time je završena provjera.

Zaključujemo da je najmanji traženi $n$ jednak $6$.