XOR de los tres enteros

Question

¿Cómo probarías lo siguiente?

Dados tres enteros no negativos$a, b, c$; Si$a \oplus b \oplus c = 0$ entonces$(a - k) \oplus (b - k) \oplus (c - k) > 0$ para cualquier$0 < k \leq min(a, b, c)$? (con$\oplus$ me refiero a XOR en modo bit o suma nim)

Saludos.

Answer 1

Aquí un esbozo para un 3-paso la prueba.

Paso 1 Reformular para quitar la resta, y la restricción en $k$. La demanda original es equivalente a: para cualquier $a', b', c'\geq 0$, e $k \geq 0$ si $a' \oplus b' \oplus c' = 0$,, a continuación,$(a'+k)\oplus(b'+k)\oplus(c'+k) \neq 0$.

Paso 2 Reformular en términos de las operaciones binarias, más sencillo trabajar con ellos. La afirmación es equivalente a: para cualquier $a',b' \geq 0$, e $k > 0$, tenemos $(a'+k) \oplus (b'+k) \neq (a \oplus b) + k$.

Paso 3 Probar esta última forma directa. Como calentamiento, iniciar con el caso de $k=1$. En general, el más pequeño distinto de cero bits de $k$ le dará un lugar en el que $(a'+k) \oplus (b'+k)$ e $(a \oplus b) + k$ difieren.