Competition problem — Combinatorics

Library / /144 of 377

Combinatorics Difficulty 5.0 AIME Find the answer United States

Problem:
A binary string of length $n$ is a sequence of $n$ digits, each of which is $0$ or $1$ . The distance between two binary strings of the same length is the number of positions in which they disagree; for example, the distance between the strings $01101011$ and $00101110$ is $3$ since they differ in the second, sixth, and eighth positions.

Find as many binary strings of length $8$ as you can, such that the distance between any two of them is at least $3$ . You get one point per string.

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:
The maximum possible number of such strings is $20$ . An example of a set attaining this bound is

00000000	00110101
11001010	10011110
11100001	01101011
11010100	01100110
10111001	10010011
01111100	11001101
00111010	10101100
01010111	11110010
00001111	01011001
10100111	11111111

This example is taken from page 57 of F. J. MacWilliams and N. J. A. Sloane, The Theory of Error Correcting Codes (New York: Elsevier Publishing, 1977). The proof that

20

is the best possible is elementary but too long to reproduce here; see pages 537-541 of MacWilliams and Sloane for details.

In general, a set of $M$ strings of length $n$ such that any two have a distance of at least $d$ is called an $(n, M, d)$ -code. These objects are of basic importance in coding theory, which studies how to transmit information through a channel with a known error rate. For example, since the code given above has minimum distance $3$ , I can transmit to you a message consisting of strings in this code, and even if there is a possible error rate of one digit in each string, you will still be able to determine the intended message uniquely.

Want a route through all this instead of 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 reproduced verbatim; metadata (topic, difficulty) added by this project.