49th International Mathematical Olympiad Spain

To begin, let us describe those points $B\in S$ which are $k$-friends of the point $(0,0)$. By definition, $B=(u,v)$ satisfies this condition if and only if there is a point $C=(x,y)\in S$ such that $\frac{1}{2}|uy-vx|=k$. (This is a well-known formula expressing the area of triangle $ABC$ when $A$ is the origin.)

To say that there exist integers $x,y$ for which $|uy-vx|=2k$, is equivalent to saying that the greatest common divisor of $u$ and $v$ is also a divisor of $2k$. Summing up, a point $B=(u,v)\in S$ is a $k$-friend of $(0,0)$ if and only if $\gcd (u,v)$ divides $2k$.

Translation by a vector with integer coordinates does not affect $k$-friendship; if two points are $k$-friends, so are their translates. It follows that two points $A,B\in S$, $A=(s,t)$, $B=(u,v)$, are $k$-friends if and only if the point $(u-s,v-t)$ is a $k$-friend of $(0,0)$; i.e., if $\gcd (u-s,v-t)\mid 2k$.

Let $n$ be a positive integer which does not divide $2k$. We claim that a $k$-clique cannot have more than $n^2$ elements.

Indeed, all points $(x,y)\in S$ can be divided into $n^2$ classes determined by the remainders that $x$ and $y$ leave in division by $n$. If a set $T$ has more than $n^2$ elements, some two points $A,B\in T$, $A=(s,t)$, $B=(u,v)$, necessarily fall into the same class. This means that $n\mid u-s$ and $n\mid v-t$. Hence $n\mid d$ where $d=\gcd (u-s,v-t)$. And since $n$ does not divide $2k$, also $d$ does not divide $2k$. Thus $A$ and $B$ are not $k$-friends and the set $T$ is not a $k$-clique.

Now let $M(k)$ be the least positive integer which does not divide $2k$. Write $M(k)=m$ for the moment and consider the set $T$ of all points $(x,y)$ with $0\le x,y<m$. There are $m^2$ of them. If $A=(s,t)$, $B=(u,v)$ are two distinct points in $T$ then both differences $|u-s|,|v-t|$ are integers less than $m$ and at least one of them is positive. By the definition of $m$, every positive integer less than $m$ divides $2k$. Therefore $u-s$ (if nonzero) divides $2k$, and the same is true of $v-t$. So $2k$ is divisible by $\gcd (u-s,v-t)$, meaning that $A,B$ are $k$-friends. Thus $T$ is a $k$-clique.

It follows that the maximum size of a $k$-clique is $M(k{)}^2$, with $M(k)$ defined as above. We are looking for the minimum $k$ such that $M(k{)}^2>200$.

By the definition of $M(k)$, $2k$ is divisible by the numbers $1,2,\dots ,M(k)-1$, but not by $M(k)$ itself. If $M(k{)}^2>200$ then $M(k)\ge 15$. Trying to hit $M(k)=15$ we get a contradiction immediately ($2k$ would have to be divisible by $3$ and $5$, but not by $15$).

So let us try $M(k)=16$. Then $2k$ is divisible by the numbers $1,2,\dots ,15$, hence also by their least common multiple $L$, but not by $16$. And since $L$ is not a multiple of $16$, we infer that $k=L/2$ is the least $k$ with $M(k)=16$.

Finally, observe that if $M(k)\ge 17$ then $2k$ must be divisible by the least common multiple of $1,2,\dots ,16$, which is equal to $2L$. Then $2k\ge 2L$, yielding $k>L/2$.

In conclusion, the least $k$ with the required property is equal to $L/2=180180$.