Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want a set system for which:

  1. Every set contains exactly 5 natural numbers.
  2. For any given natural number $1\le k\le n$ there are 3 sets in the system whose symmetric difference yield the singleton $\{k\}$ (in other words, every element besides $k$ which appears in the sets appears in exactly 2 of them, and $k$ itself appears once or three times.
  3. The system contains $o(n)$ sets (asymptotically less than $n$ sets).

The sets can contain natural numbers larger than $n$ if this helps.

Note that without condition 3 the construction is not difficult: $\{1,2,3,4,5\},\{2,3,6,7,8\},\{4,5,6,7,8\}$ are 3 sets whose symmetric difference yields $\{1\}$, and so a solution with exactly $3n$ sets can be constructed.

Also, if there is an easy way to extend such constructions for sets of size larger than 5 and symmetric difference of an odd number different than 3 I'd be happy to hear about it, but I'm not sure that even for my parameters there is a solution.

share|improve this question
Surely there has to be at least $\frac{n}{5}$ sets. –  David Bevan Nov 30 '11 at 12:51
Now I think that this is a simple linear algebra problem (sets are vectors over $\mathbb{Z}_2$) –  Gadi A Nov 30 '11 at 13:04
In your example, there are no 3 sets whose symmetric difference gives $\{2\}$. Also, as David Bevan points out $o(n)$ is certainly impossible. Please restate the question more clearly. –  Marc van Leeuwen Nov 30 '11 at 13:22
@Marc: The question is clear. Gadi’s example shows how to construct three sets whose symmetric difference is a specified singleton. In other words, it solves the $n=1$ case. For $n=2$, add the set $\{1,3,6,7,8\}$: it together with his first and third sets will yield $\{2\}$. Or add an independent triple: $\{2,9,10,11,12\},\{9,10,13,14,15\},\{11,12,13,14,15\}$. –  Brian M. Scott Nov 30 '11 at 17:00
@Brian Scott: Thanks, I had missed the value $n=1$ in the example. However the question of what to make of $o(n)$ remains open. To be explicit; that requires asymptotically less than any constant times $n$, and for the constant $\frac15$ this is clearly impossible. –  Marc van Leeuwen Nov 30 '11 at 22:53
show 1 more comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.