clustering with equal elements Assume that we have a set of observations: $\mathbf{X} = \{x_{1}, \dots, x_{n}\}\subseteq \mathbb{R}^{d}$, containing $n$ observations for a fixed dimensionality $d$. Assume, we have some fixed integer $k$. The k-means clustering (with l2 distance) is the problem of finding centroids the clusters $S_{1}, \dots, S_{k}$ that minimize
$$
cost(S_{1}, \dots, S_{1}) = \sum_{j=1}^{k}\sum_{x\in S_{j}}||x - q_{j}||^{2},
$$
where $q_{1}, \dots, q_{k} \in \mathbb{R}^{d}$ are the centroids, i.e. $q_{j} = \frac{1}{|S_{j}|}\sum_{x\in S_{j}}x$.
Assume, there in $\mathbf{X} = \{x_{1}, \dots, x_{n}\}$ there are equal elements $\{x\} \subset \mathbf{X}$.
Is it possible that in a global (theoretical) solution these equal to each other elements $\{x\}$ belong to different clusters?
 A: First we need to distinguish between the globally optimal k-means solution and the result you get from a k-means algorithm. There are quite a number of these around, and unless the dataset is very small, they will deliver a local optimum that isn't necessarily the global one. (You say "global" in your question so I assume you mean the globally optimal solution; just to make sure.)
The answer to your question starts with "not normally"; their $\|x-q_j\|$-values are obviously equal for all $q_j$, so once the algorithm is converged (or the globally optimal $q_j$ are known), they will all be assigned to their closest $q_j$, which is the same for them all.
An exceptional situation that is not covered by the above argument occurs if not only several $x$ are equal, but they are also in equal distance to two or more $q_j$. I actually don't know of any algorithm that in this case can assign them to different clusters, but I cannot exclude that such implementations exist.
In fact I haven't tried to prove it but I suspect that the global optimum will never separate equal observations, because chances are that if equal observations are separated, one can achieve a better solution putting all of them into the cluster that has the majority of them (or just any cluster if they are evenly distributed). It doesn't seem to make sense to have these obsrvations influence more than one cluster mean (making it potentially worse for the majority of other observations in that cluster). One could probably prove this spending an afternoon doing maths, but no guarantee here, just a guess.
What I have looked at is a number of 1-d examples with equal points sitting between two halves of the data such as 1,2,3,3,4,5. Indeed you get a better solution ($k=2$) in terms of cost if you put the two 3 both either in a cluster with 1,2, or with 4,5, rather than one to the left and one to the right (you can check this by explicitly computing the cost functions).
