Korean Mathematical Olympiad

Let $a_i$ be the number of chosen points on the line $y=i$. If $a_i\ge 2$ and $x_1<x_2<\cdots <x_{a_i}$ are the x-coordinates of the chosen points on the line $y=i$, then because $$x_1+x_2<x_1+x_3<x_2+x_3<x_2+x_4<x_3+x_4<\cdots <x_{a_1-1}+x_{a_1}$$ we deduce that the number of distinct sums of two x-coordinates among chosen points on $y=i$ is at least $2a_i-3$. This also holds trivially if $a_i<2$. There are $2n-3$ distinct values that can be obtained as a sum of two integers between 1 and $n$. Since $$\sum _{i=1}^n(2a_i-3)=2k-3n\ge 5n-2-3n=2n-2>2n-3,$$ by the pigeonhole principle, there exist four distinct chosen points $(x_1,y_1)$, $(x_1^{\prime },y_1^{\prime })$, $(x_2,y_2)$ such that $x_1+x_1^{\prime }=x_2+x_2^{\prime }$ and $y_1\ne y_2$. There exists a circle going through these four points.