Este problema que propones es un hibrido de combinatoria y topología.
En primer lugar cuando dices "cada persona conoce a otras 15", ¿Hay que interpretarlo como que conoce a 15, o que puede llegar a conocer hasta un máximo de 15? o sea:
- 15 personas
- Un número de personas dentro de este rango [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
?
De momento he supuesto que todas tienen que conocer a 15 y solo a 15.
Esta cuestión es importante, ya que determinara que topologías de redes son validas.
Vamos a crear alguna topología que cumpla con el requerimiento anterior:
Colocamos los 2000000 de elementos equidistantes sobre una circunferencia,
Además:
\( 2000000=2^7 5^6 \)
Por tanto es divisible por estos números: 1,2,4,5,8,16,25,32,64,125,128
Lo interesante es que por cada número que sea divisible, se puede crear un polígono regular.
El número de lados del polígono en función del divisor será:
NumeroLados=2000000/Divisor
Y a su vez, por cada polígono regular que se agregue, cada nodo de la red tendrá dos conexiones más.
Por tanto para conseguir las 15 conexiones por nodo, se han de agregar 7 polígonos regulares mas una estrella.
La estrella esta formada por rectas que pasan por el centro de la circunferencia y unen nodos opuestos, se crea
una sola conexión en cada nodo, al contrario que en el polígono que crea dos conexiones en cada nodo.
A continuación pongo un ejemplo gráfico con 20 elementos y 6 conexiones por nodo (20 personas y 6 conocidos)
No tomar en cuenta la recta vertical central.
Podemos crear mas topologías usando el resto de los divisores siempre que el número de lados sea \( \geq{3} \), o sea:
Para la topología descrita, se usaron los divisores: 1,2,4,5,8,16,25
Otras topologías se obtendrían usando estos divisores:
2,4,5,8,16,25,32
4,5,8,16,25,32,64
5,8,16,25,32,64,125
8,16,25,32,64,125,128
Pero lo realmente importante, es que cada topología determinara para cada pareja posible de elementos, el número de nodos
intermedios necesarios para llegar del nodo inicial al final (y viceversa)
Por tanto para resolver el problema, necesitamos conocer todas las posibles topologías, y estudiar el número de nodos intermedios para cada pareja.
Entonces se sumarian todos los resultados de 2 intermediarios, y se dividirían entre el numero total de casos, esto nos daría
la probabilidad pedida.
El número de parejas en 2000000 es: \( \displaystyle\binom{2000000}{2} \) = 2*10^12
Ese número de casos se deberían evaluar para cada topología.
Por otra parte hay que desarrollar un método para calcular todas las topologías posibles!!!!!!!
Me temo que es posible que deba pasar mucho tiempo, para poder ver la solución a este problema!!!
Pero mientras tanto, se puede intentar abordar casos más asequibles, como el de 8 personas que conocen a 2 y solo 2
A continuación pongo una imagen con varias topologías posibles (no tomar en cuenta la figura 3):
Estas son solo a modo de ejemplo (unas pocas), como ya comente, hay que ver cuantas topologías existen en total, y evaluarlas todas.
En este caso el número de parejas por cada caso es de \( \displaystyle\binom{8}{2} \) =28, lo cual si el número de posibles topologías no se dispara, es asequible para ser evaluado.
A darle al coco!!!!!!!!!
