I have two positive integers, $a$ and $b$, with $a$ xor $b = m$. Here, xor is the usual binary operator applied to all digits of $a$ and $b$ (in binary).
I was wondering whether it is possible to to decrease this result to a given number $n<m$, by decreasing either $a$ or $b$ to a smaller positive integer.
I.e., I want to find $a'\in\{0,1,\dots,a-1\}$ such that $a'$ xor $b = n$ or $b'\in\{0,1,\dots,b-1\}$ such that $a$ xor $b' = n$.
Intuitively, I think this is always possible, but it turned out to be rather difficult to prove (due to the strange behaviour of $\text{xor}$).
My attempt:
We want $a'\text{ xor }b = n \Leftrightarrow a'= n\text{ xor } b$
or $a\text{ xor }b' = n \Leftrightarrow b'= n\text{ xor } a$
So, we have to prove that either $n\text{ xor } b < a$ or $n\text{ xor } a < b$.
I tried to compare the digits of $a,b$ and $n$, but with no results.
If you express $n$ in binary, you can find $a'=b \operatorname{xor} n$ and $b'=a \operatorname{xor} n$. This works because $\operatorname{xor} $ is idempotent- $c \operatorname{xor} d \operatorname{xor} d=c$
Find the highest order bit in $m \operatorname{xor} n$. We know that it is a $1$ in $m$ and $0$ in $n$ because $m \gt n$. We know that $a$ and $b$ differ in this bit because $a \operatorname{xor} b$ has a $1$ there. WOLOG assume it is $a$ that has a $1$ in this bit. Then $a'$ will agree with $a$ over all the higher bits and have a zero here so that the $\operatorname{xor}$ with $b$ comes out $0$. Thus $a' \lt a$.