Kvant Math Problem 47

Represent the five numbers as five binary strings of length $n$, where the symbols are $1$ and $2$.

kvantmathematicsolympiad

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

Problem

Using the digits 1 and 2, five $n$-digit numbers were formed such that any two numbers have the same digit in exactly $m$ positions, but in no position do all five numbers have the same digit. Prove that $$\frac{2}{5}\le \frac{m}{n}\le \frac{3}{5}.$$.

All-Union Mathematical Olympiad (1970, grades 9–10)

Exploration

Represent the five numbers as five binary strings of length $n$, where the symbols are $1$ and $2$. For each position, let $k$ be the number of strings having digit $1$ there. Since there are five strings, $k\in{0,1,2,3,4,5}$.

The condition that no position has all five digits equal excludes $k=0$ and $k=5$. Thus every position has type $k=1,2,3,$ or $4$.

At a position of type $k$, two strings agree there precisely when both belong to the group of size $k$ or both belong to the complementary group of size $5-k$. Hence the number of agreeing pairs of strings at such a position is

$$\binom{k}{2}+\binom{5-k}{2}.$$

Computing:

$$k=1,4:\quad \binom{1}{2}+\binom{4}{2}=6,$$

$$k=2,3:\quad \binom{2}{2}+\binom{3}{2}=4.$$

There are $\binom52=10$ pairs of strings. Since every pair agrees in exactly $m$ positions, the total number of pair-position agreements equals $10m$.

This suggests counting agreements in two ways. Let $a$ be the number of positions of types $1$ or $4$, and $b$ the number of positions of types $2$ or $3$. Then

$$a+b=n,$$

and double counting gives

$$6a+4b=10m.$$

Solving,

$$5m=3a+2b.$$

Since $0\le a,b\le n$, one obtains

$$2n\le 3a+2b\le 3n,$$

which immediately yields

$$\frac25\le \frac mn\le \frac35.$$

The only potentially dangerous step is the double count of agreements. It must be checked carefully that every agreement of a pair in a position is counted exactly once.

Problem Understanding

We have five $n$-digit numbers formed only from the digits $1$ and $2$. Any two of the five numbers coincide in exactly $m$ digit positions. At no position are all five digits equal.

We must prove that the ratio $m/n$ always satisfies

$$\frac25\le \frac mn\le \frac35.$$

This is a Type B problem, a pure proof.

The core difficulty is translating the condition on pairwise coincidences into a global counting statement. The natural object to count is the total number of agreements between pairs of numbers across all positions.

Proof Architecture

Let $a$ denote the number of positions in which one digit occurs once and the other four times, and let $b$ denote the number of positions in which the digits occur in a $2$-$3$ split; then $a+b=n$ because the condition excluding identical digits in all five numbers leaves only these two possibilities.

For a position of type $1$-$4$, exactly $6$ pairs of numbers agree there, because the four equal digits contribute $\binom42=6$ agreeing pairs.

For a position of type $2$-$3$, exactly $4$ pairs of numbers agree there, because the equal digits contribute $\binom22+\binom32=4$ agreeing pairs.

Counting pair-position agreements in two ways yields $6a+4b=10m$, since there are $\binom52=10$ pairs and each pair agrees in exactly $m$ positions.

From $6a+4b=10m$ and $a+b=n$, derive $5m=3a+2b$.

Since $0\le a,b\le n$, obtain $2n\le 3a+2b\le 3n$, which gives the desired bounds.

The hardest step is the double counting identity $6a+4b=10m$.

Solution

Consider the five numbers as five strings of length $n$ over the alphabet ${1,2}$.

At a fixed position, let $k$ be the number of strings having digit $1$. Since all five digits are not equal at any position, neither $k=0$ nor $k=5$ can occur. Thus $k$ is one of $1,2,3,4$.

Let $a$ be the number of positions with $k=1$ or $k=4$, and let $b$ be the number of positions with $k=2$ or $k=3$. Every position belongs to exactly one of these classes, so

$$a+b=n.$$

We count, for each position, how many pairs of numbers have equal digits in that position.

First suppose the position is of type $1$-$4$, that is, $k=1$ or $k=4$. Then one digit appears once and the other appears four times. Two numbers agree exactly when both belong to the group of four equal digits. Hence the number of agreeing pairs is

$$\binom42=6.$$

Next suppose the position is of type $2$-$3$. Then the numbers split into groups of sizes $2$ and $3$. A pair agrees precisely when both numbers belong to the same group. Hence the number of agreeing pairs is

$$\binom22+\binom32=1+3=4.$$

Therefore the total number of pair-position agreements, counted position by position, equals

$$6a+4b.$$

Now count the same quantity in a different way. There are

$$\binom52=10$$

pairs of numbers. By hypothesis, every pair agrees in exactly $m$ positions. Hence the total number of pair-position agreements equals

$$10m.$$

Equating the two counts gives

$$6a+4b=10m.$$

Dividing by $2$,

$$3a+2b=5m.$$

Using $a+b=n$,

$$3a+2b=2(a+b)+a=2n+a.$$

Since $0\le a\le n$,

$$2n\le 2n+a\le 3n.$$

Thus

$$2n\le 5m\le 3n.$$

Dividing by $5n$ yields

$$\frac25\le \frac mn\le \frac35.$$

This completes the proof.

∎

Verification of Key Steps

The first delicate point is the computation of agreeing pairs at a position.

For a $1$-$4$ split, the lone digit cannot form an agreeing pair with any other number. The four equal digits produce exactly

$$\binom42=6$$

agreeing pairs.

For a $2$-$3$ split, agreements occur only inside the two groups. The count is

$$\binom22+\binom32=1+3=4.$$

No pair belonging to different groups agrees, because the two groups carry different digits.

The second delicate point is the double counting. The quantity being counted is the set of all triples

$$(\text{pair of numbers},\ \text{position})$$

for which the two numbers have the same digit at that position.

Counting by positions gives $6a+4b$. Counting by pairs gives $10m$. Every such triple contributes exactly once to each count, so the identity

$$6a+4b=10m$$

is exact.

The final step uses

$$5m=3a+2b=2(a+b)+a=2n+a.$$

A careless argument might replace $a$ by an arbitrary quantity without using $0\le a\le n$. The bounds follow precisely because every position contributes either to $a$ or to $b$, giving $0\le a\le n$.

Alternative Approaches

Let $x_j$ be the number of positions of type $j$-$!(5-j)$ for $j=1,2$. Then

$$x_1+x_2=n.$$

The average number of agreements per pair of numbers equals $m$. On the other hand, at a position of type $1$-$4$, the average number of agreeing pairs is $6/10$, while at a position of type $2$-$3$, it is $4/10$. Averaging over all positions gives

$$\frac{m}{n} = \frac{6x_1+4x_2}{10(x_1+x_2)}.$$

This is a weighted average of $\frac35$ and $\frac25$, so it lies between them.

The main proof is preferable because it avoids introducing averages and reduces the argument to a direct double count, making the source of the inequalities completely transparent.