2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Комбинаторика
Сообщение21.07.2010, 18:42 
Rubik в сообщении #340255 писал(а):
Например очевидно, что для двузначных чисел такое множество содержит $n$ элементов.
Прям таки очевидно? ;-)
000
011
101
110

 
 
 
 Re: Комбинаторика
Сообщение21.07.2010, 18:45 
Аватара пользователя
venco в сообщении #340256 писал(а):
Rubik в сообщении #340255 писал(а):
Например очевидно, что для двузначных чисел такое множество содержит $n$ элементов.
Прям таки очевидно? ;-)
000
011
101
110

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

 
 
 
 Re: Комбинаторика
Сообщение21.07.2010, 18:46 
Пардон, я прочитал "двоичных".

 
 
 
 Re: Комбинаторика
Сообщение21.07.2010, 21:57 
Аватара пользователя
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$.

 
 
 
 Re: Комбинаторика
Сообщение22.07.2010, 10:22 
Аватара пользователя
maxal в сообщении #340288 писал(а):
В общем случае, для произвольного расстояния $d$ - это открытая проблема уже для $n=2$, текущее состояние которой описано тут: http://www2.research.att.com/~njas/codes/And/

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

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

 
 
 
 Re: Комбинаторика
Сообщение22.07.2010, 15:19 
Аватара пользователя
Rubik в сообщении #340332 писал(а):
Что такое $d$?

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

 
 
 
 Re: Комбинаторика
Сообщение22.07.2010, 17:18 
Аватара пользователя
maxal в сообщении #340288 писал(а):
Кстати, аналогичным образом легко получается нижняя оценка $n^{k-1}$. Но она является строгой уже для $n=4$.

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

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

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

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

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

 
 
 
 Re: Комбинаторика
Сообщение22.07.2010, 21:08 
Аватара пользователя
Circiter в сообщении #340427 писал(а):
Конструировать максимальное множество несвязанных чисел можно так.

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

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

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group