In an $n$-element set $S$, several subsets $A_1, A_2, \ldots , A_k$ are distinguished, each consists of at least two, but not all elements of $S$. What is the largest $k$ that it’s possible to write down the elements of $S$ in a row in the order such that we don’t find all of the element of an $A_i$ set in the consecutive elements of the row?
Problem
Source: 239 2012 S6
Tags:
VicKmath7
25.08.2021 12:29
The answer is $n-2$. Let $S$ have elements $s_i$. The construction is to take the sets to be all pairs containing $s_n$, then obviously every permutation doesn't work. Now we prove by induction that $n-2$ works. Case 1. There is element $s_i$, which is not part of any 2-element subset (therefore, placing $s_i$ somewhere won't create a problem with its adjacent elements in the permutation!) Case 1.1 $s_i$ is not in any set $A_i$. Now delete $s_i$ and some $A_j$, take the permutation from the IH, and if the elements of $A_j$ are ordered consecutively, add $s_i$ somewhere between two elements of $A_j$. This works. Case 1.2 $s_i$ is in some $A_j$. Delete them both, and take the permutation from IH. Adding $s_i$ won't make problem with any other set except $A_j$. If the elements of $A_j$ without $s_i$ are ordered consecutively, add $s_i$ in one of the ends of the permutation, far from $A_j$ without $s_i$, and this fails $A_j$. Case 2. Each $s_i$ is in some 2-element subset. Then there is one element $s_i$ in exactly one such subset, otherwise we have two many subsets (at least $n$). So delete $s_i$ and this 2-element subset, and in the permutation from IH add $s_i$ anywhere else far from the other element of the subset, and now $s_i$ doesn't form other problem since it's in exactly one 2-element subset.