We are given a set $S=\{z_1,z_2,\cdots ,z_{1993}\}$, where $z_1,z_2,\cdots ,z_{1993}$ are nonzero complex numbers (also viewed as nonzero vectors in the plane). Prove that we can divide $S$ into some groups such that the following conditions are satisfied: (1) Each element in $S$ belongs and only belongs to one group; (2) For any group $p$, if we use $T(p)$ to denote the sum of all memebers in $p$, then for any memeber $z_i (1\le i \le 1993)$ of $p$, the angle between $z_i$ and $T(p)$ does not exceed $90^{\circ}$; (3) For any two groups $p$ and $q$, the angle between $T(p)$ and $T(q)$ exceeds $90^{\circ}$ (use the notation introduced in (2)).
Problem
Source: China Mathematical Olympiad 1993 problem4
Tags: vector, complex numbers, combinatorics unsolved, combinatorics
alexiaslexia
10.12.2020 07:52
One of the most retro-looking and classical problem I've ever seen. IMO this problem ramps up the difficulty of the contest by a lot. We will divide $S$ into three sets. $\color{green} \rule{25cm}{3pt}$ $\color{green} \textbf{\text{Notations.}}$ As per the significance of $"\textbf{the resultant}"$ in the problem, pair a set $s \subseteq S$ with its resultant $R_s$ --- and from now on, we can refer to a set as a collection of its vectors --- i.e. $s$, or a resultant of its vectors --- i.e. $R_s$. We now introduce a few keywords to make more sense (of the operations after this.) Call a set of vectors $s_1$ (or $R_{s_1}$, following the above convention) to be $\textit{acutely-summed with itself}$ if $\angle (R_{s_1},z_i) < 90^{\circ} \, \, \forall z_i \in s_1$, $\textit{entirely rightly-summed}$ if for every $z_i\in S$ and $\angle(z_i,R_{s_1}) \leq 90^{\circ}$, then $z_i \in s_1$, and $\textit{universally big}$ if it has (one of) the largest norm/magnitude across all subsets of $S$ Out of all these characteristics, call it entirely rightly-summed and universally big in $S'$ if $s_1 \subseteq S'$ and it satisfies those characteristics were $S$ is replaced by $S'$. Now for the central claim. $\color{magenta} \rule{25cm}{0.5pt}$ $\color{magenta} \textbf{\text{The Big Claim.}}$ If a set $s_1$ is universally big in $S'$, then it satisfies all three characteristics in $S'$. $\color{magenta} \textbf{The Proof.}$ Pictorial proof (and use the law of cosines!)
$\color{blue} \rule{25cm}{1pt}$ $\color{blue} \textbf{\text{Finishing.}}$ Pick the first set $S_1$ to be a set which is universally big in $S$. Then, every vector which forms an acute or right angle with $R_{S_1}$ in in $S_1$, and the others are in $S-S_1$. Now pick the second set $S_2$ to be a set which is universally big in $S-S_1$ and note that by applying the parallelogram rule multiple times, its resultant must not form an acute angle with $R_{S_1}$. Pick $S_3$ to be the remaining vectors, and it is also easy to check that $\angle(R_{S_3},R_{S_i}) > 90^{\circ}$ for $i \in \{1,2\}$. We are done. $\blacksquare$ $\blacksquare$ $\blacksquare$
Section 1: 5 points. Soft Tech (Resultant sums are important): Here we must see that the existence of one or two individual vectors doesn't matter in the grand scale, and what matters is their relations to groups of vectors.
Section 2: 5 points. Soft Tech (Problem spotting): Self-explanatory. Sometimes constructing a random set of perfect counter-examples to the blatantly wrong algorithms is helpful.
Section 3: 10 points. Hard Tech (Seeing and implementing extremal ideas): The hardest part of the problem, by far. Turns out that some set being $\textit{universally big}$ solves half the problem.
Section 4: 2.5 points. Soft Tech (Multiple executions of similar ideas.) Here we solve all of the glaring problems in Section 2 is valid.
Section 5: 2.5 points. Hard Tech (Second and third class construction.) Basically the continuation and finishing of Section 4.
Final Comments: Summing up, this (quite) fits my initial expectation of this being unexpectedly tricky in 25-30M (although the total is 25 points, I could have put this a bit higher in 27.5 points as well.) The presence of three intimidating conditions and the failure of straight-up induction or explicit constructional ideas also ups the difficulty, though one could argue that two applications of straight-up extremal ideas works. Even then, "double extremals" are a rare method to use; and one would really need to be sure of his extremal motivations to boldly commence the construction of the second set with a similar idea.
\[\begin{tabular}{p{12cm}}
$\rule{4cm}{0.5pt} \hspace{1cm} \bigstar \hspace{1cm} \rule{4cm}{0.5pt}$ \\
\end{tabular} \\ \]From the outset, to divide $S$ into two or four sets is downright unthinkable --- for two sets to actually happen, the two resultants must form a $180^{\circ}$ angle, and for four sets to actually happen, the four resultants must form a $90^{\circ}$ angle with themselves. However, we can just build a set of $1993$ vectors which doesn't have a pair of resultants in the opposite direction, forcing the solver to divide it into three sets.
Now, the first condition dictates that a partition must happen, and the second condition dictates that the partition must have its vectors to be closely packed (when identified by its angle at the origin, of course.) If we deviate from that constraint, say that if we have $\textit{the balls}$ to have a $0^{\circ}$ angle and a $165^{\circ}$ angle in the same set, then we must also have $\textit{the balls}$ to prove that the resultant's angle must lie in the tight interval $[75^{\circ},90^{\circ}]$.
However, this breeds an interesting thought: we cannot rule out (read:color/separate into groups) immediately that some two vectors must be in different groups; even two as incompatible as $0^{\circ}$ and $179^{\circ}$ can actually belong to the same set if the group's resultant is between $[89^{\circ},90^{\circ}]$. For me, this gave a clue that the individual positions of the vectors doesn't really matter, but how the group performs in relation to itself, its vectors, other vectors, and the whole $S$ is much more crucial.
\[\begin{tabular}{p{12cm}}
$\rule{4cm}{0.5pt} \hspace{1cm} \bigstar \hspace{1cm} \rule{4cm}{0.5pt}$ \\
\end{tabular} \\ \]However, shrugging the thought that some far-distanced vectors could still belong in the same group, I immediately tried to divide it into $\textit{interval classes}$. What would happen if one just divide $S$'s vectors into $[0,110^{\circ}], [110^{\circ},230^{\circ}]$ and $[230^{\circ},360^{\circ}]$?
[asy][asy]usepackage("tikz");label("\begin{tikzpicture}[scale=0.8]
\draw[green,thick](0,0)--(4,0); \draw[green,thick](0,0)--(110:4cm); \draw[green,thick](0,0)--(230:4cm);\draw[blue!50!red!50](140:3cm)--(320:3cm); \draw[blue!50!red!50](20:3cm)--(200:3);\draw[blue!50!red!50](90:3cm)--(270:3cm); \draw[green!40!black!60,ultra thick,->](0,0)--(100:3.5cm); \draw[green!40!black!60,ultra thick,->](0,0)--(160:3.7cm); \draw[red,dashed,thick,->](0,0)--(290:2.5cm);
\node[green] at (110:4.5cm) {$\theta_2$};
\node[green] at (230:4.5cm) {$\theta_3$};
\node[green] at (4.5,0) {$\theta_1$};
\node at (100:3.8) {$R_1$};
\node at (160:4.2) {$R_2$};
\node at (290:2.9) {$R_3?$};
\fill[red] (0,0)circle(3pt);
\end{tikzpicture}");[/asy][/asy]
Some glaring problems are immediately seen: the angle $\angle (R_1, \theta_1)$ could be greater than $90^{\circ}$ (or, the angle of $R_1$ and some vector with an angle really close to $\theta_1$ could ruin the day), the angle $\angle (R_1,R_2)$ could be very small, even if $R_2$ behaves nicely within its own vectors (notice how I began to name sets based on its $(\theta_1,\theta_2)$ and its resultants now). The only "relief" was that now $R_3$'s existence (wherever it is) is loosely bounded due to the close nature of $R_1$ and $R_2$ (but, $R_3$ still have to be inside the third group's purple lines).
And, further attempts of explicit $\theta$ setting did not work; I tried to form $\theta$ from resultants -- which clearly does not make sense because $\textbf{by moving the bound, the resultants are also moved!}$.
\[\begin{tabular}{p{12cm}}
$\rule{4cm}{0.5pt} \hspace{1cm} \bigstar \bigstar \hspace{1cm} \rule{4cm}{0.5pt}$ \\
\end{tabular} \\ \]Out of the three problems I described above, the most fixable and friendly one seems to be the first, as the second wouldn't have happened without the first, and the third wouldn't happen without the first and second happening earlier. Zooming in on how $R_1$ could have formed, we get the following queer observation:
[asy][asy]usepackage("tikz");label("\begin{tikzpicture}
\draw[green,thick](0,0)--(4,0); \draw[green,thick](0,0)--(110:4cm);
\draw[blue!50!red!50](140:3cm)--(0,0); \draw[blue!50!red!50](0,0)--(0,3); \draw[green!40!black!60,ultra thick,->](0,0)--(160:3.7cm); \draw[green!40!black!60,ultra thick,->](0,0)--(100:3.5cm);
\node at (100:3.8) {$R_1$};
\node at (160:4.2) {$R_2$};
\end{tikzpicture}
\begin{tikzpicture}
\node at (0,0){}; \node at (0,2){$\quad \rightarrow \quad$};
\end{tikzpicture}
\begin{tikzpicture}
\draw[green,thick](0,0)--(4,0); \draw[green,thick](0,0)--(110:4cm); \draw[blue!50!red!50](0,0)--(0,3); \draw[orange!50!black!50, ->](0,0)--(103:2.5cm); \draw[orange!50!black!50,->](0,0)--(94:2cm); \draw[orange!50!black!50,->](0,0)--(107:3cm); \draw[orange!50!black!50,->](0,0)--(101:4cm); \draw[orange!50!black!50,->](0,0)--(97:4cm); \draw[orange!50!black!50,->](0,0)--(20:2cm);
\end{tikzpicture}");[/asy][/asy]
that there must exist some 10 vectors in the range $[90^{\circ},\theta_2]$, and only a few vectors close to $\theta_1=0^{\circ}$! Coupled with the fact that $R_2$ must also form this way (albeit to a lesser degree) --- it would make sense to attempt to create a new set of vectors which combines the vectors around $\theta_2$! Sure, this initially big resultant can be combined with other loose vectors not around $\theta_2$, but the big resultant could provide some solid foundation for the shifting, if they are indeed combined with said loose vectors. This prompted the $\textit{universally big}$ property -- which is a very crucial aspect of the solution.
\[\begin{tabular}{p{12cm}}
$\rule{4cm}{0.5pt} \hspace{1cm} \text{0.5}\bigstar \hspace{1cm} \rule{4cm}{0.5pt}$ \\
\end{tabular} \\ \]Then, I realized that I really had not used some version of the parallelogram law, which must also be crucial in this problem --- since we only consider sums of vectors here, after all! After considering such big resultants, it would seem unfitting if such high-magnitude resultants have a vector near them that is not in their set. With their large nature, I realized that this "entirely rightly-summed" somewhat solved the second condition, that they must be consistent with themselves.
Of course, seeing the operations of the parallelogram law in more detail yields the questions $"\text{what would happen if some parasites are inside the set?}"$ (i.e. reverse orientation of the $\textit{acutely-summed}$ property) and $"\text{what would happen if we add some vector outside the set to the resultant?}"$ (reverse orientation of the $"\textit{entirely rightly-summed}"$ property). With this solving entirely the second condition and providing some groundwork for building a big-magnituded first class, I then proceeded to the strangely phrased third condition.
\[\begin{tabular}{p{12cm}}
$\rule{4cm}{0.5pt} \hspace{1cm} \text{0.5}\bigstar \hspace{1cm} \rule{4cm}{0.5pt}$ \\
\end{tabular} \\ \]While it may seem obvious to construct a second set with a similar algorithm, I did not finalize the $\textit{entirely rightly-summed}$ condition by this point yet. In my mind, I still wondered $"\text{how would I stabilize the angle between} \, R_1 \, \text{and} \, R_2?"$
Setting again for $R_1$ to be the largest resultant among all (while $R_2$ is just a sub-large resultant from some of the remaining vectors) I wondered if $R_2$ "could lose some weight" by transferring some of its parasites to $R_1$. One man's trash may just be another's treasure, as some would say. Then, by the parallelogram law, $R_2$ cannot be entirely formed by the vectors in the bottom half-plane (wherever it is).
Then it dawned on me to define the "bottom half plane" to be those that are parasites to $R_1$; all the resultants from the bottom half plane must, of course, be of the bottom half-plane! This way of thinking really came in handy when constructing a largest second set, and also the third remaining set -- which also nicely satisfied the $"\textit{acutely-summed with itself}"$ property, due to all its vectors being located inside an acute interval (see the third picture in the Solution.)
\[\begin{tabular}{p{12cm}}
$\rule{4cm}{0.5pt} \hspace{1cm} \blacksquare \hspace{1cm} \rule{4cm}{0.5pt}$ \\
\end{tabular} \\ \]
Use $\text{[list=disc] [*] (Some text) [*] (Some other text) [/list]}$ for itemize.