Let be the set of -tuples , , . A triad , where , , , of distinguished elements of is called good, if there exists at least one for which the sets and are equal. A subset of is called good, if every three elements of form a good triad. Prove that every good subset of has at most elements.
Solution
We will use induction with respect to . The case for is obvious. We suppose that every good subset of has at most elements.
Let . We define the subsets similarly, that is
Since is a good set and is its subset, it follows that is also good. It means that for every three elements of there exists a coordinate which is different for every two of them. This coordinate cannot be the last one because cannot be there. Therefore the set produced from the elements of by deleting the last coordinate is a good subset of .
Moreover, we observe that, if , then .
In fact, if , then there would exist an element such that , where arise from by adding and , respectively, as last coordinate. However, if then is any other element of , it cannot have as last coordinate , and so will not form a good triad, absurd. Hence, from the induction hypothesis we have
Similarly, we get that: . Since every element of appears exactly in two of the sets , we conclude: