A set $S$ has $7$ elements. Several $3$-elements subsets of $S$ are listed, such that any $2$ listed subsets have exactly $1$ common element. What is the maximum number of subsets that can be listed?
Problem
Source: Malaysia IMONST 1 P19
Tags: combinatorics, Subsets
19.09.2020 03:10
Trước hết ta có nhận xét rằng $\forall \varepsilon >0$ thì luôn tồn tại $ n_o \in \mathbb{N^*}$ sao cho $\forall n > n_o$ ta luôn có $$A-\varepsilon \leq \frac{x_n-x_{n-1}}{y_n-y_{n-1}}\leq A+\varepsilon (1)$$Lấy $k>n_o$, khi đó $(1)$ tương đương với $$\left ( A-\varepsilon \right )\left ( y_n-y_{n-1} \right )\leq x_n-x_{n-1}\leq \left ( A+\varepsilon \right )\left ( y_n-y_{n-1} \right )\\ \Leftrightarrow \left ( A-\varepsilon \right )\sum_{i=n_o}^{k}\left ( y_i-y_{i-1} \right ) \leq \sum_{n_o}^{k}\left ( x_i-x_{i-1} \right ) \leq \left ( A+\varepsilon \right )\sum_{i=n_o}^{k}\left ( y_i-y_{i-1} \right ) \\ \Leftrightarrow \left ( A-\varepsilon \right )\left ( y_k-y_{n_o} \right ) \leq x_k-x_{n_o} \leq \left ( A+\varepsilon \right )\left ( y_k-y_{n_o} \right ) \\ \Leftrightarrow \left ( A-\varepsilon \right ) \left ( 1-\dfrac{y_{n_0}}{y_{k}} \right ) + \dfrac{x_{n_o}}{y_k} \leq \dfrac{x_k}{y_k} \leq \left ( A+\varepsilon \right ) \left( 1- \dfrac{y_{n_0}}{y_{k}} \right ) +\dfrac{x_{n_o}}{y_k} $$. Chú ý rằng $\lim \left ( \left ( A-\varepsilon \right ) \left ( 1-\dfrac{y_{n_0}}{y_{k}} \right ) + \dfrac{x_{n_o}}{y_k} \right) = \lim \left ( \left ( A+\varepsilon \right ) \left ( 1-\dfrac{y_{n_0}}{y_{k}} \right ) + \dfrac{x_{n_o}}{y_k} \right) = A$ ( do $\varepsilon $ ta có thể chọn nhỏ tùy ý và $\lim y_n = +\infty $ ). Theo nguyên lí kẹp ta có $\lim \dfrac{x_k}{y_k}=A$ tức là $\lim \dfrac{x_n}{y_n}=A. \ \ \blacksquare $
19.09.2020 03:10
Is this IMONST 1 senior P19?
19.09.2020 03:11
Payacc wrote: Trước hết ta có nhận xét rằng $\forall \varepsilon >0$ thì luôn tồn tại $ n_o \in \mathbb{N^*}$ sao cho $\forall n > n_o$ ta luôn có $$A-\varepsilon \leq \frac{x_n-x_{n-1}}{y_n-y_{n-1}}\leq A+\varepsilon (1)$$Lấy $k>n_o$, khi đó $(1)$ tương đương với $$\left ( A-\varepsilon \right )\left ( y_n-y_{n-1} \right )\leq x_n-x_{n-1}\leq \left ( A+\varepsilon \right )\left ( y_n-y_{n-1} \right )\\ \Leftrightarrow \left ( A-\varepsilon \right )\sum_{i=n_o}^{k}\left ( y_i-y_{i-1} \right ) \leq \sum_{n_o}^{k}\left ( x_i-x_{i-1} \right ) \leq \left ( A+\varepsilon \right )\sum_{i=n_o}^{k}\left ( y_i-y_{i-1} \right ) \\ \Leftrightarrow \left ( A-\varepsilon \right )\left ( y_k-y_{n_o} \right ) \leq x_k-x_{n_o} \leq \left ( A+\varepsilon \right )\left ( y_k-y_{n_o} \right ) \\ \Leftrightarrow \left ( A-\varepsilon \right ) \left ( 1-\dfrac{y_{n_0}}{y_{k}} \right ) + \dfrac{x_{n_o}}{y_k} \leq \dfrac{x_k}{y_k} \leq \left ( A+\varepsilon \right ) \left( 1- \dfrac{y_{n_0}}{y_{k}} \right ) +\dfrac{x_{n_o}}{y_k} $$. Chú ý rằng $\lim \left ( \left ( A-\varepsilon \right ) \left ( 1-\dfrac{y_{n_0}}{y_{k}} \right ) + \dfrac{x_{n_o}}{y_k} \right) = \lim \left ( \left ( A+\varepsilon \right ) \left ( 1-\dfrac{y_{n_0}}{y_{k}} \right ) + \dfrac{x_{n_o}}{y_k} \right) = A$ ( do $\varepsilon $ ta có thể chọn nhỏ tùy ý và $\lim y_n = +\infty $ ). Theo nguyên lí kẹp ta có $\lim \dfrac{x_k}{y_k}=A$ tức là $\lim \dfrac{x_n}{y_n}=A. \ \ \blacksquare $ I don't think this is the right problem...
19.09.2020 07:24
Note that each element from $S$ can appear in at most $3$ such subsets. If it appears in at least $k$ subsets where $k\geq 4,$ then the other $2k$ elements of those $k$ subsets will have to be distinct, otherwise some two of those $k$ subsets will have more than one element in common. So $\mid S\mid\geq 2k+1\geq 9,$ a contradiction. Thus, if there are $t$ such $3-$element subsets then total number of elements in them $\leq 3\times 7=21.$ So $3t\leq 21$ and $t\leq 7.$ Finally, here's an example showing that $t=7$ can be achieved. Let the elements in $S$ be $\{a,b,c,d,e,f,g\}.$ Then among the seven subsets of $S$ $\{a,b,c\},\ \{a,d,e\},\ \{a,f,g\}, \ \{b,d,f\}, \ \{b,e,g\}, \ \{c,e,f\}, \ \{c,d,g\}$ if we choose any two they have exactly one element in common.
19.09.2020 13:13
One can easily see that each number can appear inonly 3 lists or less so maximum of 7 lists and is achived by 123 145 167 246 257 347 356