Suppose that each of the 5 persons knows a piece of information, each piece is different, about a certain event. Each time person $A$ calls person $B$, $A$ gives $B$ all the information that $A$ knows at that moment about the event, while $B$ does not say to $A$ anything that he knew. (a) What is the minimum number of calls are necessary so that everyone knows about the event? (b) How many calls are necessary if there were $n$ persons?
Problem
Source: CentroAmerican & Caribbean MO 1999 Q1
Tags: geometry, geometric transformation, combinatorics proposed, combinatorics
25.01.2007 00:15
The answer is $2n-2$. It's clear that this is sufficient: one method is to choose a fixed individual, $A$, and have everyone else call $A$ ($n-1$ calls) and then have $A$ call everyone else ($n-1$ calls). Now, why we cannot do better: let us note the last time that a piece of information, $a$, is shared for the first time. This must be no earlier than the $n$th call, because $n-1$ pieces of information must have been shared, and each required a call from the person who held that piece of information. After our noted call, $a$ is known by 2 people. But in the end it must be known to $n$ people. So we need at least $n-2$ more calls. Thus, in total $2n-2$.
25.01.2007 00:26
This problem was on an old Canadian MO.
25.01.2007 00:48
The Centroamerican Olympiad was our first experience of this kind in Central America Indeed, this question belongs to the first Olympiad paper, which was celebrated in Costa Rica. But nowadays the variety and difficulty of the problems is increasing, and the competition is getting harder I see you're interested in papers of the Centroamerican Olympiad. I have tried to upload some, but unfortunately, they don't even appear in the "Resources" section of the forum I'll try to post some problems from the last year's contest
25.01.2007 02:03
Jutaro wrote: The Centroamerican Olympiad was our first experience of this kind in Central America Indeed, this question belongs to the first Olympiad paper, which was celebrated in Costa Rica. But nowadays the variety and difficulty of the problems is increasing, and the competition is getting harder I see you're interested in papers of the Centroamerican Olympiad. I have tried to upload some, but unfortunately, they don't even appear in the "Resources" section of the forum I'll try to post some problems from the last year's contest That would be nice because the "Resources" section needs an 'update' . I did some of the translations with the help of my mentor but he did most of the work . I'll try to put up more of the older tests and hopefully have a complete set of problems from CCMO available to everyone to enjoy
14.10.2020 21:12
We will prove by induction that the least amount of calls necessary for any $n$ is $2n - 2$. This can be achieved by having $n-1$ people call the remaining person, so that they know all the information, and then have said person call everyone back to tell each one everything. This would take $2(n-1) = 2n - 2$ calls. We treat $n=2$ as the trivial case. Indeed, we need $2$ calls, where one person calls the other and then vice versa, so that everyone holds all the information, and obviously 1 or 0 calls are not enough. We note that $2 = 2*2 - 2$. Now we will assume as our hypothesis of induction, that $n$ people need to perform at least $2n - 2$ calls so they all know each other's information. It is clear that $n+1$ people will need more than $2n - 2$ calls so that everyone is informed, since they will need to accomodate for one more person in the algorithm. This person needs to, at the very least, call one person to share their information, and be called by one person to learn the others' information. This brings our number of total calls to $2n = 2*(n+1) - 2$.