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$?


1 Answer 1


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, 2017 at 1:31
  • $\begingroup$ @rus9384: What? 3-SAT has a formula associated which is completely missing here. $\endgroup$
    – Aryabhata
    Aug 2, 2017 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, 2017 at 1:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .