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
Unable to parse markup [type=CF_TEX]
. Consider two random subsets of n-bit vectorsUnable to parse markup [type=CF_TEX]
of sizesUnable to parse markup [type=CF_TEX]
respectively. LetUnable to parse markup [type=CF_TEX]
, 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.
