¿Por qué la raíz de este árbol tiene que ser "1"?

Question

Organizar $2^{n-1}-1$ ceros y $2^{n-1}$ en un equilibrado árbol binario completo de profundidad $n$. Si queremos que el número de aristas que conectan a la misma (y respectivamente diferente) dígitos son los mismos, entonces se afirma que la raíz de este árbol tiene que ser una sola. ¿Por qué es eso?

Por ejemplo, si $n=2$, entonces tenemos que organizar 1 cero y 2. Una disposición que hace que el número de aristas que conectan los mismos dígitos (que en este caso es sólo uno: el borde con un "+" que conecta a 2,) y el número de aristas que conectan dos dígitos diferentes (que en este caso es también uno: el borde con un "-") son los mismos. Tenga en cuenta que la raíz de este árbol es unexceptionally 1.

      1
    /   \
 + /     \ -
  /       \
 1         0

Y aquí es un caso donde la $n=3$.

          1
        /   \
     + /     \ -
      /       \
     1         0
  + / \ -   + / \ -
   /   \     /   \
  1     0   0     1

De nuevo, vemos que la raíz es un uno. Si cambiamos la raíz a cero, sin embargo, entonces nunca podremos encontrar una disposición que hace que el número de "+" aristas es igual al número de "-" los bordes. ¿Por qué es eso?

Answer 1

Considere la posibilidad de un equilibrio de profundidad-$n$ árbol binario de $0$'s y $1$'s y la etiqueta de cada borde de la $+$ o $-$ como usted lo hizo. Si todos los bordes se $+$ $2^n-1$ vértices sería el mismo que el de la raíz. Puede cambiar un borde de $+$ $-$o viceversa, si usted mueve de un tirón todos los vértices por encima de ese límite (es decir, aquellos que el borde está en el camino desde el vértice de la raíz). Siempre se trata de voltear un número impar de vértices, por lo que la paridad de los números de $1$'s y de $0$'s de los cambios. Si usted hace un número par de borde-los interruptores, tiene la misma paridad con el que comenzó. Ahora el árbol ha $2^n-2$ bordes, y usted debe hacer $2^{n-1}-1$ interruptores para obtener un número igual de $+$ $-$ bordes. Si $n \ge 2$, esto es extraño, por lo que la paridad es diferente que en el inicio. En el principio, hubo un número impar de la misma raíz, por lo que después de la conmutación debe tener un número par. Puesto que usted desea que el número de $0$'s para ser impar, la raíz debe ser $1$.

Answer 2

Digamos que usted ha $k$ borde incidencias en $1$s y $l$ borde incidencias en $0$s. Entonces si $x$ bordes conectar un $0$$1$, lo que deja a $k-x$ incidencias en $1$s, por lo que hay $(k-x)/2$ bordes de la conexión de un $1$$1$, y de la misma manera $(l-x)/2$ bordes de la conexión de un $0$$0$. Entonces la condición de que hay el mismo número de $+$$-$, de bordes

$$ \frac{k-x}2+\frac{l-x}2=x\;, $$

y por lo tanto $x=(k+l)/4$. Por lo tanto, hay

$$ \frac{k-x}2=\frac{k-(k+l)/4}2=\frac38k-\frac18l $$

los bordes de la conexión de un $1$$1$. Intercambio de a $0$ $1$ entre una sucursal y una hoja de cambios de esta cantidad por $\pm1$, por lo que la única manera de cambiar si es un entero es cambiar la raíz, y resulta que es un entero y si la raíz es un $1$ y no un entero si no lo es.