Maths Olympiad Prep

Library / /74 of 75

Combinatorics Difficulty 6.8 National Olympiad Find the answer Italy

Problem:

A complicated choreography involves a row of 7 equally spaced ballerinas on a flat stage; facing the ballerinas' row there is an identical, parallel row of just as many male dancers. The choreographer wants to assign to each ballerina some male dancers so that, when drawing on the stage the segment joining the position of each ballerina to that of the male dancers assigned to her, there are no segments that intersect except at their endpoints. She also wants the total number of segments drawn to be 13. How many possible ways are there of making the assignments that satisfy these properties?

Pick one

Solution

Solution:

The answer is (D). For convenience, let us imagine the ballerinas and the male dancers arranged horizontally, from left to right. The condition in the text can be translated as follows. Let us call BiB_{i} the set of male dancers assigned to the ii-th ballerina, with i=1,,7i=1, \ldots, 7. In order to respect the condition in the text (the fact that the segments do not cross), the male dancers in B2B_{2} must all be to the right of those in B1B_{1} (except that the rightmost male dancer of B1B_{1} may coincide with the leftmost male dancer of B2B_{2}), and so on: the male dancers in B3B_{3} are all to the right of those in B2B_{2} (except that the rightmost one of B2B_{2} may coincide with the leftmost one of B3B_{3}), those of B4B_{4} to the right of those of B3B_{3}, and so forth. In particular, each set BiB_{i} intersects at most one element of Bi1B_{i-1} and at most one element of Bi+1B_{i+1} (provided i11i-1 \geq 1 and i+17i+1 \leq 7). The total number of male dancers assigned, that is, the total number of segments drawn, is
13=B1+B2++B7B1B2B7+6, 13=|B_{1}|+|B_{2}|+\cdots+|B_{7}| \leq |B_{1} \cup B_{2} \cup \cdots \cup B_{7}|+6,
where the inequality holds precisely because the male dancers shared among the various sets are at most 6 (one between B1B_{1} and B2B_{2}, one between B2B_{2} and B3B_{3}, \ldots). In particular, B1B7|B_{1} \cup \cdots \cup B_{7}| must be greater than or equal to 7, that is, every male dancer is assigned to at least one ballerina. The equality 13=B1+B2++B713=|B_{1}|+|B_{2}|+\cdots+|B_{7}| also implies that B1B_{1} actually has an element in common with B2B_{2}, which has an element in common with B3B_{3}, and so on up to B7B_{7} (this in particular also justifies the fact, implicitly used in the previous description, that none of the sets BiB_{i} is empty).

Let us further observe that a set BiB_{i} cannot have 'gaps', that is, it is formed by a row of adjacent male dancers (precisely: if it contains two male dancers, it also contains all those in between them). Indeed, if two male dancers are both assigned to the same ballerina, then all the male dancers between them can only be assigned to that same ballerina (in order to respect the condition that the segments do not cross). Since we have already observed that every male dancer must be assigned to at least one ballerina, we conclude, as desired, that each set BiB_{i} consists of mutually adjacent male dancers.

On the basis of all these observations we then obtain that to the first ballerina are assigned all the male dancers from the first to the i1i_{1}-th (for some i1{1,,7}i_{1} \in \{1, \ldots, 7\}); to the second, all those from the i1i_{1}-th to the i2i_{2}-th (for some i2{1,,7}i_{2} \in \{1, \ldots, 7\}), and so on up to the seventh ballerina, to whom are assigned the male dancers from i6i_{6} to i7=7i_{7}=7. To describe the situation it is therefore enough to know the numbers i1i2i6i_{1} \leq i_{2} \leq \cdots \leq i_{6} (since we already know that i7=7i_{7}=7). We can think of such a collection of numbers as a function ff from {1,2,3,4,5,6}\{1,2,3,4,5,6\} to {1,2,3,4,5,6,7}\{1,2,3,4,5,6,7\}, with the condition that it be weakly increasing, that is, that f(x+1)f(x)f(x+1) \geq f(x) for x=1,,6x=1, \ldots, 6. Knowing ff is then equivalent to knowing the function gg that sends xx to f(x)+xf(x)+x, which is now strictly increasing (that is, g(x+1)>g(x)g(x+1)>g(x)) and takes values in the set {2,3,,7+6=13}\{2,3, \ldots, 7+6=13\}. Finally, given the condition of being strictly increasing, such a function is completely determined by knowledge of the 6 elements of its image (given 6 distinct numbers in {2,,13}\{2, \ldots, 13\}, there is a unique strictly increasing function {1,,6}{2,,13}\{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,,13}\{2, \ldots, 13\} having 6 elements, that is (126)=924\left(\begin{array}{c}12 \\ 6\end{array}\right)=924.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.