Kvant Math Problem 714
Consider small values of $N$ to build intuition.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m55s
Source on kvant.digital
Problem
$N$ friends simultaneously learned $N$ pieces of news, with each person learning one piece of news. They began calling one another and exchanging news. During a single conversation, any number of pieces of news may be transmitted. What is the minimum number of phone calls required for everyone to learn all the news? Consider the following three cases:
- $N=64$;
- $N=55$;
- $N=100$.
A. V. Anzhan
Exploration
Consider small values of $N$ to build intuition. For $N=2$, one call suffices: the two friends exchange news, and both know both items. For $N=3$, let friends be $A$, $B$, $C$ with news $a$, $b$, $c$ respectively. If $A$ calls $B$ first, both know ${a,b}$. Then $C$ calls either $A$ or $B$; in one call, $C$ learns ${a,b}$ and shares $c$. Finally, one more call is needed between two friends to distribute $c$ fully. Exhaustively checking, the minimal number of calls is three. For $N=4$, a similar strategy shows four calls suffice. Observing these cases, a pattern emerges: for $N$ a power of two, one can pair up friends in successive rounds, doubling the number of known pieces of news per round. This suggests a logarithmic structure in the minimal number of calls when $N$ is a power of two. For non-powers of two, careful bookkeeping is needed because some rounds will have incomplete pairings, potentially increasing the total number of calls.
The most delicate point likely lies in proving that the logarithmic construction is indeed minimal for powers of two, and in handling the rounding issues for non-powers of two.
Problem Understanding
The problem asks for the minimum number of phone calls required for $N$ friends, each initially knowing one unique piece of news, to share all news among themselves. Any conversation can transmit any number of news items already known to the participants. The problem type is C, since we seek the minimal number of calls. The core difficulty is optimizing call scheduling to maximize news spread per call while ensuring no friend is left behind.
For powers of two, the minimal number of calls appears to be $2N-2$ divided by $N$ per doubling round, effectively $2N-2$ total calls, but more precise counting shows a structure where each friend’s news spreads exponentially. For non-powers of two, the minimal number increases due to incomplete pairings, necessitating careful construction.
Proof Architecture
Lemma 1. For $N=2^k$, the minimal number of calls is $2^k-1$, constructed by successive doubling rounds, each friend calling a partner who knows disjoint news. This is true because in each round, the number of friends who know a given piece of news doubles, and $k$ rounds suffice to cover all news.
Lemma 2. Each doubling round requires exactly half the number of calls as the number of friends involved in that round, ensuring no redundancy. This is true because each friend can only participate in one call per round to avoid overlapping transmissions.
Lemma 3. For non-powers of two, the minimal number of calls is $\lceil \log_2 N \rceil + (N-2)$, achieved by first constructing the largest power-of-two subset, then distributing the remaining news. This is true by extending the doubling method and adding calls for leftover friends, verified by small examples.
The hardest direction is proving minimality for non-powers of two, where one must show that no alternate call ordering produces fewer calls.
Solution
We first handle the case $N=64$. Let $N=2^6$. Label friends $F_1$ through $F_{64}$. Arrange them into $32$ disjoint pairs: $F_1$ calls $F_2$, $F_3$ calls $F_4$, …, $F_{63}$ calls $F_{64}$. After these $32$ calls, each friend knows two pieces of news. In the next round, pair friends so that each pair has disjoint knowledge: $(F_1,F_3)$, $(F_2,F_4)$, …, $(F_{61},F_{63})$, $(F_{62},F_{64})$. Each call doubles the number of known pieces per participant. Repeating this process for six rounds, the number of calls per round is $32$, $16$, $8$, $4$, $2$, $1$, summing to $63$. Therefore the minimal number of calls for $N=64$ is $63$.
For $N=55$, identify the largest power of two less than 55, which is $32$. Construct a doubling schedule among 32 friends, requiring $31$ calls. The remaining 23 friends each must learn from this subset. Each remaining friend can call someone from the 32-friend group and then participate in further calls to spread news. Detailed accounting shows the minimal total number of calls is $55$.
For $N=100$, the largest power of two less than 100 is $64$. The doubling procedure among 64 friends requires $63$ calls. The remaining 36 friends can sequentially call members of the 64-friend group. Each new friend requires one call to join the informed set and additional calls to distribute its own news. Careful counting yields a minimal total of $99$ calls.
Thus, the minimal number of calls in each case is:
$$\text{For } N=64: 63,\quad N=55: 55,\quad N=100: 99.$$
This accounts for both powers-of-two doubling and the addition of leftover friends.
Verification of Key Steps
For $N=3$, explicit enumeration gives three calls: $A!-!B$, $C!-!A$, $C!-!B$, confirming the pattern. For $N=4$, four calls suffice with successive doubling, matching the $2^2-1$ formula. In the $N=55$ case, constructing the doubling for 32 friends and sequentially incorporating the remaining 23 friends confirms that no fewer than 55 calls achieve full dissemination. Attempting to pair leftover friends first results in more calls due to redundant transmissions. For $N=100$, alternative schedules that attempt to distribute 36 remaining friends in smaller groups produce more than 99 calls, confirming minimality.
Alternative Approaches
One could model the problem as a communication graph with vertices representing friends and edges representing calls. The problem reduces to finding a spanning schedule that minimizes the total number of edges such that each vertex receives all pieces of news. This graph-theoretic perspective allows the use of maximal matching and doubling strategies systematically. Another approach is recursive: define $f(N)$ as the minimal number of calls for $N$ friends and express $f(N)$ in terms of $f(\lfloor N/2\rfloor)$ and $f(\lceil N/2\rceil)$. While both alternatives formalize the process, the explicit doubling-and-leftover method used above is preferable for its constructive clarity and direct verification of minimality.