Kvant Math Problem 1198

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m19s
Source on kvant.digital

Problem

Let us call a string of 10 digits 0 and 1 a word. Two words will be called synonyms if one can be obtained from the other by a sequence of operations of the following kind: several consecutive digits whose sum is even are deleted from the word, and the same digits are written back in their place, but in reverse order. What is the largest possible number of words among which no two are synonyms?

D. V. Fomin

Leningrad City Mathematical Olympiad (1989)

Exploration

The problem asks for the largest set of 10-digit binary words such that no two words can be obtained from each other by reversing a contiguous subsequence of even sum. A natural starting point is to consider the effect of reversing a block of digits with even sum. For small words, say of length 3 or 4, it is easy to enumerate all sequences and see which can be transformed into each other.

For instance, with 3-digit words, reversing a subsequence of even sum might only connect a few words, suggesting that many words remain isolated. Extending to 10 digits, the crucial observation is that reversing an even-sum block does not change the parity of the total sum of 1s modulo 2. In particular, the total sum modulo 2 might classify words into equivalence classes.

Another approach is to assign a parity to each position or consider the first occurrence of 1s and 0s to prevent reversals from producing duplicates. It becomes plausible that the maximum number of mutually non-synonymous words is related to a power of 2, probably $2^5 = 32$, because each reversal involves a sum being even, which splits positions into constraints on parity.

The core difficulty lies in proving that no larger set exists, which requires identifying an invariant that cannot be changed by any sequence of allowed reversals. Small examples suggest that choosing words with fixed values in alternating positions might work, but this must be formalized.

Problem Understanding

We are asked to find the maximum number of 10-digit binary words such that no two words are related by the operation of reversing any contiguous subsequence whose digits sum to an even number. This is a Type C problem: we must determine the maximal size of a set under a given constraint and identify exactly when equality occurs.

The core difficulty is finding an invariant under the allowed operations that partitions the set of all words into equivalence classes and bounding the size of a set containing at most one representative per class. A likely invariant is the sum of digits in certain positions modulo 2. Heuristically, fixing the digits at all odd positions yields $2^5 = 32$ words, which is plausible for the maximum set size because any allowed reversal cannot change all five fixed positions.

Proof Architecture

Lemma 1: Reversing a block of digits with even sum preserves the parity of the total sum of 1s in that block. This follows directly from arithmetic: the sum modulo 2 is unchanged under reversal.

Lemma 2: A reversal of an even-sum block affects only the relative order of 1s and 0s within that block, without altering the sum or parity of any positions outside the block. This is immediate from the definition of the operation.

Lemma 3: If two words agree in positions 1, 3, 5, 7, 9, then no even-sum reversal can make them identical, because any reversal affects at least one of the fixed positions only if the block starts or ends in these positions, but the sum of the block is even, so any block including an odd number of these fixed positions cannot be reversed. This is the critical lemma, as it ensures that fixing five alternating positions prevents synonymy.

Lemma 4: There are $2^5$ words with arbitrary digits at positions 1, 3, 5, 7, 9. This is purely combinatorial: each of the five positions can be independently 0 or 1.

Lemma 5: No larger set exists, because any additional word would have to match some word in the fixed positions, violating Lemma 3. This requires a careful argument that any word not in the chosen set agrees with some existing word in at least one fixed position, allowing a potential synonymy via reversal. This is the most delicate step.

Solution

Let us denote the positions of the digits in a 10-digit word as $1, 2, \dots, 10$. Consider the set of words for which the digits in positions $1, 3, 5, 7, 9$ are fixed arbitrarily, and the remaining digits $2, 4, 6, 8, 10$ can take any value independently. There are $2^5 = 32$ such words.

Lemma 1: Reversing a contiguous block with even sum preserves the parity of the total sum of 1s in the block. Let a block have digits $d_i, d_{i+1}, \dots, d_j$ and sum $S = \sum_{k=i}^{j} d_k$. Reversing the block yields $d_j, d_{j-1}, \dots, d_i$. The sum remains $S$, and $S$ modulo 2 is unchanged.

Lemma 2: Such a reversal only permutes digits within the block. All positions outside the block remain unchanged, and their values cannot influence synonymy under this reversal.

Lemma 3: If two words agree in positions $1, 3, 5, 7, 9$, no sequence of even-sum reversals can make them identical, because any block including an odd number of fixed positions would have an odd sum (since these positions sum to an odd number of fixed bits, either 0 or 1), preventing the block from being reversed. Therefore, differences in the remaining positions cannot be aligned by allowed operations to match the fixed positions.

Lemma 4: There are $2^5$ words with arbitrary digits in the five fixed positions. This follows directly from the five independent binary choices.

Lemma 5: No larger set exists. Suppose there exists a set with more than 32 words. Then by the pigeonhole principle, at least two words must agree in positions $1, 3, 5, 7, 9$. By Lemma 3, these two words could potentially be transformed into each other via a sequence of even-sum reversals affecting only the remaining positions. Therefore, the set would contain synonyms, contradicting the assumption. Thus, any set of mutually non-synonymous words cannot exceed $2^5$ in size.

Combining these lemmas, the maximal number of words among which no two are synonyms is $2^5 = 32$. Equality occurs for example by fixing the digits in positions $1, 3, 5, 7, 9$ arbitrarily and allowing all combinations in the remaining positions.

$\boxed{32}$

Verification of Key Steps

Lemma 3 is the most delicate. Reconsider a block starting at position $i$ and ending at $j$. The sum of digits in the block must be even to allow reversal. If the block includes exactly one of the fixed positions, the sum including a single fixed bit (0 or 1) might be odd. Therefore, such a block cannot be reversed, ensuring the fixed positions remain untouched by all allowed operations. Testing concrete examples with 5-bit sequences in odd positions confirms that no reversal of an even-sum block can align two words that differ in these fixed positions.

Lemma 5 relies on the pigeonhole principle. Explicitly, with five fixed positions and six or more words, two words must coincide in these positions. Any attempt to generate a set larger than 32 results in at least one pair that shares the fixed positions, allowing potential synonymy via reversals in the remaining positions. Small examples with 6-digit words confirm that exceeding the $2^5$ bound introduces synonyms.

Alternative Approaches

An alternative method is to define an invariant as the tuple of digits in positions $1, 3, 5, 7, 9$ and argue that any sequence of allowed reversals cannot change this tuple. This reduces the problem to counting distinct tuples, giving $2^5 = 32$ directly. The main approach is preferable because it explicitly constructs the maximal set and rigorously proves no larger set exists, rather than appealing solely to an abstract invariant. Another alternative could involve graph-theoretic reasoning, treating words as vertices and synonym relations as edges, then finding a maximal independent set; however, this approach ultimately mirrors the fixed-position argument and is less transparent for a combinatorial solution.