Does there exist a set $S$ of $100$ points in a plane such that the center of mass of any $10$ points in $S$ is also a point in $S$?
Problem
Source: Bulgaria NMO 2021 P5
Tags: algebra, combinatorics, combinatorial geometry
16.05.2021 18:24
It's impossible. Let $V:=\{v_i: i=1,2,\dots,100\}$ be the corresponding set of distinct vectors and let $m:=\min\{|v_i-v_j|: i\neq j\}$. Clearly $m>0$. Suppose $m=|v_k-v_{\ell}|, k\neq \ell$. Let $V_0\subset V$ be a set of $9$ vectors not equal to $v_k$ and $v_{\ell}$. Then $v_i:=\frac{1}{10}\left(\sum_{v\in V_0}v+v_{k}\right)\in V$ and $v_j:=\frac{1}{10}\left(\sum_{v\in V_0}v+v_{\ell}\right)\in V$ and $v_i\neq v_j.$ We have $$|v_i-v_j|=\frac{|v_k-v_{\ell}|}{10}=\frac{m}{10}$$contradiction.
18.05.2021 15:47
Tricky problem. The other idea is to choose $101$ sets of $10$ points with distinct centres of mass. Impose coordinate system and label the points $1,2,...100$, such that $j$ has bigger $x-coordinate$ than $i$, for $j>i$ (obviously this is possible). Now we choose these $101$ sets such that their sums of elements are increasing, which will guarantee that these centres of mass are distinct. Indeed, this idea has appeared many times, e.g. ISL 1993 C2, ISL 2013 C4. Choose $(1,2,...9,10),(1,2,...9,11),...(1,2,...9,100),(1,2,...8,10,100),(1,2,...8,11,100) ,...(1,2,...8,19,100)$ (note that by ISL 1993 C2 we can construct much longer chain of such sets with increasing sums)
19.05.2021 11:47
@above: This was exactly the official solution.
21.05.2021 22:30
You can prove it with almost a single sentence. Say the first 11 vectors contain k different values of x coordinates a1<a2<...<ak then you have the set of averages s1,s2,...,sk defined as s_i is the average of all a_j with j!=i then the s_i are k different values in the range [a1,ak] so each s_i equals some a_j but if so then a1 is the average of some elements larger then him, which is a contradiction that can only be explained by k=1 so the first 11 vectors has all the same x coordinate and then assume by way of contradiction that d is the smallest number that is an x coordinate of some vector and satisfies d>a1 then the average (d+9*a1)/10 is different from all x coordinates if vectors in S which is a contradiction, so all x coordinates of all 100 vectors are equal and the same for y coordinates, meaning all vectors are the same
23.05.2021 12:48
Mikeglicker wrote: You can prove it with almost a single sentence. Say the first $11$ vectors contain $k$ different values of $x$ coordinates $a_1<a_2<\dots< a_k$ then you have the set of averages $s_1,s_2,\dots,s_k$ defined as: $s_i$ is the average of all $a_j$ with $j\neq i$. Then the $s_i$'s are $k$ different values in the range $[a_1,a_k]$ so each $s_i$ equals some $a_j,$ but if so then $a_1$ is the average of some elements larger than itself, which is a contradiction that can only be explained by $k=1,$ so the first $11$ vectors have all the same $x$ coordinates and then assume by way of contradiction that $d$ is the smallest number that is an $x$ coordinate of some vector and satisfies $d>a_1$ then the average $(d+9\cdot a_1)/10$ is different from all $x$ coordinates of vectors in $S$, which is a contradiction. So all $x$ coordinates of all $100$ vectors are equal and the same for $y$ coordinates, meaning all vectors are the same. Ok, I think, your sentences are more than the sentences of any solution, presented above. But, also, there is a small flaw, which can be fixed, but the number of sentences will increase further. The second text in red. It does not imply the coordinates of the first $11$ vectors are the same. For example, if you have $10$ vectors with the same $x$ coordinate $a_1$ and one with $a_2, a_2>a_1$ then by your notations, $s_{11}=10\cdot a_1/10=a_1,$ so you cannot claim all $11$ vectors have the same $x$ coordinates!
04.01.2022 03:42
We will prove that if we replace $100$ by $n\geq 3$ and $10$ by $k\leq n$ then a possible configuration exists only for $k=1$ and $k=n$. Lemma. (IMO SL 1993) Let $S$ be a set of $n$ pairwise distinct real numbers and $k\leq n$ be a positive integers. Then the number of distinct values of the sums $x_1 + x_2 + \ldots + x_k$, where $x_1, x_2, \ldots, x_k$ are pairwise distinct elements from $S$, is at least $k(n-k) + 1$. Proof. Let the elements of $S$ be $x_1 < x_2 < \ldots < x_n$. Put a ball on each of $1,2,\ldots,k$ on the number axis and let us apply (several times, in a particular way) the following operation: we move a ball from $m$ to $m+1$ with the condition that $m+1$ is not already occupied by another ball. Every $k$-tuple of positions of the balls corresponds to a sum of $x_i$-s, whose indices are the positiions of the balls. Moreover, after each application of the operation the sum increases and so the number of distinct sums is at least the number of possible moves plus $1$ (the sum from the start also has to be counted). Let us start with the ball on position $k$ and apply the operation $n-k$ times - this leads to ball positions $1,2,\ldots,k-1,n$. Doing analogously with the other balls, we finally reach $n-k+1,n-k+2,\ldots,n-1,n$ after $k(n-k)$ moves. The lemma follows. Back to the main problem. For $k=1$ every set of $n$ points works while if $k=n$ we can for example pick the vertices of a regular $(n-1)$-gon and its center. Now suppose $2\leq k \leq n-1$. We may assume that all the abscissa of the points in $S$ are different - if not, then we rotate the coordinate axes so that the $y$-axis is not perpendicular to any segment with endpoints in $S$; this is possible since the number of segments with endpoints in $S$ is finite while the set of angles of rotation is infinite. From the lemma we have $k(n-k) + 1 \geq n+1$ (equivalent to $n\geq \frac{k^2}{k-1} = k+1 + \frac{1}{k-1}$) different values among the arithmetic means of $k$-tuples of abscissa and so at least $n+1$ points, contradiction. It remains to take care of $k=n-1$. In this case $k(n-k) + 1 = n$ and so there are at least $n$ arithmetic means of $k$-tuples of abscissas. In other words, if $x_1 < x_2 < \ldots < x_{n}$ are these abscissa and $A = x_1 + x_2 + \ldots + x_{n}$, then the means $\frac{A-x_i}{n-1}$ are a permutation of the $x_i$-s. In particular, $x_1 = \frac{A-x_i}{n-1}$ for some $i$, which is impossible.
24.01.2022 13:44
Lemma: We can find 11 points such that the convex-hull of these points does not contain any point from the remaining 89 points. Proof: Choose 11 points. If there is a point in convex-hull, add it to these 11 points and substract a point of convex-hull from the first 11 points. By continuing this process we eventually get the needed set. There are 11 different 10-tuple, all of the mass centers are different and must be inside convex hull. Thus all 11 points are mass center for some 10-tuple. However there is a point on convex hull which is a (actually two at least) vertex ( if A,B,C,... are the points on convex hull then there is at least one point with $A \notin \text{ segment }BC$, other way is you can choose the one with the least [and the greatest] $x$ coordinate.) Thus the number of mass centers must be less than 11, contradiction.