Library / Harvard-MIT Mathematics Tournament /238 of 352

Harvard-MIT Mathematics Tournament

Combinatorics Difficulty 5.3 AIME, harder Prove it United States

Problem:
A cell of a 2-configuration of a set $A$ is a nonempty subset $C$ of $A$ such that
i. for any two distinct elements $a, b$ of $C$ , there exists a sequence $c_{0}, c_{1}, \ldots, c_{n}$ of elements of $A$ with $c_{0}=a, c_{n}=b$ , and such that $\left\{c_{0}, c_{1}\right\},\left\{c_{1}, c_{2}\right\}, \ldots,\left\{c_{n-1}, c_{n}\right\}$ are all elements of the 2-configuration, and
ii. if $a$ is an element of $C$ and $b$ is an element of $A$ but not of $C$ , there does NOT exist a sequence $c_{0}, c_{1}, \ldots, c_{n}$ of elements of $A$ with $c_{0}=a, c_{n}=b$ , and such that $\left\{c_{0}, c_{1}\right\},\left\{c_{1}, c_{2}\right\}, \ldots,\left\{c_{n-1}, c_{n}\right\}$ are all elements of the 2-configuration.
Also, we define a 2-configuration of $A$ to be barren if there is no subset $\left\{a_{0}, a_{1}, \ldots, a_{n}\right\}$ of $A$ , with $n \geq 2$ , such that $\left\{a_{0}, a_{1}\right\},\left\{a_{1}, a_{2}\right\}, \ldots,\left\{a_{n-1}, a_{n}\right\}$ and $\left\{a_{n}, a_{0}\right\}$ are all elements of the 2-configuration.
Show that, given any 2-configuration of a set $A$ , every element of $A$ belongs to exactly one cell.

Solution

Solution:
First, given $a$ , let $C_{a}$ be the set of all $b \in A$ for which there exists a sequence $a=c_{0}, c_{1}, \ldots, c_{n}=b$ as in the definition of a cell. Certainly $a \in C_{a}$ (take $n=0$ ); we claim that $C_{a}$ is a cell. If $b, b^{\prime} \in C_{a}$ , then there exist sequences $a=c_{0}, c_{1}, \ldots, c_{n}=b$ and $a=c_{0}^{\prime}, c_{1}^{\prime}, \ldots, c_{m}^{\prime}=b^{\prime}$ , so the sequence $b=c_{n}, c_{n-1}, \ldots, c_{1}, c_{0}, c_{1}^{\prime}, \ldots, c_{m}^{\prime}=b^{\prime}$ shows that the first condition is met.

For the second, suppose that there does exist a sequence $b=c_{0}, c_{1}, \ldots, c_{n}=b^{\prime}$ with $b \in C_{a}, b^{\prime} \notin C_{a}$ . Then, concatenating with our sequence from $a$ to $b$ , we get a sequence from $a$ to $b^{\prime}$ , contradicting the assumption $b^{\prime} \notin C_{a}$ . Thus, the second condition holds, and $C_{a}$ is a cell. So $a$ lies in at least one cell.

But now, note that if $C$ is a cell containing $a$ , then all $b$ for which such a sequence from $a$ to $b$ exists must lie in $C$ (or the second condition is violated), and if no such sequence exists, then $b$ cannot lie in $C$ (or the first condition is violated). Thus, the elements of $C$ are uniquely determined, so there is exactly one cell containing $a$ , and the proof is complete.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.