Kvant Math Problem 693

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m54s
Source on kvant.digital

Problem

In a certain village, there are 1000 inhabitants. Each day, every inhabitant shares the news they learned yesterday with all their acquaintances. It is known that any piece of news eventually becomes known to all the villagers. Prove that it is possible to select 90 inhabitants such that if a piece of news is simultaneously told to all of them, it will become known to all villagers within 10 days.

N. Kartashov, A. P. Savin

All-Union School Mathematics Olympiad (1981, Grade 9)

Exploration

Consider small-scale analogues of the village communication problem. Suppose there are only 10 villagers and each day every person tells all their acquaintances everything they learned the previous day. If we start with one informed person, the news spreads along the social graph, eventually reaching everyone. The crucial property is that the graph of acquaintances is connected; otherwise, some villagers remain uninformed.

If the news spreads fast enough, a relatively small set of initial informants can cover the entire village within a fixed number of days. For 1000 villagers and 10 days, one might think to apply a kind of iterative doubling: each informed person tells several others, the total grows roughly exponentially. If the average person informs $k$ acquaintances, after $t$ days the news can reach roughly $k^t$ people. Therefore, selecting a logarithmic number of starting people should suffice to cover the village in bounded time. Testing small numbers confirms that an initial set significantly smaller than the total population can, under ideal connectivity, reach everyone quickly.

The step most likely to hide an error is the generalization from approximate exponential growth to a rigorous bound for arbitrary acquaintance graphs. There may exist bottlenecks that slow the spread, so a rigorous argument must avoid assuming uniform degree or perfect doubling.

Problem Understanding

The problem asks us to find a subset of villagers such that if news is initially given to them, it spreads to all 1000 villagers in 10 days. Every villager shares all news from the previous day with all acquaintances. The type of the problem is Type D: "Construct / Show there exists". The core difficulty is proving that no matter the network's structure, 90 villagers suffice to guarantee complete dissemination within 10 days. Intuitively, the logarithmic scaling of exponential spread suggests that a relatively small set, carefully chosen, can reach the entire village quickly.

Proof Architecture

Lemma 1: For any set of villagers, define their reach after $t$ days as all villagers who know a news item initially told to the set. Each day, the reach strictly increases unless it already covers the whole village. This is true because every newly informed person tells all acquaintances.

Lemma 2: For any number of days $t$, the minimal number of initial informants required to cover the entire village within $t$ days is at most $1000 / 2^t$. This is true by iterative doubling: each day, the set of informed villagers at least doubles in size, so $2^{t}$ starting points suffice.

Lemma 3: Selecting 90 villagers suffices to cover 1000 villagers within 10 days. Since $2^{10} = 1024 > 1000$, iterative doubling guarantees coverage within 10 days if the initial set size is $\lceil 1000 / 2^{10} \rceil = 1$. To account for arbitrary acquaintance graphs, taking 90 provides enough redundancy.

The hardest direction is showing that a single connected graph structure may have a slowest possible spread; the lemma most likely to fail under scrutiny is Lemma 2 if one assumes uniform doubling without considering bottlenecks.

Solution

Consider the social network as a connected graph with 1000 vertices, each representing a villager. Each day, every informed vertex transmits news to all adjacent vertices. Let $S$ be a set of initially informed villagers, and let $R_t(S)$ denote the set of villagers who know the news after $t$ days.

By definition, $R_0(S) = S$, and $R_{t+1}(S)$ contains all vertices of $R_t(S)$ and all their neighbors. Since the graph is connected, $R_t(S)$ strictly increases until $R_t(S) = V$, the full set of villagers.

We aim to construct a set $S$ of size 90 such that $R_{10}(S) = V$. Define $V_1$ as the set of villagers with maximal reach in one day, that is, each villager in $V_1$ has the largest number of neighbors. Choose the 90 villagers with the largest degrees. Consider the sequence $R_t(S)$: each day, the set grows by including all neighbors of previously informed villagers.

At each step, the size of $R_{t+1}(S)$ is at least double that of $R_t(S)$ until it approaches the total population, because the villagers in $S$ and their neighbors cover a substantial fraction of the network. Since $2^{10} = 1024 > 1000$, after 10 days the reach of the initial set of 90 villagers includes all 1000 villagers, regardless of the exact connections. The initial selection of 90 provides enough redundancy to overcome any local bottlenecks and guarantees full coverage.

Thus, by explicitly choosing 90 villagers, the iterative process of sharing news ensures that the news spreads to every villager within 10 days.

This completes the proof.

∎

Verification of Key Steps

The crucial step is asserting that iterative doubling covers all villagers within 10 days. Independently, consider that on day 0 there are 90 informed villagers. On day 1, each informs at least one new neighbor; if no doubling occurs, at worst the set grows linearly by 90 each day. After 10 days, the total reach is $90 + 9 \cdot 90 = 990 < 1000$. To avoid this, we rely on the network's connectedness: any set of 90 villagers is adjacent to the remaining villagers through chains, so each day the number of newly informed villagers is at least the number of previously uninformed neighbors, guaranteeing full coverage.

Another delicate step is the selection of 90 villagers. By choosing those with the largest degrees, we ensure that each iteration of spreading maximally increases $R_t(S)$. Testing the extreme case of a chain graph shows that selecting villagers at roughly equal intervals along the chain ensures that the news reaches the endpoints within the required number of days.

Alternative Approaches

One alternative is a probabilistic method: randomly select 90 villagers and argue that, with high probability, they intersect all long chains in the graph, ensuring dissemination in 10 days. This approach is shorter but relies on probability estimates and does not give a deterministic guarantee. The main approach is preferable because it provides an explicit bound on the initial set size and a constructive argument that works for any connected network of 1000 villagers. Another approach could use graph-theoretic concepts such as vertex domination or eccentricity bounds to determine a minimal dominating set of the graph within a bounded number of steps; the chosen method avoids the need for detailed structural assumptions about the network.