Olimpiadas de Matemáticas
Página de preparación y problemas
Competiciones
| OME Local |
| OME Andaluza |
| OME Nacional |
| OIM |
| IMO |
| EGMO |
| USAMO |
| ASU |
| OMCC |
| Retos UJA |
Buscar problemas
La base de datos contiene 2434 problemas y 940 soluciones.
Problema 1364
OMCC, 1999-P1
Se supone que cinco personas conocen, cada una, informaciones parciales diferentes sobre cierto asunto. Cada vez que la persona $A$ telefonea a la persona $B$, $A$ le da a $B$ toda la información que conoce en ese momento sobre el asunto, mientras que $B$ no le revela lo que él conoce. ¿Cuál
es el mínimo número de llamadas necesarias para que todos lo sepan todo sobre el asunto? ¿Cuántas llamadas serían necesarias si se tratara de $n$ personas?
pistasolución 1info
Pista. ¿Cuántas llamadas son necesarias como mínimo para que una persona tenga toda la información? ¿Cuántas llamadas son necesarias como mínimo para que todas tengan la información una vez que una la tiene?
Solución. Vamos a razonar directamente para $n$ personas $P_1,\ldots,P_n$. Está claro que se puede conseguir que todos tengan toda la información con $2(n-1)$ llamadas ya que $P_1,\ldots,P_{n-1}$ pueden llamar a $P_n$ para contarle lo que saben y luego $P_n$ llamar a $P_1,\ldots,P_{n-1}$ para devolverles la información completa.
Para probar que el mínimo es efectivamente $2(n-1)$, pensemos que después de las $n-2$ primeras llamadas nadie puede tener la información completa ya que hay alguien que no ha llamado aún y, por tanto, su información no ha sido compartida. Por otro lado, observamos que no hay dos personas que obtengan la información completa en una misma llamada ya que la transferencia de información es unidireccional. Por tanto, tenemos necesariamente al menos $n$ llamadas adicionales, en cada una de las cuales una persona distinta completa toda la información. Esto hace un mínimo de $(n-2)+n=2(n-1)$ llamadas.
En el caso $n=5$, el número de mínimo de llamadas es $8$.
Si crees que el enunciado contiene un error o imprecisión o bien crees que la información sobre la procedencia del problema es incorrecta, puedes notificarlo usando los siguientes botones:
Informar de error en enunciado Informar de procedencia del problema
Informar de error en enunciado Informar de procedencia del problema
José Miguel Manzano © 2010-2025. Esta página ha sido creada mediante software libre