Problem of the Month (September 2011)

A multi-set is an unordered collection of digits, not all of which need to be distinct. The distance between two multi-sets A and B is the smallest number of different components between orderings of A and B. In other words, it is the smallest number of digits we need to change in A to get some permutation of B.

A multi-set code with base B, length L, distance D, and magnitude N is a collection of N multi-sets, each containing L digits from 1 to B, each with pairwise distance at least D. For example, a multi-set code with base B=6, length L=3, distance D=2, and magnitude N=10 is {111, 222, 333, 444, 555, 666, 123, 145, 256, 346}.

Given B, L, and D, what is the largest possible value of N?

This problem came up with B=6 in trying to identify N collections of L dice that were as "far apart" as possible.

ANSWERS

Answers were received by Johan de Riuter and Maarten Löffler, and Mark Mammel.

When B=1, there is only one possible multi-set, so N=1.

When B=2, the problem is trivial, with N = L/D .

When D>L, two strings cannot be distance D, so N=1.

When (1–1/B)L<D≤L, the only multi-sets possible are all the same, so N=B.

Notice below that the the columns are increasing, and the rows and diagonals are decreasing. This can be used to determine which values are most likely to be improved.

Below are the largest-known values of N for a given B, L, and D:

B=3
L \ D23456
34
{xxx, 123}
46
{xxyy}
57
{xxxxx,
11133, 22233,
12333, 11223}		4
{xxxxx, 11223}
610
{xxyyzz}		6
{xxxyyy}		4
{xxxxxx, 112233}
712
{xxxxxx, 1111133,
1111223, 1112222,
1112333, 1122233,
1133333, 1222223,
2222333, 2233333}		6
{xxxxyyy}		4
{xxxxxxx, 1112223}
815
{wwxxyyzz}		8
{xxxxxxxx, 11111222,
11111333, 22222113,
33333112, 22223333}		6
{xxxxyyyy}		4
{xxxxxxxx,
11122233}
919
{xxxxxxxxx,
111111123, 111111222,
111111333, 111112233,
111122223, 111123333,
111222222, 111222333,
111333333, 112222233,
112233333, 122222223,
122223333, 123333333,
222222333, 222333333}		10
{xxxxxxxx, 111111233,
111112222, 111133333,
111222333, 112222223,
122333333, 222223333}		6
{xxxxxyyyy}		4
{xxxxxxxxx,
111222333}		4
{xxxxxxxxx,
111222333}
1022
{xxxxxxxxxx, 2233333333,
2222333333, 2222222333,
1222223333, 1222222223,
1133333333, 1122233333,
1122222233, 1112333333,
1112222333, 1112222222,
1111223333, 1111222223,
1111133333, 1111122233,
1111112333, 1111112222,
1111111223, 1111111133}
(JR+ML) 		11
{xxxxxxxxxx,
2223333333, 2222223333,
1122222223, 1113333333,
1112223333, 1111122222,
1111113333, 1111111223}
(JR+ML) 		7
{xxxxxxxxxx,
2222333333, 1111333333,
1111222222, 1111112233}
(JR+ML) 		6
{xxxxxyyyyy}		4
{xxxxxxxxxx,
1111222333}

B=4
L \ D23456
35
{xxx, 123}
411
{xxyy, 1234}		5
{xxxx, 1234}
514
{xxxxx, 11222, 11234,
11333, 11444, 12233, 12244,
13344, 22234, 23334, 23444}		6
{xxxxx,
11223, 23344}
624
{xxyyzz, wwwxyz}		10
{xxxyyy}		5
{xxxxxx, 112234}
730
{xxxxxxx, 1111124, 1111133,
1111222, 1111344, 1112234,
1112444, 1113334, 1122222,
1122233, 1122244, 1123333,
1123344, 1134444, 1222234,
1223334, 1223444, 1244444,
1333334, 1333444, 2222233,
2222244, 2223333, 2223344,
2224444, 2333344, 2334444}
(MM) 		12
{xxxxxxx, 1112224, 1113333,
1114444, 1123344, 1222233,
2224444, 2233334, 3334444}		6
{xxxxxxx,
1112223, 2333444}		5
{xxxxxxx,
1122334}
845
{wwxxyyzz, xxyy1234}
(MM)		16
{xxxxxxxx,
11111222, 11111334, 11112444,
11122333, 11222344, 11333334,
11334444, 12222233, 12244444,
22222444, 22233333, 23333444}
(MM)		11
{xxxxyyyy, 11223344}
(MM)		5
{xxxxxxxx,
11223344}		5
{xxxxxxxx,
11223344}

B=5
L \ D2345
37
{xxx, 123, 345}
416
{xxyy, 1234}
(MM)		6
{xxxx, 1234}
525
{xxxxx, 11125, 11133,
11144, 11222, 11234,
11455, 12235, 12333,
12445, 13345, 13444,
13555, 22245, 22334,
22444, 22555, 23455,
33344, 33355, 44455}
(MM)		10
{xxxxx, 12233, 11255,
11344, 22445, 33455}		6
{xxxxx, 12345}
642
{xxxxxx, 111122,
111135, 111144, 111245,
111334, 111555, 112224,
112255, 112335, 112344,
113333, 113455, 114445,
122225, 122233, 122345,
123334, 123555, 124455,
133355, 133445, 134444,
145555, 222234, 222355,
222445, 223333, 223344,
224444, 224555, 233455,
234445, 333345, 333444,
335555, 344555, 444455}
(MM)		16
{xxxxxx, 111222, 111333,
111455, 112444, 122555,
123345, 222333, 222445,
333444, 333555, 444555}
(MM)		7
{xxxxxx,
112233, 114455}
766
{xxxxxxx, 1111125,
1111133, 1111223, 1111244,
1111345, 1111555, 1112222,
1112245, 1112334, 1112355,
1113335, 1113444, 1114455,
1122234, 1122255, 1122335,
1122444, 1123333, 1123445,
1124555, 1133344, 1133455,
1135555, 1144445, 1222224,
1222235, 1222333, 1222445,
1223344, 1223455, 1225555,
1233345, 1233555, 1234444,
1244455, 1333334, 1333355,
1334445, 1344555, 1455555,
2222233, 2222255, 2222344,
2223345, 2223555, 2224444,
2233334, 2233355, 2234445,
2244555, 2333335, 2333444,
2334455, 2345555, 2444445,
3333445, 3334555, 3344444,
3355555, 3444455, 4445555}
(MM)		21
{xxxxxxx, 1111222,
1111333, 1111444, 1111555,
1122334, 1134455, 1222244,
1224555, 1333355, 1334444,
2222355, 2223333, 2244445,
2333445, 2335555, 4445555}
(MM)		10
{xxxxxxx, 1122555,
1133444, 1222333,
2224445, 3334555}		6
{xxxxxxx,
1122345}

B=6
L \ D2345
310
{xxx, 123,
145, 256, 346}
424
{xxyy, 1234,
1256, 3456}
(MM)		7
{xxxx, 1234}
542
{xxxxx,
11123, 11145, 11224, 11255,
11266, 11334, 11356, 11446,
12223, 12256, 12336, 12345,
13335, 13444, 13466, 13555,
14556, 15666, 22255, 22266,
22335, 22346, 22445, 23344,
23556, 23666, 24446, 24555,
24566, 33346, 33455, 33566,
34456, 44455, 44666, 55566}
(MM) 		12
{xxxxx,
11223, 33445, 55661,
11446, 22554, 33662}		7
{xxxxx, 12345}
680
{xxxxxx, 111125, 111134,
111166, 111223, 111246, 111333,
111356, 111444, 111455, 112226,
112244, 112255, 112336, 112345,
112566, 113344, 113355, 113466,
114456, 115556, 116666, 122224,
122235, 122334, 122366, 122456,
123335, 123446, 123556, 124445,
124555, 124666, 133334, 133366,
133456, 134444, 134455, 135555,
135666, 144466, 145566, 222233,
222256, 222346, 222445, 222555,
222666, 223333, 223356, 223444,
223455, 224466, 225566, 233346,
233445, 233555, 233666, 234566,
244446, 244556, 255556, 256666,
333356, 333444, 333455, 334466,
335566, 344456, 345556, 346666,
444455, 445555, 445666, 555666}
(MM)		23
{xxxxxx, 111333, 111555,
111666, 112236, 114456,
122245, 123444, 133556,
222333, 222666, 223555,
234566, 333445, 333666,
444555, 444666, 555666}
(MM)		10
{xxxxxx,
112233, 114455,
115566, 334466}		7
{xxxxxx,
123456}

B=7
L \ D2345
314
{xxx, 123, 145, 167,
246, 257, 347, 356}
435
{xxyy, 1234, 1267, 1357,
1456, 2356, 2457, 3467}
(MM)		9
{xxxx, 1234, 4567}
566
{xxxxx, 11122, 11133, 11144,
11155, 11167, 11237, 11256,
11346, 11457, 11666, 11777,
12224, 12236, 12257, 12333,
12344, 12455, 12466, 12477,
13345, 13367, 13557, 13566,
14445, 14467, 15556, 15677,
22233, 22256, 22277, 22345,
22444, 22467, 22555, 22666,
23347, 23356, 23577, 23667,
24456, 25567, 26777, 33344,
33357, 33555, 33666, 33777,
34446, 34457, 34556, 34677,
44477, 44555, 44666, 45667,
45777, 55577, 55666, 66677}
(MM)		17
{xxxxx, 11567,
12277, 13366, 14455,
22335, 22446, 25566,
33447, 35577, 46677}		8
{xxxxx, 12345}
6132
(MM)		33
{xxxxxx,
111222, 111336, 111577,
112347, 112555, 112666,
114456, 122333, 122444,
122567, 135566, 146777,
222355, 222466, 222777,
233456, 236677, 244577,
333447, 333555, 333666,
335777, 344466, 444555,
456667, 555555, 555677}
(MM)		14
{xxxxxx, 112233,
114455, 116677,
224466, 225577,
334477, 335566}		8
{xxxxxx,
123456}

B=8
L \ D2345
316
{xxx, 138, 147, 156,
237, 246, 258, 345, 678}
450
{xxyy, 1237, 1248,
1256, 1345, 1368, 1467,
1578, 2346, 2358, 2457,
2678, 3478, 3567, 4568}
(MM)		10
{xxxx, 1234, 5678}
598
(MM)		22
{xxxxx, 11226, 11347,
11558, 13388, 14466,
16778, 22337, 22455,
23468, 24477, 25667,
33445, 35577, 45788}
(MM)		9
{xxxxx, 12345}
6231
(MM)		46
{xxxxxx, 111222, 111366,
111447, 111555, 111888,
112338, 115677, 122356,
122478, 125588, 126667,
134557, 144488, 145668,
177788, 222337, 222466,
222555, 222888, 223444,
226777, 233345, 234688,
235778, 244567, 333666,
333777, 333888, 334478,
335568, 346677, 444666,
444777, 445558, 457888,
555666, 555777, 666888}
(MM)		16
{xxxxxx,
113388, 114477,
115566, 223377,
224466, 225588,
334455, 667788}		9
{xxxxxx,
123456}

B=9
L \ D2345
321
{xxx, 129, 138, 147,
156, 237, 246, 258,
345, 369, 489, 579, 678}
463
{xxyy, 1246, 1257,
1289, 1348, 1356, 1379,
1459, 1678, 2345, 2369,
2378, 2479, 2568, 3467,
3589, 4578, 4689, 5679}
(MM)		12
{xxxx, 1234,
4567, 1789}
5139
(MM)		29
{xxxxx, 11288, 11335,
11449, 11677, 12279,
12456, 13478, 15599,
16689, 22366, 22448,
23377, 23589, 33499,
33688, 35567, 44667,
45588, 45779, 78899}
(MM)		11
{xxxxx, 12345, 56789}
6310
(MM)		60
{xxxxxx,
111229, 111333, 111488,
111555, 111777, 112344,
112568, 114579, 114666,
116999, 122366, 123888,
124899, 133468, 135569,
135778, 144467, 167889,
222333, 222444, 222555,
222688, 222777, 222999,
223789, 224569, 233567,
234558, 246678, 255779,
333444, 333555, 333666,
333777, 333889, 334599,
344566, 346779, 366899,
444555, 444999, 445777,
445889, 477888, 555667,
555888, 555999, 566688,
666777, 777899, 888999}
(MM)		21
{xxxxxx, 112299, 113388,
114477, 115566, 223377,
224466, 225588, 334455,
336699, 448899, 557799, 667788}		10
{xxxxxx,
123456}

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 9/1/11.