LIX OM - I - Task 7

In an $ n $-person association, there are $ 2n-1 $ committees (any non-empty set of association members
forms a committee). A chairperson must be selected in each committee. The following condition must be met: If
committee $ C $ is the union $ C = A\cup B $ of two committees $ A $ and $ B $, then the chairperson of committee $ C $ is also
the chairperson of at least one of the committees $ A $, $ B $. Determine the number of possible selections of chairpersons.
Answer: n!.
We will establish a one-to-one correspondence between the possible choices of committee chairs
and the ways of assigning members of the association the numbers $1, 2, \dots, n$ (where different members
are assigned different numbers). There are, of course, as many of the latter as there are permutations of an $n$-element set,
which is $n!$.
Suppose, then, that in each committee a chair has been chosen in accordance with the assumptions of the problem.
We assign the members of the association numbers inductively as follows:

The number 1 is assigned to the chair of the committee that includes all members of the association.
The number 2 is assigned to the chair of the committee that includes all members of the association except the member with number 1.
The number 3 is assigned to the chair of the committee that includes all members of the association except those with numbers 1 and 2, and so on.

We will show that with this method of assigning numbers, the following condition is satisfied:
(*) The chair of any committee is the one among its members who has been assigned the smallest number.
Indeed, consider any committee $A$ and let $k$ be the smallest of the numbers assigned to the members
of this committee. Let $B$ be the committee consisting of all members of the association who have been assigned numbers
not less than $k$. From the method of assigning numbers, it follows that the chair of committee $B$ is the member
with number $k$. Moreover, committee $B$ is the union of two committees: $A$ and $B \setminus A$. Since the member with number
$k$ does not belong to committee $B \setminus A$, according to the conditions of the problem, he must be the chair of committee $A$.
We have thus defined a mapping that assigns a way of assigning the members of the association the numbers $1, 2, \dots, n$ to a choice of committee chairs. To complete the solution of the problem, we will now define the inverse mapping.
Namely, if the members of the association have been assigned the numbers $1, 2, \dots, n$, then in each committee
we choose as chair the member who has the smallest number (condition (*) will then be satisfied).
If committee $C$ is the union $C = A \cup B$ of two committees $A, B$ and the member with number $k$ is the chair
of committee $C$, then he belongs to one of the committees $A, B$, in which he is the member with the lowest number — and thus is
its chair. We see, then, that the condition given in the problem statement is satisfied. Therefore, if
we start with the choice of committee chairs, assign numbers to the members of the association according to
the previously defined rule, and then reconstruct the committee chairs from these numbers, we
will obtain the original choice of chairs. Similarly, if we assign numbers to the members of the association, choose the committee chairs
based on these numbers, and then assign the members numbers according to the described inductive procedure, the
numbers will be identical to the original numbers. Thus, the defined mappings are mutually
inverse, which completes the solution.