HMMT 二月 2004 · 冲刺赛 · 第 45 题
HMMT February 2004 — Guts Round — Problem 45
题目详情
- 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. 7
解析
- 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. Solution: The maximum possible number of such strings is 20. An example of a set 16 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. 17