12. A complicated choreography involves a row of 7 dancers equally spaced on a flat stage; in front of the row of dancers, there is an identical, parallel row of the same number of male dancers. The choreographer wants to assign to each dancer some male dancers in such a way that, by drawing on the stage the segment connecting the position of each dancer to that of the male dancers assigned to her, there are no segments that intersect except at the ends. She also wants the total number of segments drawn to be 13. How many ways are there to make the assignments that satisfy these properties?
(A) 128
(B) 343
(C) 486
(D) 924
(E) 1716

## Numerical answer problems -5 points
12. The answer is (D). For convenience, let's imagine the dancers and dancers arranged horizontally, from left to right. The condition in the text can be translated as follows. Let $B_{i}$ be the set of dancers assigned to the $i$-th dancer, with $i=1, \ldots, 7$. To respect the condition in the text (that the segments do not cross), the dancers in $B_{2}$ must all be to the right of those in $B_{1}$ (except that the rightmost dancer in $B_{1}$ can coincide with the leftmost dancer in $B_{2}$), and so on: the dancers in $B_{3}$ are all to the right of those in $B_{2}$ (except that the last to the right in $B_{2}$ can coincide with the first to the left in $B_{3}$), those in $B_{4}$ to the right of those in $B_{3}$, and so forth. In particular, each set $B_{i}$ intersects with at most one element of $B_{i-1}$ and at most one element of $B_{i+1}$ (provided that $i-1 \geq 1 \text{ and } i+1 \leq 7$). The total number of dancers assigned, i.e., the total number of segments drawn, is

$$
13=\left|B_{1}\right|+\left|B_{2}\right|+\cdots+\left|B_{7}\right| \leq\left|B_{1} \cup B_{2} \cup \cdots \cup B_{7}\right|+6 \text {, }
$$

where the inequality holds because the dancers in common between the various sets are at most 6 (one between $B_{1}$ and $B_{2}$, one between $B_{2}$ and $B_{3}$, etc.). In particular, $\left|B_{1} \cup \cdots \cup B_{7}\right|$ must be greater than or equal to 7, i.e., each dancer is assigned to at least one dancer. The equality $13=\left|B_{1}\right|+\left|B_{2}\right|+\cdots+\left|B_{7}\right|$ implies that $B_{1}$ actually has one element in common with $B_{2}$, which has one element in common with $B_{3}$, and so on up to $B_{7}$ (this justifies in particular the fact, used implicitly in the previous description, that none of the sets $B_{i}$ is empty).

We also observe that a set $B_{i}$ cannot have 'gaps', i.e., it is formed by a row of adjacent dancers (precisely: if it contains two dancers, it also contains all those between them). Indeed, if two dancers are both assigned to the same dancer, then all the dancers between them can only be assigned to the same dancer (to respect the condition that the segments do not cross). Since we have already observed that each dancer must be assigned to at least one dancer, we conclude as desired that each set $B_{i}$ is made up of adjacent dancers.

Based on all these observations, we then obtain that the first dancer is assigned all the dancers from the first to the $i_{1}$-th (for some $i_{1} \in\{1, \ldots, 7\}$); the second, all those from the $i_{1}$-th to the $i_{2}$-th (for some $i_{2} \in\{1, \ldots, 7\}$), and so on up to the seventh dancer, to whom the dancers from $i_{6}$ to $i_{7}=7$ are assigned. To describe the situation, it is therefore sufficient to know the numbers $i_{1} \leq i_{2} \leq \cdots \leq i_{6}$ (since we already know that $i_{7}=7$). We can think of such a collection of numbers as a function $f$ from $\{1,2,3,4,5,6\}$ to $\{1,2,3,4,5,6,7\}$, with the condition that it is weakly increasing, i.e., that $f(x+1) \geq f(x)$ for $x=1, \ldots, 6$. Knowing $f$ is then equivalent to knowing the function $g$ that maps $x$ to $f(x)+x$, which is now strictly increasing (i.e., $g(x+1)>g(x)$) and takes values in the set $\{2,3, \ldots, 7+6=13\}$. Finally, given the condition of being strictly increasing, such a function is completely determined by the knowledge of the 6 elements of its image (given 6 distinct numbers in $\{2, \ldots, 13\}$, there is a unique strictly increasing function $\{1, \ldots, 6\} \rightarrow\{2, \ldots, 13\}$ that assumes them as values). We conclude, therefore, that the number sought is the number of subsets of $\{2, \ldots, 13\}$ having 6 elements, i.e., $\left(\begin{array}{c}12 \\ 6\end{array}\right)=924$.