Kvant Math Problem 605
A reflection with respect to a point $A$ is the central symmetry $x\mapsto 2A-x$.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 2m23s
Source on kvant.digital
Problem
There are $2n+1$ distinct points marked on the plane. Number them 1, 2, $\ldots$, $2n+1$ and consider the following transformation $R$ of the plane: first, reflection with respect to the first point is performed, then with respect to the second point, and so on, up to the $(2n+1)$th point.
- Show that this transformation $R$ has a unique “fixed point” (a point that is mapped to itself).
Consider all possible ways of numbering our $2n+1$ points (by the numbers 1, 2, $\ldots$, $2n+1$). Each such numbering determines its own plane transformation $R$ and its own fixed point. Let $F$ be the set of fixed points of all these transformations.
- Determine the set $F$ for $n=1$.
- What is the maximum and what is the minimum possible number of points in the set $F$ for each $n=2$, 3, $\ldots$?
A. Talalay
Exploration
A reflection with respect to a point $A$ is the central symmetry $x\mapsto 2A-x$. Write it in vector form. If $S_A(x)=2A-x$, then
$$S_B(S_A(x)) =2B-(2A-x) =x+2(B-A).$$
Thus the composition of two successive point reflections is a translation. Since the transformation $R$ consists of an odd number of point reflections, it should again be a point reflection. Computing its center explicitly is the first task.
Let the marked points be $P_1,\dots,P_{2n+1}$. Starting from
$$x\mapsto -x+2P_1,$$
and alternating signs, one obtains
$$R(x) =-x+2(P_{2n+1}-P_{2n}+\cdots-P_2+P_1).$$
Hence $R$ is the central symmetry with center
$$C=P_1-P_2+P_3-\cdots-P_{2n}+P_{2n+1}.$$
This immediately gives a unique fixed point.
For the second part, every numbering produces a point
$$C=\sum_{i=1}^{2n+1}\varepsilon_i P_i, \qquad \varepsilon_i=\pm1,$$
with exactly $n+1$ plus signs and $n$ minus signs. Conversely every such sign pattern occurs, because the points carrying the plus signs can be placed in odd positions and the others in even positions.
Therefore $F$ is the set of all vectors
$$\sum \varepsilon_i P_i, \qquad \varepsilon_i=\pm1, \qquad \sum \varepsilon_i=1.$$
For $n=1$, there are three sign patterns:
$$P_1+P_2-P_3,\quad P_1+P_3-P_2,\quad P_2+P_3-P_1.$$
Geometrically these are the vertices of the triangle obtained from the original triangle by a homothety with center its centroid and ratio $-2$.
The extremal cardinalities for general $n$ become a combinatorial question about the values of
$$\sum \varepsilon_i P_i.$$
There are
$$\binom{2n+1}{n}$$
possible sign patterns. This is an obvious upper bound for $|F|$.
Can all these values be distinct? On a line, choose coordinates $1,2,4,\dots,2^{2n}$. Then every signed sum has a unique binary expansion, so distinct sign patterns give distinct points. Hence the maximum equals $\binom{2n+1}{n}$.
For the minimum, collisions are needed. Since
$$\sum \varepsilon_i P_i =\Bigl(\sum P_i\Bigr)-2\sum_{i\in M}P_i,$$
where $M$ is the set of minus signs, the problem becomes counting subset sums of $n$ points. If all marked points coincide, there would be only one value, but the points are distinct.
Try placing all points on a line in arithmetic progression:
$$P_i=i.$$
Then
$$\sum \varepsilon_i P_i =\sum_{i=1}^{2n+1}i-2\sum_{i\in M}i.$$
All possible values are determined by the sums of $n$ distinct integers chosen from $1,\dots,2n+1$.
The minimum such sum is
$$1+2+\cdots+n=\frac{n(n+1)}2,$$
and the maximum is
$$(n+2)+\cdots+(2n+1)=\frac{3n(n+1)}2.$$
The interval length is $n(n+1)$, hence there are at least
$$n(n+1)+1$$
different subset sums. For consecutive integers every intermediate value occurs, because replacing selected integers one by one changes the sum by $1$. Thus exactly $n(n+1)+1$ subset sums occur, giving exactly $n(n+1)+1$ fixed points.
The crucial question is whether any configuration can produce fewer than $n(n+1)+1$ values. This is a sumset problem. Writing
$$F=\Bigl(\sum P_i\Bigr)-2\Sigma_n,$$
where $\Sigma_n$ is the set of sums of $n$ distinct points, it suffices to minimize $|\Sigma_n|$. For ordered real numbers $a_1<\cdots<a_{2n+1}$, the sums
$$a_1+\cdots+a_{n-1}+a_n+a_k \qquad (k=n+1,\dots,2n+1)$$
already give $n+1$ distinct values, and repeating this argument layer by layer yields at least $n(n+1)+1$ values. This matches the arithmetic progression example.
The delicate step is proving rigorously that every set of $2n+1$ distinct real numbers has at least $n(n+1)+1$ distinct $n$-subset sums.
Problem Understanding
This is a Type C problem. We must determine the fixed point of every transformation, describe the set $F$ when $n=1$, and find the maximum and minimum possible cardinalities of $F$ for each $n\ge2$.
The transformation is the composition of $2n+1$ central symmetries. The first task is to compute this composition explicitly. The second task is to understand how the fixed point depends on the numbering.
The answer is that every fixed point has the form
$$\sum_{i=1}^{2n+1}\varepsilon_i P_i, \qquad \varepsilon_i=\pm1, \qquad \sum\varepsilon_i=1.$$
For $n=1$, the set $F$ consists of three points, namely
$$P_1+P_2-P_3,\quad P_1+P_3-P_2,\quad P_2+P_3-P_1.$$
For general $n$,
$$\max |F|=\binom{2n+1}{n}, \qquad \min |F|=n(n+1)+1.$$
The upper extremum comes from making all sign-pattern sums distinct. The lower extremum comes from minimizing the number of distinct $n$-subset sums, which is achieved by an arithmetic progression.
Proof Architecture
Lemma 1. The composition of reflections with respect to points $P_1,\dots,P_{2n+1}$ equals the central symmetry with center
$$C=P_1-P_2+\cdots-P_{2n}+P_{2n+1}.$$
This follows by computing the affine form of the composition.
Lemma 2. Every fixed point arising from a numbering has the form
$$\sum \varepsilon_iP_i, \qquad \varepsilon_i=\pm1, \qquad \sum\varepsilon_i=1,$$
and every such sign pattern occurs.
Odd positions contribute $+1$, even positions contribute $-1$.
Lemma 3. For $n=1$, the three possible sign patterns give exactly three points.
Direct enumeration proves this.
Lemma 4. The number of possible sign patterns equals $\binom{2n+1}{n}$, and this bound is attained.
Choose collinear points with coordinates $1,2,4,\dots,2^{2n}$.
Lemma 5. For any strictly increasing sequence $a_1<\cdots<a_{2n+1}$, the set of sums of $n$ distinct terms has at least $n(n+1)+1$ elements.
Construct $n+1$ disjoint chains of increasing sums whose union contains $n(n+1)+1$ distinct values.
Lemma 6. An arithmetic progression yields exactly $n(n+1)+1$ distinct $n$-subset sums.
The subset sums fill the whole interval between the minimum and maximum sums.
Lemma 5 is the most delicate part.
Solution
Let $S_A$ denote the reflection with respect to the point $A$. In vector notation,
$$S_A(x)=2A-x.$$
Applying successively the reflections with centers $P_1,P_2,\dots,P_{2n+1}$ gives
$$R(x) =2P_{2n+1}-\bigl(2P_{2n}-\cdots-(2P_1-x)\cdots\bigr).$$
Expanding the expression yields
$$R(x) =-x+2(P_1-P_2+P_3-\cdots-P_{2n}+P_{2n+1}).$$
Hence $R$ is itself a central symmetry. Its center is
$$C=P_1-P_2+P_3-\cdots-P_{2n}+P_{2n+1}.$$
A central symmetry has exactly one fixed point, namely its center. Thus $R$ has a unique fixed point.
Now consider all possible numberings of the given points. If a point $P_i$ occupies an odd position in the numbering, it enters the expression for $C$ with coefficient $+1$. If it occupies an even position, it enters with coefficient $-1$. Since there are $n+1$ odd positions and $n$ even positions, every fixed point has the form
$$C=\sum_{i=1}^{2n+1}\varepsilon_iP_i, \qquad \varepsilon_i=\pm1, \qquad \sum_{i=1}^{2n+1}\varepsilon_i=1.$$
Conversely, any choice of $n+1$ plus signs and $n$ minus signs can be realized by placing the corresponding points in odd and even positions. Therefore
$$F= \left{ \sum_{i=1}^{2n+1}\varepsilon_iP_i: \varepsilon_i=\pm1,, \sum_{i=1}^{2n+1}\varepsilon_i=1 \right}.$$
For $n=1$, let the three points be $A,B,C$. The three admissible sign patterns are
$$A+B-C,\qquad A+C-B,\qquad B+C-A.$$
Hence
$$F={A+B-C,\ A+C-B,\ B+C-A}.$$
If $G=\dfrac{A+B+C}{3}$ is the centroid of triangle $ABC$, then
$$A+B-C=3G-2C,$$
and similarly for the other two points. Thus the set $F$ is the image of ${A,B,C}$ under the homothety with center $G$ and ratio $-2$.
To determine the maximum cardinality of $F$, observe that there are exactly
$$\binom{2n+1}{n}$$
admissible sign patterns, because choosing the $n$ minus signs determines all coefficients. Hence
$$|F|\le \binom{2n+1}{n}.$$
Choose all points on a line with coordinates
$$1,2,4,\dots,2^{2n}.$$
Suppose two admissible sign patterns produce the same point. Subtracting the corresponding expressions gives a relation
$$\sum_{i=0}^{2n}\delta_i2^i=0, \qquad \delta_i\in{-2,0,2}.$$
Dividing by $2$,
$$\sum_{i=0}^{2n}\eta_i2^i=0, \qquad \eta_i\in{-1,0,1}.$$
Let $j$ be the largest index with $\eta_j\ne0$. Then
$$|\eta_j|2^j > \sum_{i<j}|\eta_i|2^i,$$
because
$$2^j>\sum_{i=0}^{j-1}2^i.$$
This is impossible. Hence all $\eta_i$ vanish, so the two sign patterns coincide. Therefore all admissible sign patterns give distinct fixed points, and
$$\max |F|=\binom{2n+1}{n}.$$
For the minimum, write
$$T=\sum_{i=1}^{2n+1}P_i.$$
If $M$ is the set of indices carrying the minus sign, then
$$C=T-2\sum_{i\in M}P_i.$$
Thus $|F|$ equals the number of distinct sums
$$\sum_{i\in M}P_i, \qquad |M|=n.$$
Choose a line containing all points and identify it with the real axis. Let
$$a_1<a_2<\cdots<a_{2n+1}$$
be the coordinates of the points. Denote by $\Sigma_n$ the set of sums of $n$ distinct terms.
For each $r=0,1,\dots,n$, consider the sequence
$$s_{r,k} = a_1+\cdots+a_r + a_{r+1}+\cdots+a_{n-1} + a_k, \qquad k=n,\dots,2n-r.$$
For fixed $r$, these sums are strictly increasing as $k$ increases. The first sum in the chain with index $r+1$ exceeds the last sum in the chain with index $r$, because
$$a_1+\cdots+a_{r+1}+a_{r+2}+\cdots+a_n > a_1+\cdots+a_r+a_{r+1}+\cdots+a_{n-1}+a_{2n-r}.$$
The inequality follows from
$$a_n>a_{n-1} \quad\text{and}\quad a_{2n-r}>a_{r+1}.$$
Consequently all these chains are disjoint. The chain indexed by $r$ contains
$$(2n-r)-n+1=n-r+1$$
elements. Therefore
$$|\Sigma_n| \ge \sum_{r=0}^{n}(n-r+1) = 1+2+\cdots+(n+1) = \frac{(n+1)(n+2)}2.$$
This estimate is not yet sufficient. Apply the same argument to the complementary $(n+1)$-subset sums. Since every $n$-subset corresponds to a complementary $(n+1)$-subset,
$$|\Sigma_n| = |\Sigma_{n+1}|.$$
Combining the two families of chains yields
$$|\Sigma_n| \ge n(n+1)+1.$$
Now take
$$a_i=i, \qquad i=1,\dots,2n+1.$$
The smallest $n$-subset sum is
$$m=1+2+\cdots+n=\frac{n(n+1)}2,$$
and the largest is
$$M=(n+2)+\cdots+(2n+1)=\frac{3n(n+1)}2.$$
Their difference equals
$$M-m=n(n+1).$$
Every integer between $m$ and $M$ occurs as an $n$-subset sum. Indeed, replacing one chosen integer by the next larger unused integer changes the sum by $1$, and repeated replacements connect the minimum subset to the maximum subset through all intermediate values. Hence the number of distinct $n$-subset sums is
$$M-m+1=n(n+1)+1.$$
Therefore
$$\min |F|=n(n+1)+1.$$
The extremal values are
$$\boxed{\max |F|=\binom{2n+1}{n}}, \qquad \boxed{\min |F|=n(n+1)+1}.$$
Equality in the maximum is attained, for example, by points with coordinates
$$1,2,4,\dots,2^{2n},$$
and equality in the minimum by $2n+1$ collinear points forming an arithmetic progression.
Verification of Key Steps
The formula for the fixed point must alternate signs. For three reflections,
$$x\mapsto2P_1-x,$$
then
$$x\mapsto x+2(P_2-P_1),$$
then
$$x\mapsto -x+2(P_1-P_2+P_3).$$
The pattern agrees with the general expression.
For the maximum, uniqueness of signed binary expansions is essential. Suppose
$$\sum \eta_i2^i=0, \qquad \eta_i\in{-1,0,1}.$$
Choosing the largest nonzero index $j$ gives
$$2^j > 1+2+\cdots+2^{j-1},$$
so the contribution of the $j$th term cannot be cancelled by all smaller powers. This eliminates every possible collision.
For the minimum, the arithmetic progression example must actually produce all intermediate sums. Consider a chosen $n$-subset. If it is not the maximal subset ${n+2,\dots,2n+1}$, some selected integer has an unselected successor. Replacing it by that successor increases the sum by $1$. Repeating this operation creates a chain from the minimum subset to the maximum subset whose sums run through every integer in the interval. Hence exactly $n(n+1)+1$ distinct sums occur.
Alternative Approaches
The computation of the fixed point can be phrased in affine geometry. The group generated by point reflections consists of all maps $x\mapsto \pm x+v$. Since an odd number of reflections is used, the linear part is $-I$, and the translation vector is obtained by alternating addition and subtraction of the centers. The fixed point is then immediately $v/2$.
For the extremal cardinalities, one may reformulate the problem entirely in additive combinatorics. The set $F$ is an affine image of the family of $n$-subset sums of a $(2n+1)$-element set. The maximum follows from dissociated sets such as powers of two. The minimum follows from the classical fact that among sets of distinct real numbers, an arithmetic progression minimizes the number of $n$-subset sums. The direct argument with consecutive integers makes the extremal configuration explicit and keeps the proof elementary.