Комбинаторика ("связанные числа")

[Rubik]

Два числа назовём связанными, если у них отличается только одно цифра. Сколько элементов содержит наибольшее множество попарно не связанных $k$-значных чисел в системе счисления с основанием $n$? ($n$-значным числом здесь считается число, состоящее из $n$ цифр от $0$ до $k-1$, то есть числа 0000, 0005 могут считаться четырёхзначными.) Например очевидно, что для двузначных чисел такое множество содержит $n$ элементов.

[venco]

Rubik в сообщении #340255 писал(а):

Например очевидно, что для двузначных чисел такое множество содержит $n$ элементов.

Прям таки очевидно?
000
011
101
110

[Rubik]

venco в сообщении #340256 писал(а):

Rubik в сообщении #340255 писал(а):

Например очевидно, что для двузначных чисел такое множество содержит $n$ элементов.

Прям таки очевидно?
000
011
101
110

Ну я ж написал - для двузначных.

[venco]

Пардон, я прочитал "двоичных".

[maxal]

Rubik в сообщении #340255 писал(а):

Два числа назовём связанными, если у них отличается только одно цифра. Сколько элементов содержит наибольшее множество попарно не связанных $k$-значных чисел в системе счисления с основанием $n$? Например очевидно, что для двузначных чисел такое множество содержит $n$ элементов.

В общем случае, для произвольного расстояния $d$ - это открытая проблема уже для $n=2$, текущее состояние которой описано тут: http://www.eng.tau.ac.il/~litsyn/tableand/

Впрочем, для расстояния $d=2$ (как в вашей задаче), ответ возможно и можно получить в явном виде. Например, для $n=2$ ответом будет $2^{k-1}$ (нужно взять все $(k-1)$-битные последовательности и приписать к каждой её бит четности).

-- Wed Jul 21, 2010 14:05:00 --

Кстати, аналогичным образом легко получается нижняя оценка $n^{k-1}$. Но она является строгой уже для $n=4$.

[Rubik]

maxal в сообщении #340288 писал(а):

В общем случае, для произвольного расстояния $d$ - это открытая проблема уже для $n=2$, текущее состояние которой описано тут: http://www2.research.att.com/~njas/codes/And/

Впрочем, для расстояния $d=2$ (как в вашей задаче), ответ возможно и можно получить в явном виде. Например, для $n=2$ ответом будет $2^{k-1}$ (нужно взять все $(k-1)$-битные последовательности и приписать к каждой её бит четности).

Что такое $d$?

[maxal]

Rubik в сообщении #340332 писал(а):

Что такое $d$?

Минимальное расстояние Хемминга между парами элементов в множестве. В вашей задаче $d=2$.

[maxal]

maxal в сообщении #340288 писал(а):

Кстати, аналогичным образом легко получается нижняя оценка $n^{k-1}$. Но она является строгой уже для $n=4$.

А вот для $n=3$ она дает точный ответ, как доказано в статье:
Bounds on Mixed Binary/Ternary Codes (см. Proposition 4.1)

[Circiter]

Что-то я не понимаю, по-моему, формула $n^{k-1}$ всегда дает точную оценку для задачи топикстартера. :)

Конструировать максимальное множество несвязанных чисел можно так. Будем перебирать последовательно значения первого (старшего) разряда и для каждого выбранного значения будем перебирать все значения второго разряда, &c. Последний же разряд (младший) пробегает значения из алфавита, полученного циклическим сдвигом (влево) исходного алфавита со смещением на единицу большим значения первого разряда. Любое число из такого множества, очевидно, отличается от каждого из оставшихся хотя-бы в одном из первых $k-1$ разрядов; причем, если оно отличается от него только в старшем разряде, то оно отличается от него и в дополнительном младшем разряде за счет сдвига алфавита.

Фактически, это лишь одно из возможных решений, но здесь важно, что во-первых, мощность построенного таким образом множества равна $n^{k-1}$, а во-вторых, добавить в это множество ещё какое-нибудь число уже не получится. Действительно, возьмем случайное число. Так как в построенном ранее множестве первые $k-1$ разрядов представляют всевозможные $(k-1)$-разрядные числа, то наше случайное число обязательно совпадет в этих разрядах с одним из уже имеющихся чисел. Значит, оно может отличаться от частично совпадающего числа лишь в младшем разряде (что, однако, противоречит несвязанности этих чисел), либо быть ему равным полностью...

Хотелось бы увидеть пример, в котором оценка $n^{k-1}$ врет... А то я тщательно проверил все комбинации только для $n=3$... :)

[maxal]

Circiter в сообщении #340427 писал(а):

Конструировать максимальное множество несвязанных чисел можно так.

Проще по аналогии с бинарным случаем: первые $k-1$ разрядов пробегают все возможные комбинации, а последний равен их сумме по модулю $n$.

Однако, доказательства максимальности $n^{k-1}$ для $n>3$ пока нет. Впрочем, я беру назад свои слова о строгости оценки для $n=4$ - это может быть и не так.