Competition problem — Combinatorics

Library / /39 of 41

Combinatorics Difficulty 6.8 National olympiad Prove it Romania

The people of an ancient tribe used a language in which the words were formed with two letters only: $A$ and $B$ . Researchers discovered that any two words of equal length differ in at least three positions. For instance, the words $ABBAA$ and $AAAAB$ differ in positions $2$ , $3$ and $5$ , that is, in three positions.

Let $n \in \mathbb{N}$ , $n \ge 3$ . Prove that this language cannot contain more than $\left\lfloor \frac{2^n}{n+1} \right\rfloor$ words of length $n$ .

Solution

If we denote by $C$ the set of all possible words of length $n$ (not necessarily from the language), we have $\text{Card}(C) = 2^n$ . If $x$ and $y$ are arbitrary words from $C$ , let $d(x, y)$ be the number of positions at which the corresponding letters are different (the Hamming distance). Obviously, $d(x, x) = 0$ and $d(x, y) = d(y, x)$ . For each $x \in C$ , we define the set $C_x = \{y \in C \mid d(x, y) \le 1\}$ . It is not difficult to see that $\text{Card}(C_x) = n + 1$ .

If $a, b$ are words of length $n$ from the given language, then $d(a, b) \ge 3$ , hence $C_a \cap C_b = \emptyset$ .

Let $D$ be the set of all words of length $n$ from the language. Then $\bigcup_{a \in D} C_a \subset C$ , which implies $\text{Card}\left(\bigcup_{a \in D} C_a\right) \le \text{Card}(C)$ . But $\text{Card}\left(\bigcup_{a \in D} C_a\right) = (n+1) \cdot \text{Card}(D)$ , so that $(n + 1) \cdot \text{Card}(D) \le 2^n$ , therefore $\text{Card}(D) \le \frac{2^n}{n+1}$ , and the conclusion follows.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.