Maths Olympiad Prep

Library / /258 of 377

Combinatorics Difficulty 5.3 AIME, harder Prove it United States

Problem:
A cell of a 2-configuration of a set AA is a nonempty subset CC of AA such that
i. for any two distinct elements a,ba, b of CC, there exists a sequence c0,c1,,cnc_{0}, c_{1}, \ldots, c_{n} of elements of AA with c0=a,cn=bc_{0}=a, c_{n}=b, and such that {c0,c1},{c1,c2},,{cn1,cn}\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 aa is an element of CC and bb is an element of AA but not of CC, there does NOT exist a sequence c0,c1,,cnc_{0}, c_{1}, \ldots, c_{n} of elements of AA with c0=a,cn=bc_{0}=a, c_{n}=b, and such that {c0,c1},{c1,c2},,{cn1,cn}\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 AA to be barren if there is no subset {a0,a1,,an}\left\{a_{0}, a_{1}, \ldots, a_{n}\right\} of AA, with n2n \geq 2, such that {a0,a1},{a1,a2},,{an1,an}\left\{a_{0}, a_{1}\right\},\left\{a_{1}, a_{2}\right\}, \ldots,\left\{a_{n-1}, a_{n}\right\} and {an,a0}\left\{a_{n}, a_{0}\right\} are all elements of the 2-configuration.
Show that, given any 2-configuration of a set AA, every element of AA belongs to exactly one cell.

Solution

Solution:
First, given aa, let CaC_{a} be the set of all bAb \in A for which there exists a sequence a=c0,c1,,cn=ba=c_{0}, c_{1}, \ldots, c_{n}=b as in the definition of a cell. Certainly aCaa \in C_{a} (take n=0n=0); we claim that CaC_{a} is a cell. If b,bCab, b^{\prime} \in C_{a}, then there exist sequences a=c0,c1,,cn=ba=c_{0}, c_{1}, \ldots, c_{n}=b and a=c0,c1,,cm=ba=c_{0}^{\prime}, c_{1}^{\prime}, \ldots, c_{m}^{\prime}=b^{\prime}, so the sequence b=cn,cn1,,c1,c0,c1,,cm=bb=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=c0,c1,,cn=bb=c_{0}, c_{1}, \ldots, c_{n}=b^{\prime} with bCa,bCab \in C_{a}, b^{\prime} \notin C_{a}. Then, concatenating with our sequence from aa to bb, we get a sequence from aa to bb^{\prime}, contradicting the assumption bCab^{\prime} \notin C_{a}. Thus, the second condition holds, and CaC_{a} is a cell. So aa lies in at least one cell.

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

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 reproduced verbatim; metadata (topic, difficulty) added by this project.