Для зашифровки телеграфных сообщений требуется разбить всевозможные десятизначные "слова" – наборы из десяти точек и тире – на две группы так, чтобы каждые два слова из разных групп отличались не менее чем в трёх разрядах. Указать способ такого разбиения или доказать, что его не существует.

задан 2 Май 23:44

изменен 2 Май 23:48

10|600 символов нужно символов осталось
3

А зачем в условии требуется, чтобы аж в трех разрядах отличались? Доказывается, что разбиение не возможно даже при условии, что в двух разрядах должны отличатся. Допустим, что разбиение возможно. Пусть в групу А попало слово, состоящее из одних тире. Тогда в этой групе должны быть всевозможные слова из 9 тире и одной точки. Из этого, в свою очередь, следует, что в групе А должны быть всевозможные слова из 8 тире и двух точек, ибо для каждого из них найдется 9-тиренное слово с разницой только в одном разряде. И так далее по индукции получим, что все слова должны быть в групе А. Противоречие.

ссылка

отвечен 3 Май 0:18

изменен 3 Май 0:23

1

@Witold2357, Вы пишете: "А зачем в условии требуется, чтобы аж в трех разрядах отличались?" ...........
За что покупаем, за то и продаём, это задача 1967г. http://www.problems.ru/view_problem_details_new.php?id=78602

(3 Май 0:22) Казвертеночка
1

@Казвертеночка: там по ссылке решение, мягко говоря, специфическое. Ясно, что от любого буквосочетания к любому можно перейти, меняя по одному символу (подобно переходу от слова МУХА к слову СЛОН в известной игре). Отсюда всё сразу следует для случая двух разрядов.

(3 Май 2:21) falcao
1

@falcao, там по ссылке и задача-то другая. У меня каждые два слова из разных групп отличались не менее чем в трёх разрядах, а там - из одной...

(3 Май 11:40) Казвертеночка
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

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

по почте:

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

по RSS:

Ответы

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

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