Найти минимальное расстояние $%d_\min(A, B)$% между точками сфер $%A = S_{15}(\tilde α)$% и $%B = S_{13}(\tilde β)$% и число $%N_{A,B}$% пар ближайших точек из сфер $%A$% и $%B$%.

$$ \tilde α = 11111101011111110001111010100011010 \\ \tilde β = 01011111001101010100000001101011110 $$

задан 3 Май '15 15:02

изменен 3 Май '15 19:26

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

Так это опять всё тот же пример со строками длиной 35! Или здесь спрашивается всё то же самое, но для минимального расстояния вместо максимального?

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

(3 Май '15 15:05) falcao

@falcao у меня набор задачек, где надо рассмотреть 2 случая, т.е. подход один и тот же, мне нужно было решение любой, чтобы понять, что я делаю не так.

(4 Май '15 0:22) sleepless_study

@sleepless_study: если хотите, можно проанализировать Ваш ход мысли, чтобы понять, в чём дело.

(4 Май '15 0:26) falcao
10|600 символов нужно символов осталось
2

Удобно произвести преобразование координат, прибавляя ко всем векторам один и тот же вектор $%\alpha$%. Ясно, что попарные расстояния не будут меняться. Вектор $%\alpha$% станет при этом нулевым, а у $%\beta$% окажется 20 нулевых координат и 15 единичных.

Меняя 13 координат у $%\beta$%, мы за счёт нечётности получим вектор с чётным количеством единиц. Поэтому он не совпадёт с вектором, получаемым из $%\alpha$%, у которого 15 координат будут единичными. Таким образом, расстояния 0 между точками сфер нам не достичь, а расстояние 1 получится, если у $%\beta$% после изменений окажется 14 или 16 единиц.

Рассмотрим первый случай. Для уменьшения количества единиц на 1 нам надо переименовать 7 единиц и 6 нулей. Количество способов сделать это равно $%C_{15}^7C_{20}^6$%. При этом у вектора $%\alpha$% мы меняем 14 координат, ставших единичными у $%\beta$%, и ещё какую-то 15-ю координату, выбираемую из оставшихся. Поэтому произведение сочетаний пойдёт с коэффициентом $%21$%.

Теперь второй случай: для увеличения количества единиц на 1 меняем 6 единиц и 7 нулей. Количество способов равно $%C_{15}^6C_{20}^7$%. Получаем вектор с 16 единицами, и у $%\alpha$% меняем 15 из них, одну координату оставляя неизменной. Здесь коэффициент будет равен $%16$%.

Итого получается $%21C_{15}^7C_{20}^6+16C_{15}^6C_{20}^7=11445634200$% способов.

ссылка

отвечен 3 Май '15 20:49

@falcao в методичке дан ответ dmin=1
NA,B = 20􏰀(C из 16 по 9)(C из 19 по 6)􏰁 + 15􏰀(С из 14 по 8)(С из 􏰁􏰀21 по 7)=2855699608 мой мозг вынесен окончательно))

(4 Май '15 0:30) sleepless_study
1

@sleepless_study: я хотел отметить тот факт, что при разных способах подсчёта могут получаться разные выражения с участием сочетаний (как это ни странно). Но численный ответ, конечно, должен совпасть. Он и совпадает: приведённое Вами выражение даёт то же самое число 11445634200, которое было у меня. Я только что проверил в Maple.

То, что указанный Вами численный ответ неверен, достаточно очевидно. Левая часть делится на 5, а правая не делится. Так что "мозг" можно торжественно "внести" :)

(4 Май '15 0:36) falcao

@falcao фух, спасибо, в методичке, очевидно, ошибка, я так рада!!! Спасибо!

(4 Май '15 0:39) sleepless_study

@sleepless_study: ошибка только на уровне численного ответа (причём она бросается в глаза). Сам же ответ в форме сочетаний -- правильный, хотя там использованы другие выражения.

(4 Май '15 0:47) falcao

@falcao не поняла, как Вы делали преобразование координат, "прибавляя ко всем векторам один и тот же вектор альфа", не буквально же мы их складываем как двоичные числа?

(4 Май '15 1:22) sleepless_study
1

@sleepless_study: это совсем элементарный приём. К каждому вектору прибавляется фиксированный вектор $%a$% (поразрядно, по модулю 2). Расстояние между $%x$% и $%y$% было равно числу единиц вектора $%x+y$% (сумма в том же смысле). Ясно, что у $%x+a$% и $%y+a$% она будет такой же ввиду $%a+a=0$%.

(4 Май '15 1:25) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,870

задан
3 Май '15 15:02

показан
1194 раза

обновлен
4 Май '15 1:25

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru