Let I have a $0-1$ set of $n$ elements, where $n\ge 3$.

Now this set has $C_n^3$ triples (subsets of 3 elements).

Each triple can have either even amount of 1's (0 or 2) or odd (1 or 3). I'll call them even/odd triples.

Now the question: for any number $p\in[0,~C_n^3]$, there exists a set that has $p$ even triples.

Example for $n = 4$:

  1. Set has no even triples. Such set is $\{1,1,1,1\}$ and all of it's triples are $\{1,1,1\}$.
  2. Set has one even triple. Such set is $\{1,0,0,0\}$. One triple is $\{0,0,0\}$ and $3$ others are $\{1,0,0\}$.
  3. Set has two even triples. Such set is $\{1,1,0,0\}$. $2$ triples are $\{1,1,0\}$ and other $2$ are $\{1,0,0\}$.

Negating 1st and 2nd sets will give examples of sets containing $3$ and $4$ even triples.

This shows that for $n \leq 4$ answer for question is true, but is it true for any $n$?


Suppose the set has $m$ ones and $n$ zeroes and let $N = m + n$

Then the number of even triples is $$\binom{m}{2} + \binom{n}{3}$$

For a given $N$ this takes at most $N$ different values (vary $m$ from $0$ to $n$), but $\binom{N}{3}$ is $\theta(N^3)$.

Hence the answer is no, there are only finitely many $N$ for which your statement is true, and those $N$ necessarily satisfy $N \ge \binom{N}{3}$.

  • $\begingroup$ Well, the formula is not correct and if there would exist correct one, we could solve XOR-3-SAT in linear time. $\endgroup$ – rus9384 Aug 2 '17 at 1:31
  • $\begingroup$ @rus9384: What? 3-SAT has a formula associated which is completely missing here. $\endgroup$ – Aryabhata Aug 2 '17 at 1:34
  • $\begingroup$ In fact XOR-3-SAT just gives set of triples and each triple either must have even or odd amount of positive variables. $\endgroup$ – rus9384 Aug 2 '17 at 1:36

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.