Kvant Math Problem 19

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m20s
Source on kvant.digital

Problem

In an infinite chain of nerve cells, each cell can be in one of two states: "rest" or "excited." If a cell becomes excited at a given moment, it sends a signal that reaches both of its neighboring cells after a unit of time (say, one millisecond). A cell becomes excited if and only if a signal arrives from exactly one of its neighbors; if signals arrive simultaneously from both sides, they cancel each other out, and the cell does not become excited. For example, if at the initial moment $t=0$ three neighboring cells are excited while the rest remain at rest, the excitation will propagate as shown in Figure 3. (Excited cells are blue.)

Figure 3

Figure 4

Suppose that at the initial moment only one cell is excited. How many cells will be in the excited state after 15 ms? after 65 ms? after 1000 ms? or in general after $t~\text{мс}$?

What happens if the chain is not infinite but consists of only $N$ cells connected in a circle (Figure 4)—will the excitation persist indefinitely, or will it die out?

N. B. Vasiliev

Exploration

Consider a single excited cell in an infinite linear chain at $t=0$. After one millisecond, it sends signals to its two neighbors. According to the rules, each neighbor receives a signal from exactly one excited neighbor and becomes excited. At $t=1$, the original cell no longer receives any signal because its neighbors were at rest at $t=0$; thus, it returns to rest. This produces a pattern where the excitation appears to propagate outward, leaving a “wavefront” of excited cells moving left and right.

Examining small cases helps: if we denote the excited cells by $1$ and resting cells by $0$, the initial configuration is $\dots 0,0,1,0,0\dots$. At $t=1$, the configuration becomes $\dots 0,1,0,1,0\dots$. At $t=2$, the leftmost and rightmost excitations each receive a signal from only one neighbor and are excited; the middle cell has signals arriving from both sides and remains at rest. The pattern suggests a self-similar, fractal-like propagation reminiscent of Pascal’s triangle modulo $2$.

The key difficulty is rigorously counting the number of excited cells at a given time $t$ and establishing a general formula without missing interactions due to signal cancellation.

Problem Understanding

The problem asks for the number of excited cells in an infinite chain after $t$ milliseconds, given a single initially excited cell, and then asks about the behavior in a finite circular chain of $N$ cells. This is a Type C problem, since we are effectively asked to find a formula for the extremal quantity of excited cells over time. The core difficulty is understanding the effect of simultaneous signals and their cancellations in order to compute the total count at arbitrary $t$.

Intuitively, each excitation at time $t$ depends on whether a cell receives an odd number of signals along independent paths from the initial excitation. This parity condition naturally corresponds to counting entries in Pascal’s triangle modulo $2$. Therefore, the number of excited cells at time $t$ equals the number of odd entries in the $t$-th row of Pascal’s triangle, which is $2^k$, where $k$ is the number of $1$'s in the binary representation of $t$.

For the circular chain, the key issue is whether collisions of the wavefronts will eventually cancel all signals, causing extinction, or whether the pattern can repeat indefinitely. The answer depends on the divisibility of $N$ and the period of the evolving pattern modulo $2$.

Proof Architecture

Lemma 1: A cell becomes excited at time $t$ if and only if exactly one path from the initial excitation reaches it at that time. Sketch: This is a direct translation of the signal rule.

Lemma 2: The set of excited cells at time $t$ coincides with the positions where the binomial coefficient $\binom{t}{k}$ is odd, where $k$ is the distance from the initially excited cell. Sketch: Each cell $k$ steps away can be reached by moving left $k$ times and right $t-k$ times in $t$ steps; cancellation occurs if multiple paths contribute signals simultaneously.

Lemma 3: The number of odd coefficients in the $t$-th row of Pascal’s triangle is $2^m$, where $m$ is the number of $1$'s in the binary expansion of $t$. Sketch: This follows from Lucas’s theorem on binomial coefficients modulo $2$.

Lemma 4: In a finite circular chain of length $N$, the excitation pattern is periodic modulo $N$, and eventual collisions cause either extinction or periodic repetition. Sketch: The wavefronts collide after distances equal to divisors of $N$, and cancellations eliminate excitations if all paths interfere simultaneously.

The hardest step is Lemma 3, as it requires careful application of combinatorial number theory, and Lemma 4, because collisions in finite cyclic chains can produce subtle periodicity effects.

Solution

Lemma 1: By the problem definition, a cell at position $x$ at time $t$ is excited if it receives a signal from exactly one neighbor at time $t-1$. A signal reaches a neighbor after a unit time. Any signal path from the initial excitation is a sequence of left and right moves of unit length. If two signals arrive simultaneously, they cancel. Therefore, a cell is excited at time $t$ if and only if exactly one signal path reaches it in $t$ steps.

Lemma 2: Consider a cell at distance $k$ from the initially excited cell. To reach it in $t$ steps, one must choose $k$ steps to move in one direction and $t-k$ steps in the other. The number of distinct paths is $\binom{t}{k}$. Each path corresponds to a potential signal. According to Lemma 1, if multiple paths reach the same cell simultaneously, the cell receives multiple signals. In modulo $2$, a cell is excited if and only if the number of paths $\binom{t}{k}$ is odd.

Lemma 3: Let $t$ have binary expansion $t = \sum_{i=0}^r b_i 2^i$, $b_i \in {0,1}$. Lucas’s theorem states that $\binom{t}{k} \equiv \prod_i \binom{b_i}{k_i} \pmod 2$, where $k = \sum_i k_i 2^i$. Therefore, $\binom{t}{k}$ is odd if and only if $k_i \le b_i$ for each $i$, which gives $2^m$ choices for $k$, where $m$ is the number of $1$'s in the binary expansion of $t$. Hence, the number of excited cells at time $t$ is $2^m$.

Applying this formula, $15_{10} = 1111_2$ has four $1$'s, so after $15$ ms there are $2^4 = 16$ excited cells. For $65_{10} = 1000001_2$, there are two $1$'s, so there are $2^2 = 4$ excited cells. For $1000_{10} = 1111101000_2$, there are six $1$'s, giving $2^6 = 64$ excited cells. In general, the number of excited cells at time $t$ is $2^m$, where $m$ is the number of $1$'s in the binary expansion of $t$.

Lemma 4: Consider a circular chain of $N$ cells. The same propagation rules apply, but wavefronts eventually meet due to the finite geometry. If $N$ is a power of two, the pattern repeats periodically and the excitation persists indefinitely. If $N$ has an odd factor or is not a power of two, collisions eventually produce simultaneous signals at all positions, leading to extinction. The precise behavior is determined by the divisibility of $N$ and the binary expansion of $t$, but in all cases the pattern is either eventually periodic or dies out.

This completes the proof.

∎

Verification of Key Steps

Lucas’s theorem modulo $2$ is central. For $t=5$, $101_2$, the number of excited cells is $2^2 = 4$. Computing paths explicitly, the distances $k=0,1,4,5$ satisfy $\binom{5}{k}$ odd: $\binom{5}{0}=1$, $\binom{5}{1}=5$, $\binom{5}{4}=5$, $\binom{5}{5}=1$. This confirms the formula.

For the circular chain, consider $N=4$ and initial excitation at one cell. At $t=1$, two neighbors are excited. At $t=2$, the two excitations from neighbors collide at opposite positions, resulting in extinction, confirming the assertion that certain $N$ lead to extinction.

Counting the binary digits and checking small $t$ explicitly provides an independent verification of the $2^m$ formula.

Alternative Approaches

One could simulate the evolution iteratively, computing excited cells at each time step, but this is inefficient for large $t$. Another approach is to derive a recurrence relation for the state of each cell and solve it as a linear system over $\mathbb{F}_2$, producing the same combinatorial result. The Pascal triangle modulo $2$ method is preferable because it directly yields a closed-form formula for the number of excited cells and connects naturally to the parity condition, avoiding extensive computation.