Есть одна очень интересная задачка на стыке комбинаторики и теории вероятностей с контр интуитивным решением. Знакомые попросили ее решить так чтобы ученик всё понял.
Постановка задачи 1
Бросают кубик три раза. Какова вероятность, что выпавшие значения образуют треугольник?
Постановка задачи 2
Бросают три кубика одним броском. Какова вероятность, что выпавшие значения образуют треугольник?
На первый взгляд кажется, что вероятность будет одинаковая. Какая разница как бросать?
Терминология
Размещение - В комбинаторике размещением (из n по k) называется упорядоченный набор из k различных элементов из некоторого множества различных n элементов (без повторений).
Сочетание - В комбинаторике сочетанием из n по k называется набор из k элементов, выбранных из n-элементного множества, в котором не учитывается порядок элементов (неупорядоченная выбока).
У треугольников есть одно интересное свойство. Сумма двух противоположных сторон (c+a) должна превышать длину ребра напротив (b). И так для каждого ребра. Можно даже написать функцию, которая будет вычислять какие 3 числа образуют треугольник, а какие нет.
static bool is_triangle(double a, double b, double c){
bool res = false;
if(c<(a+b)) {
if(b<(c+a)) {
if(a<(b+c)){
res = true;
}
}
}
return res;
}
Для решения этой задачи подойдет классическая схема вычисления вероятности.
Напомню как работает классическая схема вычисления вероятности. Тут есть 4 четких фазы.
Фаза 1) перечислить множество элементарных исходов.
Фаза 2) присвоить каждому элементу множества элементарных исходов его вероятность.
Фаза 3) выбрать благоприятные элементарные исходы исходя из условия задачи.
Фаза 4) поделить сумму вероятностей благоприятных исходов на сумму вероятностей элементарных исходов.
Для самопроверки сумма вероятностей всех элементарных исходов должна равняться единице.
Решение №1
Воспользуемся классической вероятностной схемой.
Сколько способов три раза бросить кубик? Это упорядоченное множество с повторениями. На первом шаге может выпасть один из 6ти, на втором шаге тоже один из 6ти и на третьем броске тоже один из 6ти. По правилу произведения, получается, что один кубик можно бросить три раза 216 различными способами.
6*6*6=216
Построим множество элементарных исходов эксперимента. Число всех элементарных исходов равно 216. Эти исходы равновероятны.
1, (1, 1, 1) ; 2, (1, 1, 2) ; 3, (1, 1, 3) ; 4, (1, 1, 4) ; 5, (1, 1, 5) ; 6, (1, 1, 6) ; 7, (1, 2, 1) ; 8, (1, 2, 2) ; 9, (1, 2, 3) ; 10, (1, 2, 4) ; 11, (1, 2, 5) ; 12, (1, 2, 6) ; 13, (1, 3, 1) ; 14, (1, 3, 2) ; 15, (1, 3, 3) ; 16, (1, 3, 4) ; 17, (1, 3, 5) ; 18, (1, 3, 6) ; 19, (1, 4, 1) ; 20, (1, 4, 2) ; 21, (1, 4, 3) ; 22, (1, 4, 4) ; 23, (1, 4, 5) ; 24, (1, 4, 6) ; 25, (1, 5, 1) ; 26, (1, 5, 2) ; 27, (1, 5, 3) ; 28, (1, 5, 4) ; 29, (1, 5, 5) ; 30, (1, 5, 6) ; 31, (1, 6, 1) ; 32, (1, 6, 2) ; 33, (1, 6, 3) ; 34, (1, 6, 4) ; 35, (1, 6, 5) ; 36, (1, 6, 6) ; 37, (2, 1, 1) ; 38, (2, 1, 2) ; 39, (2, 1, 3) ; 40, (2, 1, 4) ; 41, (2, 1, 5) ; 42, (2, 1, 6) ; 43, (2, 2, 1) ; 44, (2, 2, 2) ; 45, (2, 2, 3) ; 46, (2, 2, 4) ; 47, (2, 2, 5) ; 48, (2, 2, 6) ; 49, (2, 3, 1) ; 50, (2, 3, 2) ; 51, (2, 3, 3) ; 52, (2, 3, 4) ; 53, (2, 3, 5) ; 54, (2, 3, 6) ; 55, (2, 4, 1) ; 56, (2, 4, 2) ; 57, (2, 4, 3) ; 58, (2, 4, 4) ; 59, (2, 4, 5) ; 60, (2, 4, 6) ; 61, (2, 5, 1) ; 62, (2, 5, 2) ; 63, (2, 5, 3) ; 64, (2, 5, 4) ; 65, (2, 5, 5) ; 66, (2, 5, 6) ; 67, (2, 6, 1) ; 68, (2, 6, 2) ; 69, (2, 6, 3) ; 70, (2, 6, 4) ; 71, (2, 6, 5) ; 72, (2, 6, 6) ; 73, (3, 1, 1) ; 74, (3, 1, 2) ; 75, (3, 1, 3) ; 76, (3, 1, 4) ; 77, (3, 1, 5) ; 78, (3, 1, 6) ; 79, (3, 2, 1) ; 80, (3, 2, 2) ; 81, (3, 2, 3) ; 82, (3, 2, 4) ; 83, (3, 2, 5) ; 84, (3, 2, 6) ; 85, (3, 3, 1) ; 86, (3, 3, 2) ; 87, (3, 3, 3) ; 88, (3, 3, 4) ; 89, (3, 3, 5) ; 90, (3, 3, 6) ; 91, (3, 4, 1) ; 92, (3, 4, 2) ; 93, (3, 4, 3) ; 94, (3, 4, 4) ; 95, (3, 4, 5) ; 96, (3, 4, 6) ; 97, (3, 5, 1) ; 98, (3, 5, 2) ; 99, (3, 5, 3) ; 100, (3, 5, 4) ; 101, (3, 5, 5) ; 102, (3, 5, 6) ; 103, (3, 6, 1) ; 104, (3, 6, 2) ; 105, (3, 6, 3) ; 106, (3, 6, 4) ; 107, (3, 6, 5) ; 108, (3, 6, 6) ; 109, (4, 1, 1) ; 110, (4, 1, 2) ; 111, (4, 1, 3) ; 112, (4, 1, 4) ; 113, (4, 1, 5) ; 114, (4, 1, 6) ; 115, (4, 2, 1) ; 116, (4, 2, 2) ; 117, (4, 2, 3) ; 118, (4, 2, 4) ; 119, (4, 2, 5) ; 120, (4, 2, 6) ; 121, (4, 3, 1) ; 122, (4, 3, 2) ; 123, (4, 3, 3) ; 124, (4, 3, 4) ; 125, (4, 3, 5) ; 126, (4, 3, 6) ; 127, (4, 4, 1) ; 128, (4, 4, 2) ; 129, (4, 4, 3) ; 130, (4, 4, 4) ; 131, (4, 4, 5) ; 132, (4, 4, 6) ; 133, (4, 5, 1) ; 134, (4, 5, 2) ; 135, (4, 5, 3) ; 136, (4, 5, 4) ; 137, (4, 5, 5) ; 138, (4, 5, 6) ; 139, (4, 6, 1) ; 140, (4, 6, 2) ; 141, (4, 6, 3) ; 142, (4, 6, 4) ; 143, (4, 6, 5) ; 144, (4, 6, 6) ; 145, (5, 1, 1) ; 146, (5, 1, 2) ; 147, (5, 1, 3) ; 148, (5, 1, 4) ; 149, (5, 1, 5) ; 150, (5, 1, 6) ; 151, (5, 2, 1) ; 152, (5, 2, 2) ; 153, (5, 2, 3) ; 154, (5, 2, 4) ; 155, (5, 2, 5) ; 156, (5, 2, 6) ; 157, (5, 3, 1) ; 158, (5, 3, 2) ; 159, (5, 3, 3) ; 160, (5, 3, 4) ; 161, (5, 3, 5) ; 162, (5, 3, 6) ; 163, (5, 4, 1) ; 164, (5, 4, 2) ; 165, (5, 4, 3) ; 166, (5, 4, 4) ; 167, (5, 4, 5) ; 168, (5, 4, 6) ; 169, (5, 5, 1) ; 170, (5, 5, 2) ; 171, (5, 5, 3) ; 172, (5, 5, 4) ; 173, (5, 5, 5) ; 174, (5, 5, 6) ; 175, (5, 6, 1) ; 176, (5, 6, 2) ; 177, (5, 6, 3) ; 178, (5, 6, 4) ; 179, (5, 6, 5) ; 180, (5, 6, 6) ; 181, (6, 1, 1) ; 182, (6, 1, 2) ; 183, (6, 1, 3) ; 184, (6, 1, 4) ; 185, (6, 1, 5) ; 186, (6, 1, 6) ; 187, (6, 2, 1) ; 188, (6, 2, 2) ; 189, (6, 2, 3) ; 190, (6, 2, 4) ; 191, (6, 2, 5) ; 192, (6, 2, 6) ; 193, (6, 3, 1) ; 194, (6, 3, 2) ; 195, (6, 3, 3) ; 196, (6, 3, 4) ; 197, (6, 3, 5) ; 198, (6, 3, 6) ; 199, (6, 4, 1) ; 200, (6, 4, 2) ; 201, (6, 4, 3) ; 202, (6, 4, 4) ; 203, (6, 4, 5) ; 204, (6, 4, 6) ; 205, (6, 5, 1) ; 206, (6, 5, 2) ; 207, (6, 5, 3) ; 208, (6, 5, 4) ; 209, (6, 5, 5) ; 210, (6, 5, 6) ; 211, (6, 6, 1) ; 212, (6, 6, 2) ; 213, (6, 6, 3) ; 214, (6, 6, 4) ; 215, (6, 6, 5) ; 216, (6, 6, 6) ;
Из этих элементарных исходов только 111 будут образовывать треугольник. Вот они.
1, (1, 1, 1); 2, (1, 2, 2) ; 3, (1, 3, 3) ; 4, (1, 4, 4) ; 5, (1, 5, 5) ; 6, (1, 6, 6) ; 7, (2, 1, 2) ; 8, (2, 2, 1) ; 9, (2, 2, 2) ; 10, (2, 2, 3) ; 11, (2, 3, 2) ; 12, (2, 3, 3) ; 13, (2, 3, 4) ; 14, (2, 4, 3) ; 15, (2, 4, 4) ; 16, (2, 4, 5) ; 17, (2, 5, 4) ; 18, (2, 5, 5) ; 19, (2, 5, 6) ; 20, (2, 6, 5) ; 21, (2, 6, 6) ; 22, (3, 1, 3) ; 23, (3, 2, 2) ; 24, (3, 2, 3) ; 25, (3, 2, 4) ; 26, (3, 3, 1) ; 27, (3, 3, 2) ; 28, (3, 3, 3) ; 29, (3, 3, 4) ; 30, (3, 3, 5) ; 31, (3, 4, 2) ; 32, (3, 4, 3) ; 33, (3, 4, 4) ; 34, (3, 4, 5) ; 35, (3, 4, 6) ; 36, (3, 5, 3) ; 37, (3, 5, 4) ; 38, (3, 5, 5) ; 39, (3, 5, 6) ; 40, (3, 6, 4) ; 41, (3, 6, 5) ; 42, (3, 6, 6) ; 43, (4, 1, 4) ; 44, (4, 2, 3) ; 45, (4, 2, 4) ; 46, (4, 2, 5) ; 47, (4, 3, 2) ; 48, (4, 3, 3) ; 49, (4, 3, 4) ; 50, (4, 3, 5) ; 51, (4, 3, 6) ; 52, (4, 4, 1) ; 53, (4, 4, 2) ; 54, (4, 4, 3) ; 55, (4, 4, 4) ; 56, (4, 4, 5) ; 57, (4, 4, 6) ; 58, (4, 5, 2) ; 59, (4, 5, 3) ; 60, (4, 5, 4) ; 61, (4, 5, 5) ; 62, (4, 5, 6) ; 63, (4, 6, 3) ; 64, (4, 6, 4) ; 65, (4, 6, 5) ; 66, (4, 6, 6) ; 67, (5, 1, 5) ; 68, (5, 2, 4) ; 69, (5, 2, 5) ; 70, (5, 2, 6) ; 71, (5, 3, 3) ; 72, (5, 3, 4) ; 73, (5, 3, 5) ; 74, (5, 3, 6) ; 75, (5, 4, 2) ; 76, (5, 4, 3) ; 77, (5, 4, 4) ; 78, (5, 4, 5) ; 79, (5, 4, 6) ; 80, (5, 5, 1) ; 81, (5, 5, 2) ; 82, (5, 5, 3) ; 83, (5, 5, 4) ; 84, (5, 5, 5) ; 85, (5, 5, 6) ; 86, (5, 6, 2) ; 87, (5, 6, 3) ; 88, (5, 6, 4) ; 89, (5, 6, 5) ; 90, (5, 6, 6) ; 91, (6, 1, 6) ; 92, (6, 2, 5) ; 93, (6, 2, 6) ; 94, (6, 3, 4) ; 95, (6, 3, 5) ; 96, (6, 3, 6) ; 97, (6, 4, 3) ; 98, (6, 4, 4) ; 99, (6, 4, 5) ; 100, (6, 4, 6); 101, (6, 5, 2); 102, (6, 5, 3); 103, (6, 5, 4); 104, (6, 5, 5); 105, (6, 5, 6); 106, (6, 6, 1); 107, (6, 6, 2); 108, (6, 6, 3); 109, (6, 6, 4); 110, (6, 6, 5); 111, (6, 6, 6);
Получается согласно классической схеме вероятностей, вероятность выподания треугольника составляет 111/216=0.51388889=51.3 %
Решение №2
Сколько способов бросить сразу три кубика? (Сочетания с повторениями). Эксперимент может быть составлен так. Положили три куба в стакан. Хорошенечко перемешали и поставили стакан дном вверх.
Для определённости мысленно раскрасим эти кубики в разные цвета: белый, синий, красный. Они же физически различимы.
В этом случае множество элементарных исходов эксперимента состоит из 56 исходов. Вот они все перечислены.
1, (1, 1, 1) ; 2, (1, 1, 2) ; 3, (1, 1, 3) ; 4, (1, 1, 4) ; 5, (1, 1, 5) ; 6, (1, 1, 6) ; 7, (1, 2, 2) ; 8, (1, 2, 3) ; 9, (1, 2, 4) ; 10, (1, 2, 5) ; 11, (1, 2, 6) ; 12, (1, 3, 3) ; 13, (1, 3, 4) ; 14, (1, 3, 5) ; 15, (1, 3, 6) ; 16, (1, 4, 4) ; 17, (1, 4, 5) ; 18, (1, 4, 6) ; 19, (1, 5, 5) ; 20, (1, 5, 6) ; 21, (1, 6, 6) ; 22, (2, 2, 2) ; 23, (2, 2, 3) ; 24, (2, 2, 4) ; 25, (2, 2, 5) ; 26, (2, 2, 6) ; 27, (2, 3, 3) ; 28, (2, 3, 4) ; 29, (2, 3, 5) ; 30, (2, 3, 6) ; 31, (2, 4, 4) ; 32, (2, 4, 5) ; 33, (2, 4, 6) ; 34, (2, 5, 5) ; 35, (2, 5, 6) ; 36, (2, 6, 6) ; 37, (3, 3, 3) ; 38, (3, 3, 4) ; 39, (3, 3, 5) ; 40, (3, 3, 6) ; 41, (3, 4, 4) ; 42, (3, 4, 5) ; 43, (3, 4, 6) ; 44, (3, 5, 5) ; 45, (3, 5, 6) ; 46, (3, 6, 6) ; 47, (4, 4, 4) ; 48, (4, 4, 5) ; 49, (4, 4, 6) ; 50, (4, 5, 5) ; 51, (4, 5, 6) ; 52, (4, 6, 6) ; 53, (5, 5, 5) ; 54, (5, 5, 6) ; 55, (5, 6, 6) ; 56, (6, 6, 6) ;
Тут внимание, все эти исходы не равновероятны! Вот вам яркий пример. Исход (1,1,2) может выпасть тремя способами, а исход (1,2,3) может выпасть 6ю способами. Тот же выпад 1,2,2 может сформироваться тремя способами.
Из множества только 34 комплекта чисел (исходов эксперимента) образуют треугольники. Вот они перечислены.
1, (1, 1, 1) 2, (1, 2, 2) 3, (1, 3, 3) 4, (1, 4, 4) 5, (1, 5, 5) 6, (1, 6, 6) 7, (2, 2, 2) 8, (2, 2, 3) 9, (2, 3, 3) 10, (2, 3, 4) 11, (2, 4, 4) 12, (2, 4, 5) 13, (2, 5, 5) 14, (2, 5, 6) 15, (2, 6, 6) 16, (3, 3, 3) 17, (3, 3, 4) 18, (3, 3, 5) 19, (3, 4, 4) 20, (3, 4, 5) 21, (3, 4, 6) 22, (3, 5, 5) 23, (3, 5, 6) 24, (3, 6, 6) 25, (4, 4, 4) 26, (4, 4, 5) 27, (4, 4, 6) 28, (4, 5, 5) 29, (4, 5, 6) 30, (4, 6, 6) 31, (5, 5, 5) 32, (5, 5, 6) 33, (5, 6, 6) 34, (6, 6, 6)
Вот более наглядный список элементарных исходов, исходы образующие треугольники их вероятности.
+----+---------+-----+-------+-----+
|num | comb | cnt | prob | tri |
+----+---------+-----+-------+-----+
| 1 | 1, 1, 1 | 1 | 0.005 | 1 |
| 2 | 1, 1, 2 | 3 | 0.014 | 0 |
| 3 | 1, 1, 3 | 3 | 0.014 | 0 |
| 4 | 1, 1, 4 | 3 | 0.014 | 0 |
| 5 | 1, 1, 5 | 3 | 0.014 | 0 |
| 6 | 1, 1, 6 | 3 | 0.014 | 0 |
| 7 | 1, 2, 2 | 3 | 0.014 | 1 |
| 8 | 1, 2, 3 | 6 | 0.028 | 0 |
| 9 | 1, 2, 4 | 6 | 0.028 | 0 |
| 10 | 1, 2, 5 | 6 | 0.028 | 0 |
| 11 | 1, 2, 6 | 6 | 0.028 | 0 |
| 12 | 1, 3, 3 | 3 | 0.014 | 1 |
| 13 | 1, 3, 4 | 6 | 0.028 | 0 |
| 14 | 1, 3, 5 | 6 | 0.028 | 0 |
| 15 | 1, 3, 6 | 6 | 0.028 | 0 |
| 16 | 1, 4, 4 | 3 | 0.014 | 1 |
| 17 | 1, 4, 5 | 6 | 0.028 | 0 |
| 18 | 1, 4, 6 | 6 | 0.028 | 0 |
| 19 | 1, 5, 5 | 3 | 0.014 | 1 |
| 20 | 1, 5, 6 | 6 | 0.028 | 0 |
| 21 | 1, 6, 6 | 3 | 0.014 | 1 |
| 22 | 2, 2, 2 | 1 | 0.005 | 1 |
| 23 | 2, 2, 3 | 3 | 0.014 | 1 |
| 24 | 2, 2, 4 | 3 | 0.014 | 0 |
| 25 | 2, 2, 5 | 3 | 0.014 | 0 |
| 26 | 2, 2, 6 | 3 | 0.014 | 0 |
| 27 | 2, 3, 3 | 3 | 0.014 | 1 |
| 28 | 2, 3, 4 | 6 | 0.028 | 1 |
| 29 | 2, 3, 5 | 6 | 0.028 | 0 |
| 30 | 2, 3, 6 | 6 | 0.028 | 0 |
| 31 | 2, 4, 4 | 3 | 0.014 | 1 |
| 32 | 2, 4, 5 | 6 | 0.028 | 1 |
| 33 | 2, 4, 6 | 6 | 0.028 | 0 |
| 34 | 2, 5, 5 | 3 | 0.014 | 1 |
| 35 | 2, 5, 6 | 6 | 0.028 | 1 |
| 36 | 2, 6, 6 | 3 | 0.014 | 1 |
| 37 | 3, 3, 3 | 1 | 0.005 | 1 |
| 38 | 3, 3, 4 | 3 | 0.014 | 1 |
| 39 | 3, 3, 5 | 3 | 0.014 | 1 |
| 40 | 3, 3, 6 | 3 | 0.014 | 0 |
| 41 | 3, 4, 4 | 3 | 0.014 | 1 |
| 42 | 3, 4, 5 | 6 | 0.028 | 1 |
| 43 | 3, 4, 6 | 6 | 0.028 | 1 |
| 44 | 3, 5, 5 | 3 | 0.014 | 1 |
| 45 | 3, 5, 6 | 6 | 0.028 | 1 |
| 46 | 3, 6, 6 | 3 | 0.014 | 1 |
| 47 | 4, 4, 4 | 1 | 0.005 | 1 |
| 48 | 4, 4, 5 | 3 | 0.014 | 1 |
| 49 | 4, 4, 6 | 3 | 0.014 | 1 |
| 50 | 4, 5, 5 | 3 | 0.014 | 1 |
| 51 | 4, 5, 6 | 6 | 0.028 | 1 |
| 52 | 4, 6, 6 | 3 | 0.014 | 1 |
| 53 | 5, 5, 5 | 1 | 0.005 | 1 |
| 54 | 5, 5, 6 | 3 | 0.014 | 1 |
| 55 | 5, 6, 6 | 3 | 0.014 | 1 |
| 56 | 6, 6, 6 | 1 | 0.005 | 1 |
+----+---------+-----+-------+-----+
triangle cnt 34, Total results cnt 56, probability of triangle: 0.51388889Вероятность выпасть треугольнику вовсе не равна 34/56= 0.607= 60.7% как может показаться сначала. Как раз потому, что исходы имеют разную вероятность. Надо суммировать вероятности благоприятных исходов в отдельности. Тогда получится всё тот же 0.51388889= 51,3%
Моделирование эксперимента на PC.
Эксперимент очень просто промоделировать на PC. Вот код на Си
bool probability_triangle_simulation1(uint32_t number_of_exp){
bool res = false;
uint8_t side[3]={0};
uint32_t success=0;
LOG_INFO(SYS, "Try %u",number_of_exp);
uint32_t i;
for(i=0;i<number_of_exp;i++){
res = array_u8_rand(side,sizeof(side),1,6);
res=is_triangle( (double)side[0],(double)side[1],(double)side[2]);
if(res){
success++;
res = true;
}
}
double probability = ((double )success)/((double )number_of_exp);
LOG_INFO(SYS, "success %u, Total %u, probability: %f",success,number_of_exp,probability);
if(success){
res = true;
}else{
res = false;
}
return res;
}Вот результат
Вывод
Значение ответа не зависит от того как бросать. Вероятность выпадения треугольника всегда будет равна 51.38 %
Links
https://studfile.net/preview/9483706/page:10/
https://docs.google.com/spreadsheets/d/16_ZNfThw6e6atiRgsSnrsrJETntaaiEfcJlrYV-2M-o/edit#gid=0
https://docs.google.com/spreadsheets/d/1YLTWY24sbbrIfCIkChipCYn1BKBQqYCAerN3cpWuBHQ/edit#gid=282128841
Вот тут неправильное решение https://sous-otvet.net/vopros/44889171.html
