hellman_'s blog

By hellman_, 8 years ago, In English

Hello everyone!

Here's an interesting problem. Sounds easy at first but I could not find a solution that matches experimental results. Maybe I am missing some simple observation.


You are given two integers 1 ≤ l1, l2 ≤ 2n. Consider two random subsets of n-bit vectors of sizes l1, l2 respectively. Let

, where & is a bitwise AND.

Compute the expected size of R (in polynomial in n time). Computing maximum possible size of R is interesting too.

An easier version is when bitwise AND is replaced by bitwise XOR, it is also interesting.

NOTE: I am not sure that this problem has a solution.

Full text and comments »

  • Vote: I like it
  • +27
  • Vote: I do not like it