Disclaimer: these are my personal solutions; they have not been reviewed, so be careful relying on them as there might be errors. Some competitions may have official solutions from the contest publishers which you may wish to refer to instead if you’re looking for verified solutions.
Problem 6
Let $S$ be a set of positive integers and let $E$ be the operation on the set of subsets of $S$ defined by $EA = \lbrace x \in A \mid x \text{ is even} \rbrace$, where $A \subseteq S$. Let $CA$ denote the complement of $A$ in $S$. $ECEA$ will denote $E(C(EA))$, etc.
- Show that $ECECEA = EA$.
- Find the maximum number of distinct subsets of $S$ that can be generated by applying the operations $E$ and $C$ to a subset $A$ of $S$ an arbitrary number of times in any order.
Hints
Hint #1
TODO
Solution to part (a)
Open to see the solution; try solving it first or see the hints above!
$$ \begin{align*} EA & = \{ x \in A \mid x \textrm{ is even} \} & \qquad \textrm{given} \\ CEA & = \{ x \in A \mid x \textrm{ is odd} \} \cup (S \setminus A) & \qquad \textrm{need to include complement of $A$} \\ ECEA & = \{ x \in (S \setminus A) \mid x \textrm{ is even} \} & \qquad \textrm{even subset of odd subset of $A = \empty$} \\ CECEA & = \{ x \in (S \setminus A) \mid x \textrm{ is odd} \} \cup A & \qquad \textrm{complement of $S \setminus A$ is $A$} \\ ECECEA & = \{ x \in A \mid x \textrm{ is even} \} & \qquad \textrm{even subset of odd subset of $S \setminus A = \empty$} \\ \end{align*} $$Therefore, $EA = ECECEA. \quad \blacksquare$
Solution to part (b)
Below are two approaches to solving part (b) in slightly different ways.
This is short-form analytical approach to the solution.
If we can apply the operators $E$ and $C$ to $A$ an arbitrary number of times in any order, the set of possible subsets of $S$ can be represented by
$$ \cdots (E \cdots E) (C \cdots C) (E \cdots E) \cdots A $$
We can consider the two possible cases: whether the rightmost operator (i.e., the first operator) applied to $A$ is either $E$ or $C$, so we have the two possible cases:
- $ \cdots (C \cdots C) (E \cdots E) A$
- $ \cdots (E \cdots E) (C \cdots C) A$
Next, let’s consider consecutive applications of $E$ and $C$:
- $EEA = EA$ since applying “subset that is even” to a set that has already been pre-selected for evens is idempotent. Thus, by induction, any number of consecutive applications of $E$ collapse to a single application of $E$.
- $CCA = A$ since applying “complement of” is its own inverse, so any even number of applications of $C$ collapse to no applications of $C$ and any odd number of applications of $C$ collapse down to a single application of $C$.
Thus, by taking both of the above rules, the only two patterns we need to consider are alternating applications of a single operator $E$ or $C$, and the only distinguishing characteristic is the rightmost operator, as above:
- $ \cdots CECEA$
- $ \cdots ECECA$
Given that in part (a), we proved that $ECECEA = EA$, there are only a small set of these sets that are based on $EA$, namely: ${ EA, CEA, ECEA, CECEA }$.
Now we have to consider the sets that start with $CA$ so we can repeat the solution in part (a) to see where it creates a chain by repeating an earlier expression:
$$ \begin{align*} CA & = S \setminus A & \qquad \textrm{given} \\ ECA & = \{ x \in (S \setminus A) \mid x \textrm{ is even} \} & \qquad \textrm{apply $E$} \\ CECA & = \{ x \in (S \setminus A) \mid x \textrm{ is odd} \} \cup A & \qquad \textrm{need to include $A$} \\ ECECA & = \empty \cup EA = EA \\ \end{align*} $$Since $EA$ is already included in the set above, we don’t need to include it, and nor do we include $ECECA$ since it’s the same set set as $EA$.
Thus, we only add these 3 sets to the total: ${ CA, ECA, CECA }$.
Adding up the $4$ sets we found above with the $3$ sets we found here, there are a total of $\boxed{7}$ different subsets that we can create. $\blacksquare$
This is an intuitive / visual approach to the solution.
We can consider the set of all possible subsets as nodes in a graph, and each application of $E$ or $C$ operation to be a transition or an edge, between those nodes. Thus, we want to find the number of the reachable nodes in that graph, starting from a point we’ll label $A$.
We can start with the set $A$ itself, and note that applying the $E$ operator we get to the state we’ll define as $EA$ and similarly, of we apply the $C$ operator, we’ll arrive at $CA$:
We can continue recursively applying $E$ and $C$ operators until we find that we’re going around in loops, at which point, we’ll have found the exhaustive set of potential sets.
Starting with $EA$, note that $EEA = EA$ because applying “is even” to an existing set which was already pre-selected to have only evens doesn’t change anything, while applying $C$ to the set $EA$ gets a new set $CEA$:
Whereas the $C$ operator is its own inverse, namely: $CCA = A$, but applying $E$ to $CA$ gets us a new set $ECA$:
Similarly as above, applying $C$ to $CEA$ gets us $CCEA = EA$ since $C$ is its own inverse, while applying $E$ to $CEA$ gets us a new set $ECEA$:
Expanding from $ECA$ further, we know that re-applying $E$ to $ECA$ leads to $EECA = ECA$ since consecutive applications of $E$ are idempotent, while applying $C$ to $ECA$ gets us a new set $CECA$:
Let’s further expand $ECEA$: another application of $E$ is idempontent, while applying $C$ gets us $CECEA$:
Expanding $CECA$ we see that applying $C$ brings us back to $ECA$ while applying $E$ gets us a new state $ECECA$:
Here’s where things start to get interesting: from $CECEA$ we know that applying $C$ gets us to the earlier state $ECEA$, but applying $E$ should get us to a new state $ECECEA$, but … recall that in part (a) we proved that $EA = ECECEA$! Thus, this ends this branch as we have explored it entirely:
We know that $ECECA$ will loop back to itself if we reapply $E$, but applying $C$, do we get a new set $CECECA$ which we will have to explore indefinitely, or would it parallel part (a) and turn out to equal to $CA$? Let’s find out!
$$ \begin{align*} CA & = S \setminus A & \qquad \textrm{given} \\ ECA & = \{ x \in (S \setminus A) \mid x \textrm{ is even} \} & \qquad \textrm{apply $E$} \\ CECA & = \{ x \in (S \setminus A) \mid x \textrm{ is odd} \} \cup A & \qquad \textrm{need to include $A$} \\ ECECA & = \empty \cup EA = EA \\ \end{align*} $$Thus, we actually have to revise our earlier diagram, since we marked $ECECA$ as a distinct node from $EA$ but they’re actually one and the same:
Thus, there are total of $\boxed{7}$ different subsets we can create. $\blacksquare$