Quick encoding of balanced vectors It is easy to see that for any $n$ there exists a 1-1 mapping $F$ from {0,1}$^n$ to {0,1}$^{n+O(\log n)}$ such that for any $x$ the vector $F(x)$ is "balanced", i.e., it has equal number of 1s and 0s. Is it possible to define such $F$ so that given $x$ we can compute $F(x)$  efficiently ?

Thanks.
Let's consider $n$-bit strings $x$. Definitions:


$f(x,i)$ = bit string $x$ with last $i$ bits complemented.
$b(x)$ = "imbalance" of $x$: number of 1s in $x$ $-$ number of 0s in $x$.


Now fix a string $x$. Consider the function $g(i) = b(f(x,i))$. Observations:


$g(0) = b(x)$.
$g(n) = -g(0)$.
$|g(i) - g(i+1)| = 2$ for all $i$. We either remove one 0 and add one 1 or vice versa.


Now it follows that there exists an $i$ such that $-1 \le g(i) \le +1$.

Hence we can construct an $(n+O(\log n))$-bit string $y$ as follows: concatenate $f(x,i)$ and the binary encoding of the index $i$. The absolute value of the imbalance of $y$ is $O(\log n)$. Moreover, we can recover $x$ given $y$; the mapping is bijection.

Finally, you can add $O(\log n)$ dummy bits that reduce the imbalance of $y$ from $O(\log n)$ to $0$.