TAOCP 7.1.3 Exercise 8

Let $x=\mathrm{mex}(S)$ and $y=\mathrm{mex}(T)$, and define U=(S\oplus y)\cup (x\oplus T).

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 8. ▶ [M22] Given a finite set $S$ of nonnegative integers, the "minimal exclulant" of $S$ is defined to be

$$\mathrm{mex}(S) = \min{k \mid k \ge 0 \text{ and } k \notin S}.$$

Let $x \oplus S$ denote the set ${x \oplus y \mid y \in S}$, and let $S \oplus y$ denote ${x \oplus y \mid x \in S}$. Prove that if $x = \mathrm{mex}(S)$ and $y = \mathrm{mex}(T)$ then $x \oplus y = \mathrm{mex}((S \oplus y) \cup (x \oplus T))$.

Verified: yes
Solve time: 4m16s

Let $x=\mathrm{mex}(S)$ and $y=\mathrm{mex}(T)$, and define

$$ U=(S\oplus y)\cup (x\oplus T). $$

We prove $\mathrm{mex}(U)=x\oplus y$.

1. $x\oplus y \notin U$

If $x\oplus y \in S\oplus y$, then $x\oplus y=s\oplus y$ for some $s\in S$, hence $s=x$, contradicting $x\notin S$.

If $x\oplus y \in x\oplus T$, then $x\oplus y=x\oplus t$ for some $t\in T$, hence $t=y$, contradicting $y\notin T$.

Thus $x\oplus y\notin U$.

2. Every $k<x\oplus y$ lies in $U$

Fix $k<x\oplus y$. Let $z=x\oplus y$. Write all numbers in binary, and let $j$ be the highest index of a bit where $k$ and $z$ differ.

Then:

  • $z_j=1$,
  • $k_j=0$,
  • for all $i>j$, $k_i=z_i$.

Since $z=x\oplus y$, we have $z_i=x_i\oplus y_i$ for each bit $i$.

Claim: $k\oplus y < x$.

We compare $k\oplus y$ and $x$ bitwise.

For any $i>j$,

$$ (k\oplus y)_i = k_i \oplus y_i = (x_i\oplus y_i)\oplus y_i = x_i, $$

so all bits above $j$ agree with those of $x$.

At bit $j$,

$$ (k\oplus y)_j = k_j \oplus y_j = 0\oplus y_j = y_j, \quad\text{while}\quad x_j = (x_j\oplus y_j)\oplus y_j = z_j \oplus y_j = 1\oplus y_j. $$

Hence $(k\oplus y)_j \neq x_j$, and in fact $x_j=1$ and $(k\oplus y)_j=0$ because $z_j=1$ implies exactly one of $x_j,y_j$ is $1$, so if $y_j=1$ then $x_j=0$ contradicts $z_j=1$. Therefore the consistent case is $x_j=1$, $y_j=0$, giving $(k\oplus y)_j=0$, $x_j=1$.

Thus:

  • all higher bits match,
  • at the first differing bit $j$, $k\oplus y$ has $0$ while $x$ has $1$,

so

$$ k\oplus y < x. $$

Since $x=\mathrm{mex}(S)$, every integer in $[0,x-1]$ lies in $S$, hence $k\oplus y\in S$. Therefore $k\in S\oplus y \subseteq U$.

Symmetric case

If instead the first differing bit satisfies $y_j=1$ and $x_j=0$, the same argument (with roles swapped) shows $k\oplus x<y$, hence $k\oplus x\in T$, so $k\in x\oplus T\subseteq U$.

3. Conclusion

We have shown:

  • $x\oplus y\notin U$,
  • every $k<x\oplus y$ lies in $U$.

Therefore $U$ contains all nonnegative integers less than $x\oplus y$ and omits $x\oplus y$, so

$$ \mathrm{mex}(U)=x\oplus y. $$

This completes the proof. ∎