Trazo de figuras 2

Cuando una figura no cumple las condiciones de Euler para el punto de inicio y fin deseados, la solución no es rendirse, sino agregar repeticiones: al recorrer una línea dos veces, es como si en el dibujo existiera una línea adicional idéntica. El efecto de esa línea adicional es que los grados de los vértices cambian, y con ellos su paridad.

En lugar de pensar en recorrer dos veces una línea, piensa que la figura se transforma en una nueva figura en la que hemos duplicado ciertos trazos. Si la nueva figura ya cumple las condiciones de Euler, entonces sí podremos recorrerla sin repetir nada, y la longitud total será la suma de las líneas originales más las repetidas.

Veamos el efecto de repetir una línea.

En el ejemplo, A y B originalmente tenían grado $1$, es decir, ambos eran impares. Al repetir la línea, cada uno pasa a tener grado $2$, por lo que ambos se vuelven pares. Esa es la operación básica.

Efecto de repetir un camino

No siempre conviene, o no siempre es posible, repetir una sola línea aislada. Muchas veces repetiremos un camino, es decir, una sucesión de líneas que une dos vértices. Por ejemplo, repetir el camino $P \to Q \to R$ significa recorrer dos líneas una vez extra: la línea $PQ$ y la línea $QR$.

¿Qué efecto tiene eso sobre las paridades?

• Los extremos del camino, $P$ y $R$, ven aumentar su grado en $1$, por lo que cambian de paridad.
• Los vértices intermedios, como $Q$, reciben dos líneas repetidas (una para entrar y otra para salir), por lo que su grado aumenta en $2$, y su paridad no cambia.

Entonces, repetir un camino es una herramienta muy útil: permite cambiar la paridad de exactamente dos puntos de la figura, dejando a los demás igual. Es exactamente lo que necesitamos para ajustar las condiciones de Euler.

Podemos resumir el efecto en una tabla:

En todos los problemas de este tema usaremos la misma idea:

$$L_{\min} = L_{\text{figura}} + L_{\text{repeticiones}}$$

Donde:

• $L_{\text{figura}}$ es la longitud de todas las líneas de la figura original, es decir, la suma de las longitudes de todos los trazos que debemos recorrer al menos una vez.
• $L_{\text{repeticiones}}$ es la suma mínima de las longitudes de los caminos repetidos para lograr que la figura transformada tenga las condiciones de paridad necesarias.

Por eso, el problema se reduce a dos tareas:

1. Calcular la longitud total de la figura original.
2. Determinar cuáles son los puntos cuya paridad debe cambiar y emparejarlos de la forma más barata posible, midiendo la distancia más corta entre ellos a lo largo de la figura.

No es necesario construir físicamente todo el recorrido. Si la figura transformada tiene $0$ o $2$ impares cumpliendo las condiciones de inicio y fin, el teorema de Euler nos asegura que existe un recorrido continuo que usa cada línea exactamente una vez sobre la figura transformada; es decir, que usa cada línea original una vez y cada camino repetido una vez más.

Cuando se fija el punto de inicio y el punto de fin, no cualquier cantidad de impares es válida. Recuerda:

• Si inicio $=$ fin, el recorrido es cerrado. Para que exista un recorrido continuo que use todas las líneas, la figura transformada debe tener todos sus vértices pares.
• Si inicio $\neq$ fin, el recorrido es abierto. La figura transformada debe tener exactamente dos vértices impares, que deben ser justamente el punto de inicio y el punto de fin.

Entonces, el procedimiento general es comparar la paridad original de la figura con la paridad deseada:

1. Si un punto originalmente par debe seguir par, no lo tocamos.
2. Si un punto originalmente impar debe seguir impar, no lo tocamos.
3. Si un punto originalmente par debe volverse impar, lo incluiremos en la lista de puntos a cambiar.
4. Si un punto originalmente impar debe volverse par, lo incluiremos en la lista de puntos a cambiar.

Los puntos a cambiar forman un conjunto $S$. Como cada repetición de camino cambia exactamente dos puntos, el número de elementos de $S$ siempre será par. Luego, la tarea es emparejar esos puntos mediante caminos que se repetirán, de modo que la suma de longitudes de esos caminos sea mínima.

Podemos resumir las metas de paridad en esta tabla:

Observa que en el caso «inicio $\neq$ fin» la lógica siempre es la misma: la meta es que los únicos impares sean inicio y fin. Si uno de ellos ya era impar originalmente, se salva; si era par, debe convertirse en impar. Los demás impares originales siempre deben convertirse en pares.

Para resolver cualquier problema de recorrido mínimo sujeto a condiciones, se puede seguir este procedimiento:

Paso 1: Calcular la longitud de la figura original

Suma las longitudes de todas las líneas que forman la figura. A esta cantidad la llamaremos $L_{\text{figura}}$.

Paso 2: Identificar los vértices impares

Recorre mentalmente la figura y anota, para cada punto, cuántas líneas concurren en él. Marca aquellos con grado impar. No olvides considerar también los puntos intermedios que surgen por cruces de líneas.

Paso 3: Determinar los puntos que deben cambiar de paridad

Aplica la tabla anterior según la condición de inicio y fin. Forma el conjunto $S$ de puntos cuya paridad original debe ser transformada.

Paso 4: Calcular distancias más cortas entre los puntos de $S$

La distancia entre dos puntos de la figura no es la distancia en línea recta, sino la longitud del camino más corto que va de uno a otro siguiendo las líneas de la figura. En una estructura de alambre, a veces hay varias rutas posibles; debes elegir la que tenga menor longitud.

Paso 5: Emparejar los puntos de $S$ para minimizar la suma

Debes formar parejas con los puntos de $S$. Cada pareja se unirá mediante un camino repetido, y el costo de esa pareja será la distancia más corta entre sus dos puntos. La suma de los costos de todas las parejas será $L_{\text{repeticiones}}$.

Paso 6: Aplicar la fórmula fundamental

Finalmente:

$$L_{\min} = L_{\text{figura}} + L_{\text{repeticiones}}$$

Cuando el inicio y el fin son el mismo punto, el recorrido debe ser cerrado. Por el teorema de Euler, la figura transformada debe tener todos los vértices pares.

Por lo tanto:

• Si la figura original ya tiene todos sus vértices pares, no hay que repetir nada. La longitud mínima es simplemente la longitud de la figura.
• Si la figura original tiene $2,4,6,\ldots$ impares, debemos convertirlos todos en pares. El conjunto $S$ será exactamente el conjunto de todos los impares originales.

Mini ejemplo conceptual. Si una figura tiene cuatro impares $a,b,c,d$, debemos emparejarlos en dos parejas. Si las distancias más cortas entre ellos son:

$$d(a,b)=3,\quad d(c,d)=4,\quad d(a,c)=6,\quad d(b,d)=5,\ldots$$

deberemos comparar los emparejamientos posibles: $(a,b)$ con $(c,d)$ cuesta $3+4=7$; $(a,c)$ con $(b,d)$ cuesta $6+5=11$. Nos quedamos con el de menor costo.

En este caso, repetir un camino entre dos impares convierte a ambos en pares, exactamente lo que se necesita.

Aquí el recorrido es abierto. La figura transformada debe tener exactamente dos impares: el punto de inicio y el punto de fin.

Hay tres subcasos según la paridad original de esos puntos:

2.1. Inicio y fin son ambos impares originalmente

Si los puntos de inicio y fin ya eran impares, entonces no hay que cambiar su paridad. Ellos serán los únicos impares finales. Los demás impares originales deben convertirse en pares.

Por lo tanto, $S$ será el conjunto de impares originales, pero excluyendo al inicio y al fin. Luego emparejamos ese conjunto y repetimos los caminos elegidos.

2.2. Inicio es par y fin es impar, o viceversa

Supón que el inicio es par y el fin es impar. El inicio debe volverse impar; el fin ya es impar y se mantiene. Los demás impares originales deben volverse pares.

Entonces, $S$ estará formado por:

• el punto de inicio (par que debe volverse impar),
• todos los impares originales excepto el fin.

Si la situación es al revés (inicio impar, fin par), se incluye el fin en $S$ y se excluye el inicio.

Este es uno de los casos que más suele aparecer en los problemas de admisión. La clave es no olvidar que el punto par debe cambiar a impar; si lo omites, la figura final tendrá solo un impar o dos impares equivocados y el recorrido no existirá.

2.3. Inicio y fin son ambos pares originalmente

Cuando ambos son pares, los dos deben volverse impares. Además, todos los impares originales deben volverse pares. Así, $S$ incluye:

• el inicio,
• el fin,
• todos los impares originales.

En este subcaso, es posible emparejar un punto par con un punto impar: al repetir el camino entre ambos, el par se vuelve impar y el impar se vuelve par, con lo que se «corrigen» mutuamente.

La parte más delicada es decidir qué parejas formar. En figuras pequeñas se puede hacer probando todas las combinaciones razonables. En figuras más grandes, conviene:

1. Calcular primero las distancias más cortas. Identifica para cada par de puntos de $S$ cuál es la ruta más corta siguiendo la figura. No asumas que la distancia es la línea recta entre ambos, porque en un alambrado la línea recta puede no existir.

2. Emparejar puntos cercanos. Casi siempre conviene unir puntos que estén próximos entre sí a lo largo de la figura. Por ejemplo, si dos impares están separados por un tramo de $2$ cm, suele ser mejor emparejarlos entre ellos que unirlos con otros puntos más lejanos.

3. Comparar los emparejamientos viables. Cuando hay $4$ puntos a cambiar, hay tres emparejamientos posibles; con $6$ puntos, hay $15$. No es necesario escribir todos si se razona con las distancias más cortas: prueba primero los emparejamientos que usan distancias pequeñas y verifica si existe alguna combinación de mayor ahorro.

4. Aprovechar la simetría. Muchas figuras de examen son simétricas. Si hay un emparejamiento óptimo en un lado, es probable que el simétrico también lo sea. Eso sirve para confirmar, pero no para omitir el cálculo.

5. Recuerda que un camino repetido puede pasar por varios tramos. A veces repetir un solo camino largo entre dos esquinas opuestas puede ser más barato que repetir dos caminos cortos por separado; hay que comparar.

La justificación de por qué basta emparejar los puntos de $S$ es intuitiva: cada repetición de un camino cambia exactamente dos puntos. Para transformar todos los puntos de $S$, cada uno debe ser extremo de al menos una repetición. Si un punto de $S$ participara en tres repeticiones, estaría recibiendo más cambios de los necesarios, y eso rara vez ayuda porque la longitud extra crece. Como las distancias cumplen la desigualdad triangular, unir directamente dos puntos de $S$ nunca es más caro que unirlos pasando por un tercer punto de $S$. Por eso, el costo mínimo se obtiene formando parejas entre los puntos de $S$.

• Si la figura original ya cumple las condiciones de inicio y fin, entonces $L_{\text{repeticiones}}=0$ y la longitud mínima es simplemente la longitud de la figura.
• Repetir dos veces el mismo camino no cambia ninguna paridad, porque cada extremo cambia dos veces y vuelve a su estado original. Además, la longitud extra sería el doble. Por lo tanto, nunca es óptimo repetir dos veces un mismo camino.
• No confundas «número de líneas repetidas» con «número de caminos repetidos». Un camino puede estar formado por varias líneas, y su longitud es la suma de todas ellas.
• La distancia entre dos puntos siempre debe medirse a lo largo de la figura. Si la figura es un rectángulo y los puntos están en esquinas opuestas, puede haber dos rutas: por los bordes o por una diagonal, dependiendo de qué líneas existan. Escoge la menor.
• Aunque el problema pida «longitud mínima que recorre la punta de un lápiz», no es obligatorio reconstruir el orden exacto del trazo. Basta con demostrar que la figura transformada es euleriana bajo las condiciones dadas.