Maths Olympiad Prep

Library / /11 of 37

Combinatorics Difficulty 7.7 National olympiad, round 2 Find the answer

Let nn be an integer greater than 11. For a positive integer mm, let Sm={1,2,,mn}S_{m}= \{ 1,2,\ldots, mn\}. Suppose that there exists a 2n2n-element set TT such that
(a) each element of TT is an mm-element subset of SmS_{m};
(b) each pair of elements of TT shares at most one common element;
and
(c) each element of SmS_{m} is contained in exactly two elements of TT.

Determine the maximum possible value of mm in terms of nn.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let n n be an integer greater than 1. For a positive integer m m , let Sm={1,2,,mn} S_{m} = \{ 1, 2, \ldots, mn \} . Suppose that there exists a 2n 2n -element set T T such that:
(a) each element of T T is an m m -element subset of Sm S_{m} ;
(b) each pair of elements of T T shares at most one common element; and
(c) each element of Sm S_{m} is contained in exactly two elements of T T .

We aim to determine the maximum possible value of m m in terms of n n .

First, we show that m2n1 m \leq 2n - 1 . By condition (b), there are at most (2nn)\binom{2n}{n} elements of Sm S_{m} which are in 2 sets in T T . However, by condition (c), every element of Sm S_{m} is in 2 sets in T T , so Sm=mn(2nn)=(2n)(2n1)2=n(2n1)|S_{m}| = mn \leq \binom{2n}{n} = \frac{(2n)(2n-1)}{2} = n(2n-1), and thus m2n1 m \leq 2n - 1 .

Now, to see that 2n1 2n - 1 is achievable, consider a complete graph K2n K_{2n} . Note that this K2n K_{2n} has n(2n1) n(2n-1) edges, so we label the edges with distinct elements of S2n1 S_{2n-1} . Let T T be the family of sets formed by taking each vertex and creating the set of labels of incident edges. Any two sets in T T have exactly one element in common—the label of the edge between them—so condition (b) is satisfied. Each element of Sm S_{m} is in exactly two elements of T T : the two endpoints of the edge with the given label, satisfying condition (c). Condition (a) is also satisfied because every vertex in a K2n K_{2n} has degree 2n1=m 2n-1 = m , so every element of T T has m m elements. Finally, since a K2n K_{2n} has 2n 2n vertices, T=2n|T| = 2n, as desired.

Thus, the maximum possible value of m m is:
2n1 \boxed{2n - 1}

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.