Года три назад на форуме мехмата МГУ была сформулирована задача, которую предлагаю для рассмотрения.

«При игре в тотализаторе нужно угадать результат не менее 4-х игр из 6. То есть каким бы результатом ни закончились данные 6 игр, нужно угадать результат не менее 4-х игр не менее чем в одном билете. Вопрос: какое наименьшее количество билетов требуется для обеспечения вышеуказаной цели?»

Автор имел вариант из 25 билетов и надеялся, что должен существовать вариант с 19 (или даже меньше) билетами.

Эту задачу я перевел на язык покрытий следующим образом:

В пространстве Хемминга $% E^6_3 $%( $% n $% – размерность, $% q $% – мощность алфавита) найти минимальное число $% M $% шаров радиуса $% r=2,$% покрывающих $% E^6_3 .$%

Мне удалось (методом «рассуждений и манипуляций») построить покрытие из $% M =17 $% шаров. При этом моя нижняя оценка $% M \ge 11 .$%

задан 28 Дек '14 3:08

изменен 28 Дек '14 20:59

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


9917

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

Вот тут есть таблички. http://www.sztaki.hu/~keri/codes/index.htm То, что Вас интересует, там называется K3(6,2). Раздел 2 (троичные коды) содержит границы (верхние и нижние) для размерностей n <= 14 и радиусов R <= 8. В табличке указано, что верхняя граница 17 (так что поздравляю, у Вас наилучшее известное на сегодня покрытие), а нижняя 15 (вместо ваших 11).

Верхняя граница имеет ссылку на статью двух финнов 1991 года "Upper bounds for football pool problems and mixed covering codes" http://lib.gen.in/next/MTAuMTAxNi8wMDk3LTMxNjUoOTEpOTAwMjQtYg==/10.1016@0097-31659190024-B.pdf (по этой ссылке можно выкачать эту статью с пиратского ресурса LibGen).

Нижняя граница - ссылка на статью трех других авторов 2004 года "An updated table of binary/ternary mixed covering codes". Ссылка для скачивания http://lib.gen.in/next/MTAuMTAwMi9qY2QuMjAwMDg=/bertolo2004.pdf Там вроде достаточно несложная оценка, хотя я в детали не вкапывался.

ссылка

отвечен 5 Июн '15 17:00

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

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

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

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

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

отмечен:

×1,711
×1,414

задан
28 Дек '14 3:08

показан
1165 раз

обновлен
5 Июн '15 17:00

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

по почте:

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

по RSS:

Ответы

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

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