Тотализатор

Автор темы niefer 
ОбъявленияПоследний пост
ОбъявлениеРаботодателям и кадровым агентствам: Размещение вакансий26.03.2008 03:07
ОбъявлениеПравила и принципы форума «Высшая математика»28.10.2009 15:17
ОбъявлениеЗапущен новый раздел «Задачки и головоломки»29.08.2019 00:42
17.11.2011 21:12
Тотализатор
Задача такая: я играю в тотализаторе, мне нужно угадать результат не менее 4-х игр из 6. То есть, каким-бы результатом ни закончились данные 6 игр, нужно угадать резултат не менее 4-х игр не менее в одном билете. Количество билетов не ограничено.

Вопрос: какое наименьшее количество билетов требуется для обеспечения вышеуказаной цели?

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

А вот мои 25 билетов (выигрыш - "1", ничья - "x", проигрыш - "2"):

1 1 1 1 1 x x x x x x x x x x 2 2 2 2 2 2 2 2 2 2
1 1 1 1 1 x x x x x 2 2 2 2 2 x x x x x 2 2 2 2 2
1 1 1 1 1 2 2 2 2 2 x x x x x x x x x x 2 2 2 2 2
1 x x 2 2 1 x x 2 2 1 x x 2 2 1 x x 2 2 1 x x 2 2
1 x 2 x 2 1 x 2 x 2 1 x 2 x 2 1 x 2 x 2 1 x 2 x 2
1 2 x x 2 1 2 x x 2 1 2 x x 2 1 2 x x 2 1 2 x x 2


Присутствие всех 6 игр в каждом билете не обязательно.
19.11.2011 23:53
Варианты
Сформулирована задача построения минимального кода, покрывающего пространство Хемминга E6 над GF(3)
с радиусом покрытия 2.
Пожалуй, нужно проверить следующие вариантs.
1. Вариант с 23 кодовыми словами
02110221021012021221200
02121010200211202212000
02102102110221021001021
02102102121010202120210
02102102102102110212202
00022211100022211100211
2. Вариант с 21 кодовыми словами
002210221210102102201
010102121122010211000
021021102002102110211
021021201021010202121
021021021010221221010
022111000112200012100
(оптимальность не гарантируется).
Следует отметить, что в данной задаче для оптимального кода покрытия не существует (!) аналога в классе линейных кодов.
20.11.2011 11:47
Варианты
Ваш вариант с 23 билетами - это именно то, о чем я спрашивал.

К сожалению вариант с 21 билетами неудачный - вот те 11 случаев, которые не укладываются в этом наборе:
1 1 0 1 0 2
1 1 2 0 0 2
1 0 0 2 0 2
1 2 1 0 0 1
1 2 0 1 2 2
1 2 0 0 0 2
1 2 2 0 1 2
1 2 2 0 0 1
1 2 2 0 0 0
0 2 0 0 1 2
2 2 1 0 0 2

Буду признателен, если вы доработайте этот вариант, или даже уменьшите число билетов - я подозреваю, что должен сушествовать набор из 19 или 18 билетов. Я бы попробовал сам, но "пространство Хемминга E6 над GF(3) с радиусом покрытия 2" для меня звучит как какой-то малоизвестный диалект китайского ;)
21.11.2011 17:03
Уточнение и детали
Оказалось, что в варианте с 21 словами, начиная с 6-го слова, символы инвертировались. Таким образом, кодовая таблица этого варианта должна иметь вид:

002210112120201201102
010102212211020122000
021021201001201220122
021021102012020101212
021021012020112112020
022111000221100021200

Просьба проверить.
Про «пространство Хемминга над GF(3)» я написал, чтобы обозначить связь этой задачи со стандартными задачами кодирования. При этом задачу можно сформулировать в терминах многочленов над GF(3), что позволит решение искать в аналитическом виде.
Близкие конструкции:
- совершенный (4,2,1)-код Хемминга над GF(3) (числа соответственно: длина блока, число информационных символов в блоке, максимальная кратность исправляемых ошибок) одновременно является кодом упаковки и покрытия с радиусом 1. Т. е. 9 слов кода достаточно для «угадывания» результата 3-х игр из 4-х.
- совершенный (11,6,2)- код Голея над GF(3) (аналогично) обеспечивает «угадывание» 729 словами результата 9-ти игр из 11-ти.
Параметр исходной задачи 6 (игр) для построения красивых мат. конструкций не очень удачен, но можно попробовать что-либо смастерить из вышеуказанных кодов.
Временно (на 5 дней) взаимодействия по Интернету прерываю (морская прогулка).
21.11.2011 20:04
Уточнение и детали
Просто замечательно, уточненный код покрывает весь разброс всех 729 билетов. Середина вашего поста опять-таки на странном китайском, но я получил готовый рецепт и это меня устраивает.

Приятной прогулки по волнам (это где-то в южном полушарии? Зимой-то...).

Спасибо.

Надеюсь, по возвращении (набравшись позитива), вспомните о моих 19 билетах. Сейчас для меня важно именно 6 игр, и хотя упомянутое вами "9 слов... для... 3-х игр из 4-х" тоже интересно, но исходя из real-life-коэффициентов тотализаторов, вряд-ли этот вариант будет имет практическое значение. А вот 19 билетов для 4-х игр из 6 имеет очень даже практическое значение.



Редактировалось 6 раз(а). Последний 21.11.2011 22:47.
26.11.2011 16:14
И 19 – без проблем
Вот таблица (как и ранее, на боку)

0 1 2 2 0 1 0 1 1 2 2 0 0 1 2 0 1 1 2
0 0 1 2 1 1 2 2 0 0 1 0 2 2 0 1 2 1 1
0 2 0 1 1 2 2 0 1 2 1 0 2 0 1 0 2 1 2
0 2 0 1 2 1 1 2 0 2 0 1 0 1 2 2 0 1 2
0 2 2 1 0 1 2 1 2 0 0 1 1 0 2 2 0 2 1
0 2 1 0 1 0 2 2 1 1 2 2 0 0 0 0 1 2 2

А с 18-ю словами – большие трудности. Но было бы очень красиво – в каждой паре столбцов (кодовые таблицы обычно представляются в транспонированном виде относительно представленной) каждая пара символов встречалась бы ровно два раза.
О позитиве. Полушарие северное (Анталья), но тепло, солнечно и в других отношениях позитива здесь также много. Впереди по плану Питер – Финляндия (близ Лаявори) – Лондон и в феврале обратно к морю.
С пожеланиями удачи...
26.11.2011 17:22
И 19 – без проблем
Таблица работает,снимаю шляпу. Опубликовав эту задачу, я никак ни ожидал такого быстрого решения. Спасибо еще раз...

Честно говоря, много лет назад я обнаружил сначала вариант с 23 билетами, потом с 21 - это результат супер-эффективного метода: сильная сила (грубый перебор вариантов) + настойчивость + удача. И вот на днях мне стало нужно вспомнить эти наборы... 23 я вспомнил, с 21 что-то не ладилось. По этой причине я и открыл эту тему. И вот теперь у меня вариант с 19 билетами. Значит не зря я подозревал... я слышал голоса ;)

Правда метод у вас какой-то... с темными личностями - некто Хемминг... ;)



Редактировалось 4 раз(а). Последний 26.11.2011 18:04.
30.11.2011 01:20
Вот такие дела
От скуки вспомнил про задачу и сразу же случайно наткнулся на вариант с 17-ю словами

0 2 2 2 0 1 0 1 1 2 0 2 1 0 1 0 1
0 0 1 2 1 1 2 2 0 1 0 0 2 2 1 1 0
0 2 0 1 1 2 2 0 1 1 0 1 0 2 2 0 2
0 2 0 1 2 1 1 2 0 0 1 2 1 0 2 2 0
0 0 2 1 0 1 2 1 2 0 1 2 0 1 2 2 0
0 1 1 0 1 0 2 2 1 2 2 0 0 0 2 0 2

Отсюда следует, что про «каждую пару символов» написано (мной ранее) необосновано.
По существу: точное значение минимального числа слов не установлено, могу лишь утверждать, что оно не менее 11.



Редактировалось 1 раз(а). Последний 30.11.2011 01:43.
09.12.2011 20:55
Вот такие дела
17 - это как-то неприлично уже.

Я подозревал, что существует вариант с 19 билетами, но дальше уже фантазии не хватало. А вы взяли да выдали сразу 17. А еще намекаете на 11. Смею предположить, что предел 14 или может даже 13, но никак не 11.

У вас весьма полезные приступы скуки. Могу предложить лекарства обоюдополезные:
1. Упомянутое выше - 14 (или 13) слов для 4-х игр из 6.
2. Аналогичная задача для 6 игр из 9 - я думаю решение колеблется около 70 слов.

Но... я вас никак не призываю на новые подвиги, то что вы выложили здесь, уже больше того, что я просил.

Все-таки вы разбудили мои голоса снова... 11 - это не 17 ;)



Редактировалось 1 раз(а). Последний 09.12.2011 20:58.
08.01.2012 22:45
тотализатор
1 1 0 2
1 1 1 1
1 0 2 2
1 1 2 2
2 2 1 1
2 2 2 2.......в этих 4-х случаях ловли не будет......очень интересуюсь этой темой!))
09.01.2012 21:50
Конечно, я ответил бы ранее,
если был бы какой-нибудь результат.
«Ну нет у меня лодки, не-ту…» (на телепатическое воздействие с указанием предложить лодку).

1. Сначала для Serega126:
Тип задачи (построение кода покрытия с параметрами $ q=3, n=6, r=2, M \to min $) мной оговорен ранее. Код покрытия для данной задачи должен иметь число слов $ M \ge 11$. Поэтому вариант с $ M=4 $явно не подойдет. Легко видеть, что ни в один шар с центром в любой из предложе нных 4-х точек не попадает, например, последовательность $(000000) $(и многие другие).
2. Для Niefer и вообще.
То, что получена плохая нижняя граница числа слов в задаче (6,4), не должно радовать и вселять оптимизм. Приемлемой для данных случаев теории не подобрал. Классические границы (суммарный объем шаров должен превышать объем пространства) дают весьма грубые оценки $(M \ge 10)$. Маленькая хитрость улучшает эту границу до $ M \ge 11 $, но это не должно радовать, т. к. расхождение нижней и верхней оценок в абсолютном масштабировании велико. Пока не получены уточнения границ, на настоящий момент можно лишь утверждать, что $ 11 \le M \le 17 $. Поиски в направлении построения линейных кодов заведомо не дадут эффекта, т. к. для задачи (6,4) наилучший линейный код над $ GF(3) $ не может содержать менее 27 слов. Поэтому изыскания в направлении использования методов Боуза-Чоудхури-Хоквингема для данной задачи бесперспективны.
Пробные построения для задачи (9,6) привели к коду с 85 словами, но это безрадостный результат (я его выбросит и забыл).
Задачи такого типа известные и, безусловно, интересные. Много направлений для поиска: полиномы, блок-схемы, произведения пространств последовательностей, пополнения кодов упаковки, циклические последовательности, системы уравнений в целых числах и т. д.
Целенаправленно решать эту проблем возможности у меня, конечно, нет. Подобные комбинаторные задачи могут съедать все время, но не дать результата (например, определить максимальное число ортогональных латинских квадратов порядка 10, или построить совершенный код с параметрами (11 9,1) над 10-тичным алфавитом).
Но если, вдруг, что-нибудь существенное прояснится, то сообщу.
Думаю, что идеи могут появиться и у коллег, ознакомившихся с этими задачами.
12.01.2012 19:46
Продолжаем...
Рад, что тема не умерла.

@sadcamel:
Я повторяюсь, но, честно, ничего не понимаю в нижне-верхних границах и центровке шаров. К сожалению моя математика не выходит за рамки квадратного уравнения и элементарной комбинаторики, так что вся надежда на вас с Хеммингом. Я слежу за этой темой и буду рад, если вы что-нибудь новое скажете.

@serega126:
Все 4 ловятся билетом #15 - 112222.



Редактировалось 1 раз(а). Последний 12.01.2012 19:47.
15.01.2012 23:19
О задаче с шарами + детали
Мыслил в терминах шаров, поэтому предложение Serega126 о том, что «ловли не будет» понял неправильно. Осмысленный ответ дан niefer’ом.
Постараюсь пояснить «язык шаров» (к сожалению, коротко не получилось). Большинству это все известно, но кому-нибудь пригодится.
1. Популярно о задаче покрытия: $ q=3,n=6, r=2, IMI \to min $.
а. Введение. Обозначим $ E(6,3) $ – множество всех последовательностей длины 6 над троичным алфавитом (их число, очевидно, 729). В качестве троичного алфавита удобно принять множество $ A=${$ 0,1,2$} и использовать для построения функций над символами алфавита и над последовательностями из $E(6,3) $ операции по модулю 3. На основе операций $ +, - $ (определенных в $ A$) вводятся операции $ +, - $ сложения и вычитания (покомпонентного) последовательностей из $ E(6,3) $.
Весом Хемминга последовательности $ x=(x_1,…,x_n) \in E=E(n,q) $ называется число ненулевых компонент этой последовательности:
$ W(x)= \sum_i I(x_i \ne 0) $, где $ I(.)$ – индикаторная функция: $ I(True) = 1, I(False) = 0$.
Расстоянием Хемминга между последовательностями $ x, y$ называется число компонент, в которых последовательность $ y=(y_1,…,y_n)$ отличается от последовательности $ x $:
$ D(x,y)= \sum_i I(x_i \ne y_i) $).
Если должным образом в $ E$ определены операции $ +, - $ и элемент $ 0$, то, очевидно, $ D(x,y)= W(x-y) $, т. е. расстояние Хемминга между последовательностями равно весу Хемминга разности этих последовательностей.
Под пространством Хемминга обычно понимают метрическое пространство: $ <E, D>$.
б. Постановка задачи.
Пусть в соответствии с рассмотренным выше определены конструкции: $ E(6,3),W(),D(),+, -$.
Произвольная последовательность $y$ совпадает с заданной последовательностью $x$ в 4-х или более позициях тогда и только тогда, когда $ D(x,y) \le 2$, т.е. когда шар радиуса $ 2$ с центром в точке $ x$ включает (покрывает) точку $ y$.
Для $ x \in E, r=0,1,2…$ обозначим $ S(x,r) $ – шар радиуса $ r$ с центром в $ x$. Тогда записанное выше условие может быть сформулировано в виде:
последовательность y совпадает с заданной последовательностью $ x$ в 4-х или более позициях тогда и только тогда, когда $ y \in S(x,2) $.
Пусть $ M \subseteq E$ (т. е. $ M$ - код в $ E$). Мощностью (иногда объемом) кода $ M$ называют число элементов в $ M$ (обозначаемое $ IMI$). Радиусом покрытия кодом $ M$ пространства $ E$ (или просто «радиусом покрытия кода $ M$») называется наименьший радиус шаров с центрами в точках кода $ M$, покрывающих в совокупности все точки пространства $ E$.
Бытовой пример: На столе проставлены точки. Пусть круги радиуса 10 с центрами в данных точках покрывают всю поверхность стола, а круги меньшего радиуса не покрывают. Тогда радиус покрытия поверхности стола кодом из отмеченных точек равен 10.
С учетом введенных понятий рассматриваемая задача имеет следующую математическую формулировку:
Найти код $ M \in E(3,6) $ минимальной мощности, с радиусом покрытия $ 2$.
Ранее приведен пример кода с радиусом покрытия $ 2$ мощности $ 17$.
2. Некоторые детали.
а. Эквивалентные коды.
Поскольку параметры покрытия зависят лишь от метрической структуры кода, то преобразования кода, не меняющие его метрическую структуру, не изменяют свойства покрытия. При этом если код $ M$ имеет радиус покрытия $ 2$, то, очевидно, и эквивалентные коды, т. е. полученные в результате, так называемых, эквивалентных преобразований:
- перестановок компонент последовательностей,
- прибавления к каждому кодовому слову произвольной (одной и той же) последовательности,
будут иметь радиус покрытия $ 2$.
б. Объемы шаров и нижние границы.
Нижние границы элементарно получаются из следующих соображений.
Каждый шар содержит ровно $ N(q,n,r) = \sum_{j=0}^r C_n ^j(q-1)^j $ элементов. Поэтому множество из $ m$ шаров не может содержать более $ mN(q,n,r) $ точек и, следовательно, число элементов $ m=IMI$ покрывающего кода удовлетворяет неравенству
$ mN(q,n,r) \ge q^n$, откуда $ m \ge q^n/ N(q,n,r) $.
в. Элементарная граница. В нашем случае $ N(3,6,2) =73$, поэтому $ m \ge 729/730 \Rightarrow m \ge 10$.
г. Возможности для улучшения нижней границы.
Нетрудно установить (например, с использованием эквивалентных преобразований), что из любых $ 4$ шаров радиуса $ 2$ в $ E(3,6) $, по крайней мере, 2 пересекаются и, следовательно, объем любых 4-х шаров не может превышать $4x73-1$. Отсюда следует:
$ m \ge 4x729/ (4x73-1) \ge 10,2 \Rightarrow m \ge 11$.
Дальнейшее улучшение нижней границы возможно на основе получения верхней оценки максимального объема области покрытия 5-ю, 6-ю и более шарами (ограничивается вычислительной сложностью). Так, для того, чтобы убедиться в справедливости неравенства $ m \ge 12$ достаточно получить одну из оценок объема области покрытия
Число шаров 5 6 7
объем области покрытия $ \le $ 331 397 463
а для неравенства $ m \ge 13$ – соответственно из оценок
Число шаров 6 7
объем области покрытия $ \le $ 364 425
Число переборов можно сократить, если во всех вариантах использовать фиксированные две последовательности $ (000000) $ и $ (001111) $. Обоснованность такого выбора обусловлена возможностью приведения любого доминирующего варианта к варианту с указанными последовательностями путем эквивалентных преобразований.
Имеется много других возможностей для сокращения числа переборов.
С другой стороны, поиск шаров с максимальным суммарным объемом полезен для построения кода, наилучшим образом решающего сформулированную задачу.
Будем надеяться, что кто-нибудь посчитает.
16.12.2012 10:28
Перед концом света
Оживляю тему - календарь Майя торопит...

Не хочу покинуть этот бренный мир, не узнав ответа на сущий вопрос жизни - существует ли вариант с количеством вариантов меньше 17 ?
16.12.2012 10:46
Интересно,...
что если речь идет о классическом футболе, то со времени изменения правил, согласно которым за выигрыш присуждается 3 очка, а за ничью 1, количество ничьих в среднем, резко упало...
16.12.2012 13:55
21122012
Цитата
niefer
Оживляю тему - календарь Майя торопит...
Разложение на простые множители числового образа дат, прости Господи, конца света:
$21122012=2\cdot2\cdot5280503$
и
$2012=2\cdot2\cdot503$
Простые числа $5280503$ и $503$ принадлежат одной и той же подпоследовательности $p=6n-1$
Следовательно, конец света переносится на другую дату smile
16.12.2012 14:20
Задача из разряда «под контролем»
Воспользуюсь случаем, чтобы устранить неточность, которую я (ранее sadcamel) допустил в предыдущем сообщении.
Цитата
sadcamel
Нетрудно установить (например, с использованием эквивалентных преобразований), что из любых $ 4$ шаров радиуса $ 2$ в $ E(3,6) $, по крайней мере, 2 пересекаются и, следовательно, объем любых 4-х шаров не может превышать $4x73-1$. .
На самом деле, вот перечень непересекающихся 4-х шаров радиуса 2 в $ E^6 $:
$ (000000), (011111), (101222), (222012). $ Указанные центры шаров образуют в $ E^6 $ правильный тетраэдр с длиной ребра равной 5.
Вместе с тем справедливость оценки $ m(6,2) \ge 11 $ можно установить на основе рассмотрения конструкций с 5-ю шарами радиуса 2.
Есть еще неточность в рассуждениях насчет двух фиксированных последовательностей,… тоже без фатальности.
Цитата
niefer
Не хочу покинуть этот бренный мир, не узнав ответа на сущий вопрос жизни - существует ли вариант с количеством вариантов меньше 17 ?
Сам удивляюсь, как получил этот код. Если будет найдено 16 покрывающих шаров, то аналогичный вопрос возникнет относительно их минимальности. В данном случае, конечно, еще есть надежда на возможность перебора с усечением всех вариантов. А что делать с $ E^{15} $?
Узнаем ли мы ответы на вопросы о максимальном числе ортогональных латинских квадратов порядка 10 или о существовании совершенного кода хотя бы над каким-нибудь составным алфавитом (например, 10)?
---------------------
Информация для объекта – это то (конечно, не все то), что влияет (может повлиять) на его поведение. Все остальное – шумовой фон. Если говорят, значит, кому-то это нужно….говорить. (Это не только о Майя).
19.02.2017 19:42
Интересно
А сколько понадобится слов при условии, что надо угадать не менее 13 игр из 15ти ?
26.02.2017 18:12
Легко прикинуть, что ...
... не менее 31816. Чтобы убедиться, достаточно поделить объем пространства на объем шара радиуса 2.
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти