Ternario balanceado

Este es un sistema de numeración posicional no estándar. Su particularidad es que los dígitos pueden tomar uno de los valores -1, 0 y 1. Aun así, su base sigue siendo 3 (porque hay tres valores posibles). Como no es cómodo escribir -1 como dígito, usaremos de aquí en adelante la letra Z para ese propósito. Si parece un sistema bastante extraño, se puede ver en la imagen una de las computadoras que lo utilizan.

Estos son algunos de los primeros números escritos en ternario balanceado:

    0    0
    1    1
    2    1Z
    3    10
    4    11
    5    1ZZ
    6    1Z0
    7    1Z1
    8    10Z
    9    100

Este sistema permite escribir valores negativos sin un signo menos al frente: basta con invertir los dígitos de cualquier número positivo.

    -1   Z
    -2   Z1
    -3   Z0
    -4   ZZ
    -5   Z11

Nótese que un número negativo empieza con Z y uno positivo con 1.

Algoritmo de conversión

Es fácil representar un número dado en ternario balanceado pasándolo primero al sistema ternario normal. Cuando el valor está en ternario estándar, sus dígitos son 0, 1 o 2. Iterando desde el dígito menos significativo podemos saltar sin problemas cualquier 0 y 1; en cambio, un 2 debe convertirse en Z y sumar 1 al dígito siguiente. Los dígitos 3 deben convertirse en 0 bajo las mismas condiciones: esos dígitos no aparecen en el número inicialmente, pero pueden aparecer después de incrementar algunos 2.

Ejemplo 1: Convirtamos 64 a ternario balanceado. Primero reescribimos el número en ternario normal:

$$64_{10} = 02101_{3}$$

Lo procesamos desde el dígito menos significativo (el de más a la derecha):

• 1, 0 y 1 se dejan como están. (Porque 0 y 1 están permitidos en ternario balanceado)
• 2 se convierte en Z incrementando el dígito a su izquierda, de modo que obtenemos 1Z101.

El resultado final es 1Z101.

Convirtámoslo de vuelta al sistema decimal sumando los valores posicionales ponderados:

$$1Z101 = 81 \cdot 1 + 27 \cdot (-1) + 9 \cdot 1 + 3 \cdot 0 + 1 \cdot 1 = 64_{10}$$

Ejemplo 2: Convirtamos 237 a ternario balanceado. Primero reescribimos el número en ternario normal:

$$237_{10} = 22210_{3}$$

Lo procesamos desde el dígito menos significativo (el de más a la derecha):

• 0 y 1 se dejan como están. (Porque 0 y 1 están permitidos en ternario balanceado)
• 2 se convierte en Z incrementando el dígito a su izquierda, de modo que obtenemos 23Z10.
• 3 se convierte en 0 incrementando el dígito a su izquierda, de modo que obtenemos 30Z10.
• 3 se convierte en 0 incrementando el dígito a su izquierda (que por defecto es 0), y así obtenemos 100Z10.

El resultado final es 100Z10.

Convirtámoslo de vuelta al sistema decimal sumando los valores posicionales ponderados:

$$100Z10 = 243 \cdot 1 + 81 \cdot 0 + 27 \cdot 0 + 9 \cdot (-1) + 3 \cdot 1 + 1 \cdot 0 = 237_{10}$$

Problemas de práctica

• Topcoder SRM 604, Div1-250