HMMT 二月 2004 · 冲刺赛 · 第 45 题

英文解析

45. A binary string of length n is a sequence of n digits, each of which is 0 or 1. Thedistance between two binary strings of the same length is the number of positionsin 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 betweenany 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 setattaining this bound is 16
    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. Mac williams and N. J. A. Sloane, The
    Theory of Error Correcting Codes (New York: Elsevier Publishing, 1977). The proofthat 20 is the best possible is elementary but too long to reproduce here; see pages
    537–541 of Mac williams and Sloane for details.
    In general, a set of M strings of length n such that any two have a distance of at leastd 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 toyou a message consisting of strings in this code, and even if there is a possible errorrate of one digit in each string, you will still be able to determine the intended messageuniquely.
    17