Kmeans on “symmetric” data A set is said to be fully-symmetric if for every x in it, negating one of its components results in y such that y is in the set as well.
A set is said to be semi-symmetric if for every x in it, negating all of its components (at once) results in y such that y is in the set as well.
Now examine the optimal solution of the Kmeans objective with K=2d+1 for d-dimensional unique observations that are fully-symmetric.
Suppose it is known that the optimal means set w.r.t the above setup is unique and contains the zero vector. Prove or give a counter example to the following claim: The set of optimal means is semi-symmetric
 A: Under weaker conditions, the assumptions imply the set of optimal means is fully symmetric.  The proof is trivial, but exposing that triviality (or, perhaps, exposing my misunderstanding of the question!) seems to require a bit of (standard) notation, so let's begin there.
Let me just say at the outset, though, that the intuition is this: if the "set of optimal means" is not fully symmetric, then applying an appropriate symmetry to the original set will produce a different set of optimal means that nevertheless achieves the same global minimum value of the K-means objective function, thereby contradicting the hypothesis that the set of optimal means is unique.  Rather than adopt this proof by contradiction, however, I will develop a direct proof involving the same ideas.
Let $X \subset \mathbb{R}^d$ be fully symmetric--that is, invariant under the group $G$ generated by the $d$ reflections around the coordinate planes.  Write $x^g$ for the action of $g \in G$ on $x \in X$ and let $Y^g$ = $\{y^g|y \in Y\}$ whenever $Y\subset X$.  A "semi-symmetric" set is invariant under a particular subgroup $H \subset G$; namely, the one generated by the product of those $d$ reflections (in any order--they all commute).  Note that all reflections (and therefore all products of reflections) are Euclidean isometries: they preserve distances.
K-means clustering is a distance-based method to partition $X$ into $K$ nonempty subsets $X_1, \ldots, X_K$, thereby determining $K$ corresponding barycenters.  This clustering method does not necessarily yield a unique solution, but we are allowed in this case to assume that all K-means solutions determine the same set of barycenters ("the optimal means set is unique").
Because $G$ acts isometrically as a group of permutations on $X$ and the K-means algorithm can be written strictly in terms of distances between elements of $X$, it is immediate that whenever $\{X_1, \ldots, X_K\}$ is a K-means solution then so is $\{X_1^g, \ldots, X_K^g\}$ for any $g\in G$.  The uniqueness assumption tells us that the set of barycenters of the $X_i^g, i=1,\ldots, K,$ equals the set of barycenters of the $X_i, i=1,\ldots, K$.  But, because $g$ is an isometry of $\mathbb{R}^d$ and barycenters are uniquely determined by distance-based criteria, the barycenter of $X_i^g$ is the image under $g$ of the barycenter of $X_i$.  Consequently, the set of barycenters is $G$-invariant (and a fortiori it is $H$-invariant), QED.

It was not necessary either to assume $K=2d+1$ nor to assume $0$ is among the barycenters: uniqueness of the set of barycenters alone implies the conclusion.
A more interesting conjecture is this: when $X$ is $G$-invariant, then there exists a K-means clustering that is "semisymmetric" (but not all K-means solutions have to enjoy any of the symmetries of $G$).  For example, the center, midpoints, and vertices of a square in $\mathbb{R}^2$, $\{(0,0),(1,0),(0,1),(-1,0),(0,-1),(1,1),(-1,1),(-1,-1),(1,-1)\}$ has some semi-symmetric $5$-means solutions (the origin together with four (vertex, midpoint) pairs) but no fully-symmetric solutions; indeed, it even has some solutions with no symmetry at all.  However, even this conjecture is not generally true.  (Consider the 2-means solutions in $\mathbb{R}^1$ for $X=\{-1,0,1\}$.)  Possibly restricting $K=2d+1$ will make this work, as suggested by the question, but I'm not sure precisely what set of assumptions would be both interesting and lead to a correct conclusion along these lines.
