For a given integer , let be distinct three-element subsets of the set such that for each the sets contain exactly one element. Determine the maximal possible value of for each .
Solution
For each let be the maximal value of . Readily and . If each number belongs to at most 2 subsets. Thus, . Therefore since the example works.
Let . If some element belongs to all subsets then readily . The example for odd shows that in this case .
Suppose that no element belongs to all subsets. If some number belongs to at least 4 subsets, say and some does not contain then should contain at least 4 elements since it contains at least one element from each for , contradiction.
Suppose that each belongs to at most 3 subsets. Let us fix one of the subsets: . Then there are at most 2 subsets containing each , and there are at most subsets. The example for 7 subsets: .
Thus, .
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.