Задачка.

← →
Alx2 (2002-10-10 10:17) [0]

Дано 3 6-ти гранных кубика и 18 наклеек с цифрами от 1 до 18 соответственно.
Дано 2 игрока, A и B.
Игрок A наклеивает все наклейки на грани кубиков.
Игрок B смотрит и выбирает один кубик.
Игрок A выбирает один кубик из 2х оставшихся.
Hачинается игра, каждый игрок бросает свой кубик.
Выигрывает тот у кого больше очков выпало.

Вопрос: Как игрок A должен наклеить наклейки на кубики чтобы выигрывать максимально часто?

* Original in area RU.MATH

← →
NeyroSpace (2002-10-10 10:23) [1]

Может быть равномерно?

← →
Alx2 (2002-10-10 10:31) [2]

>NeyroSpace © (10.10.02 10:23)
Почему?

← →
MBo (2002-10-10 10:32) [3]

>Как игрок A должен наклеить наклейки на кубики чтобы выигрывать максимально часто

Нетранзитивно (камень, ножницы, бумага) c равными суммами по 57,
1>2>3, но 3>1 (> - чуть большая вероятность выигрыша)
и соответственно выбирать предыдущий в цикле.

← →
Alx2 (2002-10-10 10:36) [4]

>MBo © (10.10.02 10:32)
И какова тогда вероятность выигрыша у A?

← →
MBo (2002-10-10 13:25) [5]

19/36 для такого, например, расклада

3 13 4 5 18 14
11 12 16 9 2 7
1 17 15 8 6 10

Наилучший случай:
5/9 (20/36) для такого расклада (не единственный)

14 18 4 2 16 3
15 9 12 7 1 13
10 5 11 6 17 8

Если B выбрал i-й набор, нужно выбирать i+1 или первый, если выбран последний

← →
still (2002-10-10 13:39) [6]

мне кажется так, чтобы одинаковая сумма на всех была

← →
MBo (2002-10-10 13:48) [7]

>still
Да, это обязательно, но недостаточно.
Такой, например, набор
1 2 3 16 17 18
4 5 6 13 14 15
7 8 9 10 11 12
суммы одинаковые, но дает одинаковые вероятности выигрышей для всех комбинаций.

← →
Alx2 (2002-10-10 14:57) [8]

>MBo © (10.10.02 13:48)
В ответе: 21/36 и 15/36
PS
Сам еще не решал :(

← →
MBo (2002-10-10 14:58) [9]

>Alx2
Я не заметил 21/36, надо будет внимательнее посмотреть

← →
MBo (2002-10-10 15:14) [10]

вот некоторые варианты для 7/12

1 9 10 11 12 14
5 6 7 8 13 18
2 3 4 15 16 17

6 7 8 9 10 17
3 4 5 14 15 16
1 2 11 12 13 18

1 8 9 12 13 14
5 6 7 10 11 18
2 3 4 15 16 17

← →
RV (2002-10-10 15:15) [11]

MBo © (10.10.02 15:14)
как ты считаешь? какие методы?

← →
Alx2 (2002-10-10 15:20) [12]

>MBo © (10.10.02 15:14)
Наваял прогу. Выдала 1 :)))))
Ищу жука...

← →
MBo (2002-10-10 15:21) [13]

>RV
перебором

← →
Alx2 (2002-10-10 15:32) [14]

>MBo © (10.10.02 15:21
Уф, нашел :)
Оказывается, я считал как надо наклеивать тому, кто берет кубик первым. А ему и думать нечего :))

Вот мой вариант (один из) с p=21/36
[ 18 7 8 12 5 6 ] [ 4 17 15 16 2 3 ] [ 14 10 1 13 9 11 ]

Осталось доказать, что лучше не получится :)

← →
MBo (2002-10-10 15:39) [15]

Ух ты, разные суммы...
И сходится? Все по кругу бьют?
Я прогонял с разными суммами, но не заметил в просмотренном куске, чтобы все вероятности были по одну сторону от 18.
Надо еще попробовать.

← →
Alx2 (2002-10-10 15:56) [16]

>MBo © (10.10.02 15:39)
Однако из разных принципов исходили :)
Но мой вариант должен работать

← →
MBo (2002-10-10 16:29) [17]

5 6 7 8 12 18 #56 21
2 3 4 15 16 17 #57 21
1 9 10 11 13 14 #58 22

2 3 4 15 16 17 #57 21
1 9 11 12 13 14 #60 24
5 6 7 8 10 18 #54 21

3 4 5 6 17 18 #53 20
1 2 13 14 15 16 #61 24
7 8 9 10 11 12 #57 24

← →
Alx2 (2002-10-10 16:39) [18]

>MBo © (10.10.02 16:29)
Вот моя оценочная ф-я:

function Cost:Double;
Var c1,c2,c3,p12,p13,p23,p21,p31,p32 : Double;
begin
p12 := prob(1,2); // вероятность победить играя кубиком 1 против 2
p21 := prob(2,1);
p13 := prob(1,3);
p31 := prob(3,1);
p23 := prob(2,3);
p32 := prob(3,2);
c1 := min(p12,p13); // считаем, что враг себе возьмет лучший кубик - самый худший для нас случай. Тогда вероятность max(c1,max(c2,c3)) = вероятность его побед над нами, если он выбрал наилучший кубик
c2 := min(p21,p23);
c3 := min(p31,p32);
Result := 1-max(c1,max(c2,c3)); // максимизируя эту вещь = пытаемся ему не дать насладиться выбором кубика
end;

← →
MBo (2002-10-10 16:56) [19]

еще один
2 3 4 15 16 17 #57 21
1 10 11 12 13 14 #61 25
5 6 7 8 9 18 #53 21

← →
IGOREK (2002-10-11 03:49) [20]

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

← →
Alx2 (2002-10-11 08:41) [21]

>IGOREK © (11.10.02 03:49)
>Игрок Б для максимизации математического ожидания числа,
>которое выпадет, всегда будет выбирать кубик с максимальным >средним числом (соотв. суммой).

Не обязательно. Макс. ср. число (соотв. сумма) еще не означает, что таким кубиком можно чаще выигрывать. Вообще вероятность выигрыша одного кубика над другим от суммы зависит не столь явно.

Посмотри пост от MBo © (10.10.02 10:32) и несколько последующих его постов. Там суммы равны, но вероятности - нет.

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

Var
box : array [1..3,1..6] of integer

function prob(k1,k2 : integer):double;
Var k,l : integer;
begin
Result := 0;
for k := 1 to 6 do
for l := 1 to 6 do
if box[k1,k]>box[k2,l] then Result := Result + 1/36;
end;

Где k1 и k2 - номера кубиков. ф-я расчитывает вероятность выиграша k1 над k2. Так что дело не совсем в сумме, сколько в количестве преобладающих номеров на гранях кубика.
Как пример, кубик с номерами на гранях 0,0,0,0,0,1000 и 1,1,1,1,1,1. Очевидно, что первый кубик невыгоден для игры. Так как вероятность выиграть им = 1/6; Хотя сумма=1000, ср. сумма=500/3. А у второго все гораздо меньше: сумма = 6 и ср. сумма = 1

В нашем случае с номерами граней от 1 до 18 этот факт может показаться не существенным. Но это не так.

← →
Igorek (2002-10-12 12:03) [22]

2 Alx2 © (10.10.02 10:17)
Вы правы. Если бы спрашивалось о стратегии для максимального среднего колличества очков, то я был бы прав. Но все равно, неужели нету другого метода нахождения раскладок кроме перебора?

← →
Alx2 (2002-10-14 08:14) [23]

>Igorek © (12.10.02 12:03)
>Но все равно, неужели нету другого метода нахождения раскладок
>кроме перебора?

Есть, наверное :)
И было бы интересно с ним ознакомиться

← →
Igorek (2002-10-15 10:35) [24]

Доформализуем и обобщим немного задачу:
Есть набор 2*К чисел N1, N2...N2*K
Есть два гипотетических "кубика" с К колличеством граней.
При бросании кубика вероятности выпадания любой грани одна и та-же (1/К)
Дальше все по старому.

Вот тут у меня засветился такой алгоритм:
1) Формируем матрицу соотношений А[2K, 2K], причем
каждый элемент вычисл по характер. функции:
if i=j then
A[i,j]=-1
else
A[i,j]= Ni > Nj
2) разбиваем произвольным образом числа (и соотв матрицу по
столбцам и рядам) на 2 равные части.
3) высчитываем вероятность выиграша при таком разбиении чисел
4) формируем еще одну матрицу В[K, K], где каждый элемент - это
число, которое показывает насколько изменится вероятность выиграша при обмене двух чисел из разных наборов
5) начинаем итеративный процес, при котором обмениваем числа из разных наборов, пока общая вероятность выиграша не приблизится к 0,5. Начинаем обменивать пары с наибольшим выиграшем, потом по убыванию и заканчиваем, когда не найдется больше пары, обмен которой не принесет больше приближение общей вероятности к 0,5. Конечный набор и должен быть наиболее обтимальным разбиением (наверно).

Все описано на словах, но думаю идея будет понятна.
Решений может быть несколько, но это уже другая история. Предлагаю ее продолжить.

← →
Igorek (2002-10-15 13:02) [25]

Нет, итеративный процесс в п.5. должен быть посложнее, а то оно не найдет оптимум.

← →
Chorkov (2002-10-15 18:38) [26]

> Igorek ©
> Доформализуем и обобщим немного задачу:
> Есть набор 2*К чисел N1, N2...N2*K
> Есть два гипотетических "кубика" с К колличеством граней.
> При бросании кубика вероятности выпадания любой грани одна
> и та-же (1/К)

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

Для случая двух кубиков, решение может быть найдено аналитически:

Первый кубик: 1, 2, ... 1/2K, 3/2K+1, 3/2K+2, ... K
Второй кубик: 1/2K, 1/2K+1, 1/2K+2, ... , 3/2K
( предпологается, что K - четное, иначе вероятность 0.5 недостижима ).

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

← →
Igorek (2002-10-16 11:14) [27]

2 Chorkov (15.10.02 18:38)

> Непонятно как обощить предложенный алгоритм на случай большего
> числа кубиков.

Элементарно. Для начала заметим, что К должно быть кратно колл. кубиков умноженное на кол. граней. Если нет, то просто выкидываем столько чисел, сколько надо. Они все равно не нужны, а какие именно выкидывать не имеет значения. Если кубиков больше двух, то просто на все другие наклеиваем числа начиная с наименьших. Так мы гарантируем что последние два кубика гарантированно будут лучше остальных.
Кроме того, даже если числа N идут не по порядку, то их можно заменить последовательными - соотношения (больше-меньше) между ними сохраняться.

Насчет алгоритма: пока что светит только полный перебор в матрице В для нахождения такого набора обменов чисел, который максимально приблизит нас к вероятности 0,5

Кто предложит что-то получше?

← →
Alx2 (2002-10-16 11:26) [28]

Число сочетаний из 18 по 6 = 18564 - можно и полным перебором.
Если извращаться - то метод ветвей и границ подключить.
Если вручную - думать... :)

← →
Igorek (2002-10-16 12:19) [29]

2 Alx2 © (16.10.02 11:26)

> Если извращаться - то метод ветвей и границ подключить.

Вот и я тоже подозреваю, что на матрице В надо перебор методом ветвей и границ. Остается только его озвучить. ;-)

← →
Igorek (2002-10-18 11:45) [30]

Блин, достала эта задача. ;-)
2 Alx2
Слушайте, я наверно чего-то недопонимаю. Почему мы должны стремиться к вероятности 21/36 а не к 18/36? Если вероятность для одного кубика будет 21/36, то для другого соотв. 15/36. Противник же возьмет себе тот, что с 21/36 и нам останется только 15/36.
А для вероятности 18/36 алгоритм нахождения раскладки довольно простой.
Для начала раскладка такая:
первый кубик - 1..6
второй: 7,18,8,17,9,16
третий: 10,15,11,14,12,13

Алгоритм (на форме кнопка и два лейбла):
procedure TForm1.Button1Click(Sender: TObject); const N1 = 7; N2 = 18; var C2, C3: String; I, b1, b2: Integer; begin C2 := "Раскладка для второго кубика:"; C3 := "Раскладка для третьего кубика:"; b1 := N1 + (N2 - N1 + 1) div 4; b2 := N2 - (N2 - N1 + 1) div 4; for I:=N1 to N2 do if (I >= b1) and (I <= b2) then C3 := C3 + IntToStr(I) + " " else C2 := C2 + IntToStr(I) + " "; Label1.Caption := C2; Label2.Caption := C3; end;
Условием остается делимость разности (N1 - N2 + 1) на 4. Т.е. число граней кубика - парное.

← →
Alx2 (2002-10-18 12:07) [31]

>Igorek © (18.10.02 11:45)
:))
>вероятность для одного кубика будет 21/36, то для другого
>соотв. 15/36. Противник же возьмет себе тот, что с 21/36 и нам
>останется только 15/36.
Кубика ведь три? Пусть противник берет любой.Но у нас остается еще два кубика, один из которых обязательно лучше того, который бы взял противник. И кокой кубик противник не возьмет - у нас всегда есть в запасе кубик, который будет бить кубик противника. Им и играем. И при этом выясняется, что в худшем случае мы выигрываем с вер. 21/36. А если противник лоханется при выборе первого кубика, то мы выиграем с еще большей вероятностью.

← →
Igorek (2002-10-18 14:25) [32]

Задачка. Найти похожие ветки