Найти число наборов, несравнимых ни с a, ни с b.

a=11110110111111001101011101

b=01110000011011001100011001

задан 10 Сен '18 20:32

изменен 10 Сен '18 20:39

@desriver: условие неполное. Прежде чем ставилась такая задача, должны были где-то сказать, что понимается под сравнимостью наборов. Этот признак должен быть частью условия.

Моё предположение: рассматривается частичный порядок <=, при котором для всех координат выполнено соответствующее неравенство; сравнимость рассматривается относительно этого порядка. Так ли это?

(10 Сен '18 23:12) falcao

@falcao Да, получается по условию наборы a и b сравнимы, если a<=b или b<=a

(10 Сен '18 23:22) desriver
10|600 символов нужно символов осталось
0

Здесь даны не какие попало векторы, а векторы с условием b <= a (можно даже написать строгое неравенство, так как векторы не равны).

Подсчитаем для начала, сколько векторов сравнимы с b. Это все векторы x со свойством x<=b, и векторы x со свойством b<=x. Сам вектор b входит и туда, и сюда. Значит, надо найти две величины, сложить их, и вычесть 1.

Векторы со свойством x<=b получаются так: заменяем какие-то координаты 1 у вектора b на 0. Всего у b имеется 12 координат, равных 1. Способов замены будет 2^{12}, так как каждый из них определяется подмножеством 12-элементного множества (включая пустое, когда мы ничего не меняем).

Аналогично, для векторов со свойством b<=x, мы берём какие-то нули у b и меняем на 1. Нулевых координат здесь 14, способов замены 2^{14}. Итого имеется B=2^{12}+2^{14}-1 векторов, сравнимых с b.

Тем же способом находим число векторов, сравнимых с a. Их будет A=2^{19}+2^{7}-1.

Теперь смотрим, сколько векторов сравнимы и с a, и c b. Это все векторы x<=b, и их 2^{12}; все векторы a<=x, и их 2^{7}. К ним надо добавить векторы со свойством b<=x<=a. Они получаются так: если координата у b и a та же самая, то у x она такая же. Если у b координата равна 0, и у a она равна 1, то у x её полагаем равной 0 или 1. Таких координат всего 7. Это видно непосредственно, а также может быть найдено по формуле 26-12-7. Итого 2^7 векторов со свойством b<=x<=a. Поскольку сами векторы b, a учтены дважды, имеем ответ C=2^{12}+2^7+2^7-2 для числа векторов, сравнимых и с b, и с a.

Формула A+B-C даёт число векторов, сравнимых хотя бы с одним из векторов b, a. Это 2^{14}+2^{19}-2^{7}. Осталось из общего числа наборов вычесть эту величину, что даёт ответ 2^{26}-2^{14}-2^{19}+2^7=66568320. Заметим, что это почти 2^{26}, то есть реально почти все наборы обладают требуемым свойством, то есть они ни с одним из двух наборов не сравнимы.

Можно проследить и общий смысл величин: 19 есть число координат 1 у большего вектора, 14 -- это число координат 0 у меньшего. Число 7 было получено по закону 26-(26-14)-(26-19)=14+19-26.

ссылка

отвечен 10 Сен '18 23:55

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,475
×1,295

задан
10 Сен '18 20:32

показан
779 раз

обновлен
10 Сен '18 23:55

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

по почте:

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

по RSS:

Ответы

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

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