Muchoscruces¶
Cerca de aquí se va a construir un pueblo nuevo. Va a ser un pueblo un poco especial, ya que va a ser infinito. Estará formado por (infinitos) barrios, cada uno con una forma distinta. Todos ellos tendrán forma de cuadrícula. El equipo de construcción nos ha pedido ayuda para algunos de los cálculos necesarios. ¡Manos a la obra!
Conexiones completas¶
Nos han encargado que contemos cuántas conexiones son necesarias en cada barrio de Muchoscruces. Queremos que cada pareja de casas vecinas estén conectadas.
Barrios cuadrados¶
Algunos barrios de Muchoscruces
¿Cuántas conexiones son necesarias en un barrio de \(n \times n\)?
Contemos primero las conexiones horizontales. En cada fila hay \(n\) casas y \(n-1\) conexiones. Como tenemos \(n\) filas, el total de conexiones horizontales es \(n(n-1)\). Pero el número de conexiones verticales es el mismo, ya que estamos en un cuadrado. Por lo tanto, el número total de conexiones es el doble, es decir, \(\boxed{2n(n-1)}\).
Barrios rectangulares¶
¿Cuántas conexiones son necesarias en un barrio de \(m \times n\)?
Podemos usar la misma estrategia que antes y contar primero las conexiones horizontales. En cada fila hay \(n\) casas y \(n-1\) conexiones. Como tenemos \(m\) filas, el total de conexiones horizontales es \(m(n-1)\). Si cambiamos filas por columnas, vemos que el número de conexiones verticales es \(n(m-1)\). Por lo tanto, el número total de conexiones es \(\boxed{m(n-1)+n(m-1)=2mn-m-n}\).
Conexiones mínimas¶
Hemos podido calcular el número total de conexiones para los infinitos barrios rectangulares de Muchoscruces. Pero el equipo de ingeniería ha pensado que son demasiadas, y que en realidad no hace falta que cada casa esté conectada con todas sus vecinas. Lo único que nos interesa es que estén todas conectadas a una misma red eléctrica. Eso nos permite ahorrar conexiones. Por ejemplo, en el barrio de \(2 \times 2\) ya no son necesarias \(4\) conexiones, nos basta con \(3\). Pero, ¿qué ocurre en el resto de barrios?
¿Cuál es el menor número de conexiones necesarias en un barrio de \(n \times n\)?
Podemos probar a dibujar unos cuantos casos en el barrio de \(3 \times 3\), por ejemplo. Veremos que siempre que logremos una conexión mínima, tendrá \(8\) conexiones.
Secuencias interesantes¶
- Número de árboles para la cuadrícula de \(n \times n\) (A007341, OEIS)
- Número de árboles para la cuadrícula de \(3 \times n\) (A006238, OEIS)
Grafos, árboles y bosques¶
Lo que hemos llamado conexiones mínimas es lo que los matemáticos conocen como árbol. Un árbol es un grafo en el que no hay ciclos. Es decir, entre cualquier pareja de puntos hay un único camino. Un grafo formado por varios árboles se conoce, muy apropiadamente, como bosque.
De grafo a árbol a bosque
El matemático Arthur Cayley utilizó estas ideas para descubrir compuestos químicos. La química orgánica es la química del carbono. Es muy importante porque el carbono se encuentra por todas partes, pero especialmente en los seres vivos, ¡como nosotros! Los alcanos son compuestos de carbono e hidrógeno, como el metano o el butano. Tienen en común que su esqueleto es un árbol, ya que son moléculas sin ciclos. El carbono puede formar hasta \(4\) enlaces y en los alcanos los tiene todos ocupados, o bien con otros átomos de carbono o con átomos de hidrógeno.
¿Cuántos alcanos hay con \(5\) carbonos?
Haciendo una lista podemos encontrar que hay 3 isómeros: pentano, isopentano y neopentano.
¿Cuántos alcanos hay con \(6\) carbonos?
Existen 5 isómeros: hexano, 2-metilpentano, 3-metilpentano, 2,2-dimetilbutano y 2,3-dimetilbutano.
Secuencias interesantes¶
- Número de alcanos con \(n\) carbonos (A000602, OEIS)