1
$\begingroup$

Given an integer $N$. Consider set $S=\{0, 1,…, 2^N−1\}$. How many subsets $A\subset S$ with Xor of all elements of $A$ as zero are there ?

Note : The Xor sum of an empty set is zero and Xor here is a bit wise operation.

Example : Let $N=2$ then answer is $4$

Here are $4$ subsets : empty set, $\{0\}$, $\{1,2,3\}$, $\{0,1,2,3\}$ as all have Xor sum as zero.

How to find this count for given $N$?

$\endgroup$
4
$\begingroup$

Any subset of $S$ must have a XOR-sum in $S$. Also, if you consider the subset $T=\{1=2^0,2^1,\ldots,2^{N-1}\}$ of $S$, given any element $s$ of $S$, there is a unique subset of $T$ with XOR-sum $s$, which is given by choosing the elements of $T$ corresponding to the bits in the binary expansion of $s$ which are $1$. Therefore, to find a subset $S'$ of $S$ with XOR-sum zero, you can choose the intersection of $S'$ with $S\setminus T$ freely, and then there is a unique way to choose $S'\cap T$ which will make the overall XOR-sum zero. The number of ways to choose a subset of $S$ with XOR-sum zero is then the number of subsets of $S\setminus T$, which is $$2^{\#(S\setminus T)}=2^{2^N-N}.$$

$\endgroup$
  • $\begingroup$ How to find this formula (2^2^N − N) MOD m where m is a prime number ? $\endgroup$ – user3804397 Feb 21 '15 at 8:48
2
$\begingroup$

Combine the following bits:

  • All the possible subset sums occur.
  • They all occur equally often, because the subset $S$ XOR-sums to zero if and only if the symmetric difference of $S$ and $\{k\}$ XOR-sums to $k$.

Therefore the fraction of subsets with zero sum is $1/2^N$ of all the subsets. In other words

$2^{2^N-N}$.


This could also be written using the language of vector space over the field $\Bbb{F}_2$. Essentially you are counting the number of words in a Hamming code.

$\endgroup$
  • $\begingroup$ @JykriLahtonen How to find this formula (2^2^N − N) MOD m where m is a prime number ? $\endgroup$ – user3804397 Feb 21 '15 at 8:47

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.