2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Двоичная комбинаторика
Сообщение14.05.2011, 12:50 
Заслуженный участник


02/08/10
629
Пусть X обозначает множество всех двоичных последовательностей длины 24. Y - произвольное подмножество X, в котором каждые два элемента отличаются не менее чем в 8 позициях. Доказать, что множество Y содержит не более, чем 4096 элементов.

 Профиль  
                  
 
 Re: Двочиная комбинаторика
Сообщение14.05.2011, 13:37 


03/10/10
102
Казахстан
Что-то не выходит. Двоичная последовательность, как я понял, это последовательность из нулей и едениц, так? Тогда для Y выберем произвольный базисный элемент a из Х. Отличается в какой-то позиции это значит вместо нуля - еденица, вместо еденицы - нуль. Тогда кол-во элементов, отличающихся от a в 8 позициях равно $C^8_{24}$, в 9 - $C^9_{24}$,..., в 24 - $C^{24}_{24}$. Но $ \frac{1}{2} \cdot C^{12}_{24} + C^{13}_{24}+...+C^{24}_{24}= \frac{1}{2} \cdot (C^1_{24}+ C^2_{24}+...+C^{24}_{24})=2^{23} \ge 2^{12}$ Может я что-то не понял или все же какая-то ошибка?

 Профиль  
                  
 
 Re: Двочиная комбинаторика
Сообщение14.05.2011, 13:51 
Заслуженный участник


02/08/10
629
Simba в сообщении #445742 писал(а):
Что-то не выходит. Двоичная последовательность, как я понял, это последовательность из нулей и едениц, так? Тогда для Y выберем произвольный базисный элемент a из Х. Отличается в какой-то позиции это значит вместо нуля - еденица, вместо еденицы - нуль. Тогда кол-во элементов, отличающихся от a в 8 позициях равно $C^8_{24}$, в 9 - $C^9_{24}$,..., в 24 - $C^{24}_{24}$. Но $ \frac{1}{2} \cdot C^{12}_{24} + C^{13}_{24}+...+C^{24}_{24}= \frac{1}{2} \cdot (C^1_{24}+ C^2_{24}+...+C^{24}_{24})=2^{23} \ge 2^{12}$ Может я что-то не понял или все же какая-то ошибка?

В этом подмножестве ЛЮБЫЕ 2 элемента должны отличаться не менее чем в 8 позициях, а Вы зачем-то берёте 1 базисный элемент.

Зы, Модераторы, исправьте пожалуйста опечатку в названии темы=)

 Профиль  
                  
 
 Re: Двоичная комбинаторика
Сообщение31.05.2011, 17:03 
Модератор
Аватара пользователя


11/01/06
5710
MrDindows в сообщении #445729 писал(а):
Пусть X обозначает множество всех двоичных последовательностей длины 24. Y - произвольное подмножество X, в котором каждые два элемента отличаются не менее чем в 8 позициях. Доказать, что множество Y содержит не более, чем 4096 элементов.

Это же бабл-гам двоичный код Голея [24, 12, 8].

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group