a.) For all positive integer $k$ find the smallest positive integer $f(k)$ such that $5$ sets $s_1,s_2, \ldots , s_5$ exist satisfying: i. each has $k$ elements; ii. $s_i$ and $s_{i+1}$ are disjoint for $i=1,2,...,5$ ($s_6=s_1$) iii. the union of the $5$ sets has exactly $f(k)$ elements. b.) Generalisation: Consider $n \geq 3$ sets instead of $5$.
Problem
Source: China TST 1987, problem 1
Tags: combinatorics, Number theoretic functions, Sets, China, Team Selection Test
17.05.2005 02:56
Just a simple observation: if $n$ is even, we can take $s_1=s_3=...s_{n-1}$ and $s_2=s_4=...s_n$ so we need at most $2k$ different elements! It is obvius we cant do it with less than that number of elements! Now for odd $n$, each element appears at most in $\frac{n-1}{2}$ sets, so we get $f(k)\geq \frac{2n}{n-1}k$ I am not awake like to give a construction right now...
03.09.2006 16:27
I think $f_{2n+1}(k)\geq 2k+\frac{k}{2}$
04.09.2006 06:37
I choose $s_{1},...,s_{5},s_{4},s_{5},s_{4},s_{5},...$ work well
07.09.2006 23:49
Obviously, if $n$ is even, $f_{n}(k) = 2k$ for all k. We claim: $f_{2n+1}(k) = Ceil[\frac{(2n+1)k}{n}]$. Proof: For convenience, we will take the indices $i$ in $s_{i}$ modulo $2n+1$, and the elements as $1,2,...k$ modulo $k$. Suppose we have fewer than $\frac{(2n+1)k}{n}$ elements. For any $i$, $s_{i-1}$ and $s_{i+1}$ must both be disjoint from $s_{i}$, so they must share more than $\frac{(n-1)k}{n}$ elements. Applying this to $s_{1}, s_{3}, ..., s_{2n-1}$, we have that $s_{1}$ and $s_{2n-1}$ must share more than $\frac{k}{n}$ elements. Since $s_{0}$ and $s_{1}$ are disjoint, $s_{0}$ and $s_{2i-1}$ share fewer than $\frac{(n-1)k}{n}$ elements. This leaves fewer than $k$ elements for $s_{2n}$, which must be disjoint from both. On the other hand, let there be $m = Ceil[\frac{(2n+1)k}{n}]$ elements. Then we can satisfy the conditions by letting $s_{2i}={Floor[\frac{im}{2n+1}]+j | j = 1,2,...k}$. Then, for any $i$, we have $s_{2i}={Floor[\frac{im}{2n+1}]+j | j = 1,2,...k}$ $s_{2i+1}= s_{2i+2n+2}={Floor[\frac{im+nm+m}{2n+1}]+j | j = 1,2,...k}$. Since $Floor[\frac{im+nm+m}{2n+1}]-Floor[\frac{im}{2n+1}] \geq Floor[\frac{im+nm+m}{2n+1}-\frac{im}{2n+1}] = Floor[\frac{(n+1)m}{2n+1}] \geq k$, and $Floor[\frac{im+nm+m}{2n+1}]-Floor[\frac{im}{2n+1}] \leq Ceil[\frac{im+nm+m}{2n+1}-\frac{im}{2n+1}] \leq Ceil[\frac{(n+1)k}{n}] = m-k$, we see that $s_{2i}$ and $s_{2i+1}$ are disjoint. Since $s_{2i}$ covers all $s_{j}$ for $i = 1,2,...,2n+1$, we are done.