расстояние хемминга, подсчет числа последовательностей

[4aineg]

1. Для $\alpha = (110100)$,$\beta = (100010)$ найти все $\gamma \in B^6$,$\gamma \not = \alpha$,$\gamma \not = \beta$ такие что в неравенстве треугольника для
расстояния хемминга выполняется равенство $\rho(\alpha,\gamma)+\rho(\gamma,\beta)=\rho(\alpha,\beta)$ , где $\rho(\delta,\varepsilon)$ - расстояние хемминга между словами $\delta$ и $\varepsilon$.
тут в принципе не сложно получается можно перебрать все несовпадающие разряды, либо посчитать количество комбинаций $2^3$ несовпадающих разрядов и вычесть $\alpha$ и $\beta$ т.к. они будут в числе всех возможных комбинаций

2. Для $\alpha = (0101101)$,$\beta = (1000101)$ требуется найти количество $\gamma \in B^7$, для которых выполняется равенство $\rho(\alpha,\gamma)+\rho(\gamma,\beta) = 4$ , где $\rho(\delta,\varepsilon)$ - расстояние хемминга между словами $\delta$ и $\varepsilon$.

в соответствии с равенством $\rho(\alpha,\gamma)+\rho(\gamma,\beta) = 4$
возможные комбинации:
$\rho(\alpha,\gamma) = 1$
$\rho(\gamma,\beta) = 3$

$\rho(\alpha,\gamma) = 2$
$\rho(\gamma,\beta) = 2$

$\rho(\alpha,\gamma) = 3$
$\rho(\gamma,\beta) = 1$

ну рассмотрим
$\rho(\alpha,\gamma) = 1$
$\rho(\gamma,\beta) = 3$

возможные векторы тут:

$\gamma = (0100101) (0001101) (1101101)$

получается это соответствует $\rho(\alpha,\gamma) = 1$, но не соответствует $\rho(\gamma,\beta) = 3$, т.к. $\rho(\gamma,\beta) = 2$
подскажите пожалуйста как мне быть, задачу требуется решить срочно, скоро поступать.

Да у меня вопрос кстати, а можно ли из множества совпадающих векторов, назовем его(S) взять и поменять разряд в каком нибудь элементе, чтобы выполнилось $\rho(\alpha,\gamma)+\rho(\gamma,\beta) = 4$?

[Sonic86]

4aineg в сообщении #466594 писал(а):

ну рассмотрим
$\rho(\alpha,\gamma) = 1$
$\rho(\gamma,\beta) = 3$

возможные векторы тут:

$\gamma = (0100101) (0001101) (1101101)$

Как Вы их находили? Если Вы искали все вектора $\gamma$ такие, что $\rho(\alpha,\gamma) = 1$, то Вы нашли не все вектора - у Вас их всего 3, а можно найти ровно 7, меняя один разряд. Соответственно среди оставшихся можете поискать вектора $\beta: \rho(\gamma,\beta) = 3$. Кроме того, у Вас есть еще 2 случая. Если не найдете, значит таких векторов нету.

(а еще можно!)

а еще можно рассмотреть разность $\alpha - \beta$ и искать $\gamma$ для нее - так луче видно, существуют ли векторы и сколько их

4aineg в сообщении #466594 писал(а):

множества совпадающих векторов

Что это такое?

[Kallikanzarid]

4aineg
ИМХО, универсальный совет - руководствуйтесь тем, что $\rho(x,y) = \rho(x - y, 0) =: \|x - y\|$ - это норма на векторном пространстве $\mathbb{Z}_2^n$, то есть большинство ваших вопросов легко перевести на язык геометрии.

[4aineg]

значит получается можно менять разряды которые совпадают и в $\alpha$ и в$\beta$ а в формульном виде можно выразить это все?

[LaTeXScience]

Задача элементарно решается, если заметить, что $\rho_n((\alpha_1,...,\alpha_n),(\beta_1,...,\beta_n))=\rho_1(\alpha_1,\beta_1)+...+\rho_1(\alpha_n,\beta_n)$ и $\rho_1(\alpha_i,\beta_i)\leqslant 1$. Ну и свойства расстояния еще используйте.

-- 09.07.2011, 11:20 --

Kallikanzarid
А разность как определить? Чему будет равно, например, $(00)-(01)$?

[Kallikanzarid]

LaTeXScience в сообщении #466705 писал(а):

А разность как определить? Чему будет равно, например, $(00)-(01)$?

Разность по модулю 2 совпадает с суммой по модулю 2. Получается $(00) - (01) = (01)$, таким образом, $\rho((00), (01)) = \|(01)\| = 1$, норма Хэмминга просто считает единицы.

[4aineg]

вы конечно извините за тупой вопрос) ну что дает: $\rho_n((\alpha_1,...,\alpha_n),(\beta_1,...,\beta_n))=\rho_1(\alpha_1,\beta_1)+...+\rho_1(\alpha_n,\beta_n)$
и почему $\rho_1(\alpha_i,\beta_i)\leqslant 1$

извините конечно, просто я не давно стал все это изучать, причем самостоятельно...

-- Сб июл 09, 2011 13:49:17 --

Цитата:

а еще можно рассмотреть разность $\alpha - \beta$ и искать для нее $\gamma$ - так луче видно, существуют ли векторы и сколько их

по моему мы уже ее рассмотрели, это ведь и будет расстояние хэмминга. если опираться на $\Sum(\alpha-\beta) = 3$ всего $2^3$ таких векторов. но как привязать $\rho(\alpha,\gamma)+\rho(\gamma,\beta) = 4$ я никак не пойму(

Цитата:

так луче видно, существуют ли векторы и сколько их

что-то пока ничего не видно...

а можете написать ответ к задаче, чтоб мне свериться было с чем когда решу

[LaTeXScience]

4aineg
$\alpha_i$ и $\beta_i$ это 0 либо 1. У Вас равенство будет в первой задаче:
$3=A_1+...+A_6$, где $A_i=\rho_1(\alpha_i,\gamma_i)+\rho_1(\beta_i,\gamma_i)$.
Дальше по неравенству треугольника находите какие $A_i$ равны единице, а какие нулю. Зная все $A_i$ найдете $\gamma_i$, а значит и всю $\gamma$.
Kallikanzarid
Не понимаю как это поможет решить задачу, имхо, какие-то не нужные выкрутасы.

[Sonic86]

LaTeXScience в сообщении #466757 писал(а):

Не понимаю как это поможет решить задачу, имхо, какие-то не нужные выкрутасы.

Это Вам так кажется

[4aineg]

Цитата:

У Вас равенство будет в первой задаче

ну первая задача для меня составляет меньший интерес, т.к. я ее решил. да в соответствии с вашими рассуждениями сколько у вас получится количество $\gamma$?

[LaTeXScience]

Sonic86
Ну получится $\|\alpha-\gamma\|+\|\gamma-\beta\|=3$. И что дальше?
4aineg
Вроде бы 6. Во второй - 64.

[Kallikanzarid]

LaTeXScience в сообщении #466757 писал(а):

Не понимаю как это поможет решить задачу, имхо, какие-то не нужные выкрутасы.

Это общий совет, не связанный конкретно с этой задачей :)

-- Сб июл 09, 2011 20:17:58 --

Кстати, посмотрите на определение эллипса. У вас, конечно, будет не совсем аналогичная ситуация (потому что пространство не двумерное), но сравнить интересно.

[4aineg]

LaTeXScience
$A_1 + A_2 + A_3 + A_4 + A_5 + A_6 + A_7 = 4$

Получается $A_1, A_2 ,A_4$ принимают единицу, а дальше как? ведь получается в каком-то из элементов $A_3 A_5 A_6 A_7$ все равно придется брать расстояние равное 1му? можешь по подробней объяснить?

короче я пытался при помощи числа сочетаний сделать, у меня получилось 32. но я сильно сомневаюсь в правильности

конечная формула:

$2^{\rho(\alpha,\beta)} {n \choose k} = 32$

[4aineg]

$2^3 {4 \choose 1 } = 32$

[LaTeXScience]

Я неправильный ответ дал.
На самом деле здесь вообще нет решений.
$A_3$ не может равняться 1 ни при каких $\gamma_3$.
$A_5$ не может равняться 1 ни при каких $\gamma_5$.
$A_6$ не может равняться 1 ни при каких $\gamma_6$.
$A_7$ не может равняться 1 ни при каких $\gamma_7$.
Они могут быть равны только нулю или двум. Значит решений нет.