assume that the sequence of circles is $C_i$ then we want to say that $C_i$ is constant eventually,so suppose that $A_{1,C_i},\dots,A_{k_i,C_i}$ are in $C_i$ then define such a function $F(C_i)=\sum_{j=1}^{i_k} (R^2-|O_iA_{j,C_i}|^2)$ then this function if $O_i\neq O_{i+1}$ increase .(this part is cmputational) defining such afunction is not that hard i think that if you define $F(C_i)=\sum (|O_iA_{j,C_i}|^2)+(n-i_k)R^2$ this decrease so it will stop.any way no one could'nt solve it in exam.

Cool problem! I have the same idea, but I wanted to express it via moment of inertia only, and I, obviously, failed to get monotonocy. sam-n wrote: define such a function $F(C_i)=\sum_{j=1}^{i_k} (R^2-|O_iA_{j,C_i}|^2)$ then this function if $O_i\neq O_{i+1}$ increase .(this part is cmputational) Indeed, $\sum_{j=1}^{i_k} |O_iA_{j,C_i}|^2$ is the moment of inertia of $\{A_{j,C_i}\}$ wrt $O_i$. Due to Steiner's theorem when we move the point $O_i$ to the center of gravity $O_{i+1}$ this sum decreases, moreover we lost some negative summands $R^2-|O_iA_{j,C_i}|^2$, if $A_{j,C_i}$ becomes out of circle, and we gain new positive summands from the new incoming points. Therefore, $f(C_i)$ increases!

I feel myself stupid. Is the circle the set of $X$ for which $OX=R$ or the set of $X$ for which $OX\le R$? I was sure that the first case is correct, than there is a counterexample: take a rectangular $ABCD$, put $O$ in a midpoint of $AB$, and choose $r=OC=OD$. Then $O$ moves from midpoint of $AB$ to midpoint of $CD$ and so on.

Indeed, we consider a disk instead of a circle in this problem.

This problem was the most difficult problem. I think nobody solved it.

hey people, i need some help here understanding the proof. how do you prove that $f(C_i)$ keeps increasing? and myth, what's Steiner's theorom and what does moment of inertia refer to ?

Here's a solution by geoishard and me. There are finitely many centroids, so it suffices to show that no nontrivial cycles exist. Suppose that centers $O_1,O_2,\ldots,O_n$ of circles $C_1,C_2,\ldots,C_n$ ($n>1$; indices modulo $n$) form a cycle so that for all $k$, $O_{k+1}$ is the centroid of the points $P\in C_k$. The key idea is that the centroid (uniquely) minimizes the sum of squares of distances to vertices (while centers of circles essentially minimize maximal distances), so $\sum_{P\in C_k}PO_k^2-PO_{k+1}^2>0$ for all $k$ since $O_k\ne O_{k+1}$. On the other hand, \begin{align*} \sum_{k=1}^{n}\sum_{P\in C_k}PO_k^2-PO_{k+1}^2 &=\sum_{k=1}^{n}\sum_{P\in C_k}PO_k^2-\sum_{P\in C_{k-1}}PO_k^2 \\ &=\sum_{k=1}^{n}\sum_{P\in C_k\setminus C_{k-1}}PO_k^2-\sum_{P\in C_{k-1}\setminus C_k}PO_k^2 \\ &\le r^2\sum_{k=1}^{n}|C_k\setminus C_{k-1}|-|C_{k-1}\setminus C_k|=r^2\sum_{k=1}^{n}|C_k|-|C_{k-1}|=0, \end{align*}contradiction.

This problem is closely related to the K-means algorithm from signal processing and unsupervised machine learning. You can learn more about this topic on the corresponding Wikipedia article or Coursera video. First I will introduce the algorithm and show why it terminates, and then I will apply it to solve the problem. Introducing the K-means Algorithm: Suppose we have $m$ points $P_1, P_2, \dots, P_m$ in some Euclidean space and we want to group them into $k$ clusters of "nearby" points. We accomplish this with an iterative process as follows: At the initial iteration $t=1$ start with $k$ random points $Q_1^0, Q_2^0, \dots, Q_k^0$ in the space which represent the centers of the clusters. Now at each iteration $t$ of the algorithm, we will group the points $P_1, P_2, \dots, P_m$ based on which of the $k$ points $Q_1^{t-1}, Q_2^{t-1}, \dots, Q_k^{t-1}$ they are closest to; this partitions the $P_i$ into $k$ clusters $C_1,C_2, \dots, C_k$ such that all points in $C_i$ are closer to $Q_i^{t-1}$ than $Q_j^{t-1}$ for any $j\neq i$ (ties are broken arbitrarily). Now for each $1\le i\le k$ we will define $Q_i^t$ as the centroid of the points in $C_i$ (with no change if $S_i$ is empty), and then move on to the next iteration of the algorithm. There are nice pictures illustrating this in the links I wrote above. We terminate when the $Q_i$ stop moving (ie. when $Q_i^{t-1} = Q_i^t$ for each $i$). Proof the algorithm terminates: Clearly there are only finitely many possible positions for the $Q_i^t$, so if we can find a monovariant then the algorithm must terminate. At any given iteration $t$ of the algorithm, define $f_t(i)=j$ if $P_i\in C_j$, so that $f_t(i)$ represents the point $Q_j^t$ closest to $P_i$ at step $t$. Then it's easy to see that the cost $\displaystyle\sum_{1\le i\le m} |P_iQ_{f_t(i)}^{t-1}|^2$ decreases whenever we go from $t\to t+1$ until the algorithm terminates: This is because the step where we cluster the $P_i$ based on which of the $Q_j^t$ they are closest to necessarily minimizes each individual term $|P_iQ_{f(i)}^{t-1}|^2$ over all possible index assignment functions $f$, and the step where we reassign $Q_j$ to be the average of the points $C_j$ necessarily minimizes $\sum_{f_{t+1}(i) = j} |P_iQ_j^t|^2$ over all possible choices of $Q_j^t$ for each $j$, since it's well-known the centroid minimizes the sum of squares of distances. (Basically, the index reassignment and $Q_j$ reassignment steps both act to greedily minimize the cost). Solving the Iran problem: WLOG suppose we are working in the plane $z=0$ and denote $O = (x_0,y_0,0)$ the initial position of $O$, the center of the disk. For each point $P_i = (x_i,y_i,0)$ for $1\le i\le n$ we will introduce a duplicate point $P_i' = (x_i,y_i,2r)$ in an upper plane so there are $2n$ total $P$'s. We will run the $K$-means algorithm on these $2n$ points with $n+2$ clusters. For each pair $P_i = (x_i,y_i,0), P_i' = (x_i,y_i,2r)$ we introduce a cluster center $Q_i^0 = (x_i,y_i,r)$; we also introduce two new clusters at positions $Q_{n+1}^0 = (x_0,y_0, 0), Q_{n+2}^0 = (x_0, y_0, 2r)$. First note that as the algorithm progresses, the movements of $Q_{n+1}, Q_{n+2} = O, O'$ will mirror each other, on parallel planes. This means by induction on $t$ that the positions of the points $Q_1^t, Q_2^t, \dots, Q_n^t$ will always remain fixed, because for each $1\le i\le n$ the only points which could possibly lie in $C_i$ at any given moment in time are $P_i, P_i'$ (since $Q_i^t$ will be $r$ units away from $P_i, P_i'$ and $>r$ units from everything else), and the average of $P_i, P_i'$ is precisely $Q_i^0$. Therefore the movements of $Q_{n+1}, Q_{n+2}$ in the $K$-means algorithm precisely mirror the movement of $O, O'$ in the original problem, since the only points in $C_{n+1}, C_{n+2}$ will be the ones $\le r$ units away from $Q_{n+1}^t, Q_{n+2}^t$, and we keep updating $Q_{n+1}, Q_{n+2}$ to be the centroids of the points in $C_{n+1}, C_{n+2}$! Thus since the $K$-means algorithm terminates, $O$ and $O'$ will eventually stop moving as well $\blacksquare$ (Obviously the cost function we use to prove the $K$-means algorithm terminates is identical to the monovariant used in the above solutions so there is nothing new here, but I thought it would be instructive to point out the connection here, and besides, this is a nice algorithm to learn about in its own right.)