[seqfan] Hamming Fun!
DENIS BORRIS
daborris at rogers.com
Fri Oct 23 18:22:53 CEST 2015
Hello. I believe you can tell me if I'm correct or wrong.I came across this problem:...........................................................................................................A set of 7-number codes is produced using the digits 1,2,3,4,5,6,7.
2 codes are defined as similar if they differ by only one digit.
In the set, no 2 codes will be similar.
Digits may be used more than once in a code.
What is the maximum number of codes in this set?
(in other words, the Hamming distance between any 2 numbersis greater than 1)...........................................................................................................I believe the solution is:
n^(n-1) if n is even
n^(n-1)-(n-1) if odd
Why?
All numbers with same digit qualify if even, but not if odd.
For n=3, we have 7 (not 9):
{1, 1, 1}, {1, 2, 2}, {1, 3, 3}, {2, 1, 2}, {2, 2, 1}, {3, 1, 3}, {3, 3, 1}
{2, 2, 2} and {3, 3, 3} don't qualify.
For n=4, we have 64:
{1, 1, 1, 1}, {1, 1, 2, 2}, {1, 1, 3, 3}, {1, 1, 4, 4}, {1, 2, 1, 2},
{1, 2, 2, 1}, {1, 2, 3, 4}, {1, 2, 4, 3}, {1, 3, 1, 3}, {1, 3, 2, 4},
{1, 3, 3, 1}, {1, 3, 4, 2}, {1, 4, 1, 4}, {1, 4, 2, 3}, {1, 4, 3, 2},
{1, 4, 4, 1}, {2, 1, 1, 2}, {2, 1, 2, 1}, {2, 1, 3, 4}, {2, 1, 4, 3},
{2, 2, 1, 1}, {2, 2, 2, 2}, {2, 2, 3, 3}, {2, 2, 4, 4}, {2, 3, 1, 4},
{2, 3, 2, 3}, {2, 3, 3, 2}, {2, 3, 4, 1}, {2, 4, 1, 3}, {2, 4, 2, 4},
{2, 4, 3, 1}, {2, 4, 4, 2}, {3, 1, 1, 3}, {3, 1, 2, 4}, {3, 1, 3, 1},
{3, 1, 4, 2}, {3, 2, 1, 4}, {3, 2, 2, 3}, {3, 2, 3, 2}, {3, 2, 4, 1},
{3, 3, 1, 1}, {3, 3, 2, 2}, {3, 3, 3, 3}, {3, 3, 4, 4}, {3, 4, 1, 2},
{3, 4, 2, 1}, {3, 4, 3, 4}, {3, 4, 4, 3}, {4, 1, 1, 4}, {4, 1, 2, 3},
{4, 1, 3, 2}, {4, 1, 4, 1}, {4, 2, 1, 3}, {4, 2, 2, 4}, {4, 2, 3, 1},
{4, 2, 4, 2}, {4, 3, 1, 2}, {4, 3, 2, 1}, {4, 3, 3, 4}, {4, 3, 4, 3},
{4, 4, 1, 1}, {4, 4, 2, 2}, {4, 4, 3, 3}, {4, 4, 4, 4}
{2, 2, 2, 2} , {3, 3, 3, 3} and {4, 4, 4, 4} qualify
Hence, if n = 7: 7^6 - 6 = 117643
Thanks for any help: confirm above, or tell me I'm wrong!!
More information about the SeqFan
mailing list