I have a discrete math problem I've stumbled onto during my research, but I'm not sure I have the math background to solve it. The problem is as follows:

There is a set, $C$, of $n$ elements, where $n = 3t+1$ for some integer $t$.

There are $n$ subsets of $C$, called $C_1 ... C_n$. Each subset contains $n-t$ elements of $C$, and the exact same $n-t$ elements never appear in more than $t$ subsets.

Each subset $C_t$ modifies itself by setting its content to the union of $n-t$ of the subsets of $C$ - this union must include $C_t$. Call the modified subsets $C_1'...C_n'$.

Prove that the intersection of all the modified subsets, $C_1' \cap C_2' \cap ... C_n'$, always has a cardinality of at least $n-t$. (or find a counterexample)

Can someone provide help or at least a starting point?


I found a counterexample.

$n = 10, t = 3, n - t = 7$
$C = \{1,2,3,4,5,6,7,8,9,10\}$
$C_1, C_2, C_3 = \{1,2,3,4,5,6,7\}$
$C_4, C_5, C_6 = \{1,2,3,4,5,6,8\}$
$C_7, C_8, C_9 = \{1,2,3,4,5,6,9\}$
$C_{10} = \{1,2,3,4,5,6,10\}$

All $C$ subsets have $\{1,2,3,4,5,6\}$ so it just becomes a matter of getting all $C'$ subsets to have the same 7th item.

$C_1', C_8' = C_1 \cup C_2 \cup C_3 \cup C_7 \cup C_8 \cup C_9 \cup C_{10} = \{...7,9,10\}$ (no 8)
$C_2', C_5' = C_1 \cup C_2 \cup C_3 \cup C_4 \cup C_5 \cup C_6 \cup C_{10} = \{...7,8,10\}$ (no 9)
$C_3', C_6', C_9' = C_1 \cup C_2 \cup C_3 \cup C_4 \cup C_5 \cup C_6 \cup C_7 = \{...7,8,9\}$ (no 10)
$C_4', C_7' = C_4 \cup C_5 \cup C_6 \cup C_7 \cup C_8 \cup C_9 \cup C_{10} = \{...8,9,10\}$ (no 7)
$C_{10}' = C_1 \cup C_2 \cup C_4 \cup C_5 \cup C_7 \cup C_8 \cup C_{10} = \{...7,8,9,10\}$ (all items)

The intersection of $C_1'$ through $C_{10}'$ is $\{1,2,3,4,5,6\}$, which has a cardinality of 6, which is less than $n-t$ (7).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.