La solución a sus problemas (1): La red social

¡Tenemos ganador! Alberto Castaño, famoso divulgador con múltiples apariciones en los medios, después de estrujarse los sesos una sobremesa completa, y con la colaboración inestimable de Marta Aguilera, ha dado con una solución al problema. Un poquillo enrevesada, eso sí, pero correcta. La solución ganadora puede encontrarse en este fichero PDF. Pero si siguen leyendo, encontrarán una respuesta más sencilla, al más puro estilo de Warren Sánchez.

Recordemos el enunciado:

En un pueblo con \(12 k\) habitantes, cada uno conoce a \(3k+6\) convecinos y el conocimiento es mutuo. Existe un entero positivo \(n\) tal que, para cada pareja de habitantes, el número de personas que conocen a ambos es \(n\). ¿Cuántos habitantes hay en el pueblo?

Para resolver el problema, vamos a contar los habitantes del pueblo de dos maneras diferentes.

Por un lado, sabemos que hay \(12k\) vecinos. Por otro, habrá \({12k \choose 2} = 6k(12k-1)\) parejas, y cada una de ellas es conocida por \(n\) personas. Si contamos estas \(n\) personas \(6k(12k-1)\) veces, habremos contado a todo el pueblo, pero cada persona habrá sido contada varias veces. En concreto, cada vecino conoce a \({3k+6 \choose 2} = \frac{1}{2}(3k+6)(3k+5)\) parejas, luego habrá sido contado \(\frac{1}{2}(3k+6)(3k+5)\) veces.

Por tanto, el número de personas del pueblo es

\(\displaystyle\frac{6k(12k-1)n}{\frac{1}{2}(3k+6)(3k+5)} = \frac{12k(12k-1)n}{(3k+6)(3k+5)}\)

Como este número es igual a \(12 k\), obtenemos finalmente \((12k-1)n = (3k+6)(3k+5)\).

Ahora sólo queda saber qué números enteros pueden cumplir esta ecuación. Observemos que todo divisor común de \(12k-1\) y \(3k+6\), será también divisor de \(4(3k+6)-(12k-1)\), es decir, será divisor de 25. Igualmente, todo divisor común de \(12k-1\) y \(3k+5\) será también divisor de \(4(3k+5)-(12k-1)\), es decir, será divisor de 21. Por tanto, \(12k-1\) es obligatoriamente un divisor de \(25\times 21 = 525\).

Como el único divisor de 525 que se puede escribir de la forma \(12k-1\) es 35, debemos tener \(12k-1=35\), y por tanto el número de habitantes del pueblo es \(12k =36\). ¡Una aldeíta, vamos!

Hay quien se quedaría a gusto con esta solución (como nuestro flamante ganador). Pero quizás se debería cuestionar si de verdad puede existir un pueblo con 36 habitantes donde cada uno conozca a 15 vecinos, y cada pareja sea conocida exactamente por 6 personas. Los tiquismiquis que se lo hayan preguntado pueden ver el grafo de la figura, donde cada vértice representa a un vecino, y cada arista une a dos vecinos que se conocen. ¡Lo que me ha costado dibujarlo, oiga!

¿Que no se ve nada? Pues otra posible forma de verlo consiste en disponer a los 36 habitantes formando un cuadrado \(6\times 6\), desde la posición \((1,1)\) a la posición \((6,6)\), y considerar que el habitante \((i,j)\) conoce a todos los de su fila, a todos los de su columna, y a todos los de su diagonal (esto último quiere decir a todos los \((p,q)\) tales que \(i-j=p-q\) módulo 6).

Esperamos que les haya gustado. Se admiten peticiones para el próximo. ¿Cómo dicen? ¿Más fácil? Bueno, ya veremos…