How would you prove the following:
Given three non-negative integers $a, b, c$; if $a \oplus b \oplus c = 0$ then $(a - k) \oplus (b - k) \oplus (c - k) > 0$ for any $0 < k \leq \min(a, b, c)$ ? (with $\oplus$ I mean bitwise XOR or nim-sum)
Regards.
$\endgroup$ 91 Answer
$\begingroup$Here is a rough outline for a 3-step proof.
Step 1 Rephrase to remove the subtraction, and the restriction on $k$. The original claim is equivalent to: for any $a', b', c'\geq 0$, and $k \geq 0$, if $a' \oplus b' \oplus c' = 0$, then $(a'+k)\oplus(b'+k)\oplus(c'+k) \neq 0$.
Step 2 Rephrase in terms of binary operations, more straightforward to work with. The claim is equivalent to: for any $a',b' \geq 0$, and $k > 0$, we have $(a'+k) \oplus (b'+k) \neq (a \oplus b) + k$.
Step 3 Prove this last form directly. As a warmup, start with the case $k=1$. In general, the smallest nonzero bit of $k$ will give a place in which $(a'+k) \oplus (b'+k)$ and $(a \oplus b) + k$ differ.
$\endgroup$
