Consider $n$ independent tosses of a fair coin; the sample space has $2^n$ elements. Let $R_n(x)$ be the length of the longest run of heads in outcome $x$. We know that $$E[R_n]=\Theta (\log n)$$ csun.edu/~hcmth031/research.html
Can we pair outcomes such that for every pair $(x,y)$, we have $\max$ {$R_n(x),R_n(y)$}$=\Omega(\log n)$.
In case of partition into groups of two elements is impossible, can it be done if we divide the sample space into groups of no more than $k$ elements ($k$ is const)?