Hay n estudiantes en una clase, cada uno en posesión de una historia divertida diferente. Como los estudiantes se estaban aburriendo en la clase, decidieron inventar un juego para pasar el tiempo. Quieren compartir las historias divertidas entre ellos mediante el envío de mensajes electrónicos. Suponga que un remitente incluye todas las historias divertidas que conoce en el momento en que se envía el mensaje y que un mensaje puede tener solo un destinatario. ¿Cuál es la cantidad mínima de mensajes que deben enviar para garantizar que todos reciban todas las historias divertidas?
Solución: el número mínimo de mensajes es igual a 2n – 2. Hay varias formas de hacerlo.
Método 1: Los estudiantes pueden designar a un estudiante, digamos, el estudiante 1, a quien todos los demás envían el mensaje con la historia divertida que conocen. Después de recibir todos estos mensajes, el estudiante 1 combina todas las historias divertidas con su historia divertida y envía este mensaje combinado a cada uno de los otros n – 1 estudiantes. Se puede entender por la siguiente figura. Representar a los n estudiantes como S1, S2, S3, ………….., Sn. Los estudiantes designan a S1 a quien todos los demás estudiantes envían el mensaje con la historia divertida que conocen.
Después de recibir todos estos mensajes, el estudiante 1 combina todas las historias divertidas con su historia divertida y envía este mensaje combinado a cada uno de los otros n – 1 estudiantes. Por lo tanto, el número mínimo de mensajes es igual a 2n – 2.
Método 2 (Algoritmo Greedy): Numere a los estudiantes del 1 al n como S1, S2, S3, ……………, Sn y envíe los primeros n – 1 mensajes de la siguiente manera: de S1 a S2, de S2 a S3, y así sucesivamente, hasta que el mensaje combine las anécdotas inicialmente conocidas por los alumnos S1, S2, . . . , Sn – 1 se envía a la persona n. Luego envíe el mensaje combinando todas las n historias divertidas del estudiante n, es decir, Sn, a los estudiantes S1, S2, . . . , Sn-1.
Por lo tanto, el número mínimo de mensajes es igual a 2n – 2.
Nota: El hecho de que 2n – 2 mensajes sea el número más pequeño necesario para resolver el acertijo se deriva del hecho de que un aumento del número de estudiantes en uno requiere al menos dos mensajes adicionales, es decir, hacia y desde el estudiante adicional, exactamente lo que proporcionan los métodos anteriores.
Referencia: Rompecabezas algorítmicos – Anany Levitin, Maria Levitin
Publicación traducida automáticamente
Artículo escrito por Sahil_Bansall y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA