?

Log in

No account? Create an account
ushastyi
ushastyi
.............. .... ..........

Links

Октябрь 2019
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31

ushastyi [userpic]
SQL для решения задачек на вероятности

Месяц назад жена с детьми ездила в математический лагерь Жени Кац (janemouse). Особенность матлагеря была в том, что развлекали и учили не только детей, но и их родителей. Каждый день им что-то рассказывали и давали задачки желающим немного поскрипеть мозгами. Какие-то интересные, какие-то не очень. Жена решала все, и едва ли не лучше всех. Физтех. Но я из дома на них тоже посматривал. Уже давно я пользуюсь SQL, если нужно что-то несложное посчитать, и тут попалась задачка на вероятности, которую можно было очень просто решить SQL запросом. Вот такая:

В темном погребе стоит 15 банок с вареньем, 5 с малиновым и 10 с яблочным. Карлсон таскает варенье из погреба, беря каждый раз по одной банке наугад. Его цель -- утащить все малиновое варенье. Какова вероятность того, что когда Карлсон утащит последнюю банку малинового варенья, в погребе не останется никакого варенья вообще?

Задача кажется простой, и инстинктивный ответ 1/3 оказывается правильным. Но если его попытаться обосновать, то начинаются некоторые сложности. Поэтому, чтобы отсечь сомнения, я сделал так.


Закодируем последовательность добывания банок Карлсоном. Так как типов варенья у нас всего два, то можно использовать битовое кодирование: 1 -- малиновое, 0 -- яблочное. Первый бит -- первая утащенная банка, второй бит -- вторая, и т.д. 15 битов -- это 2^15-1 = 32767. Нашим вероятностным пространством будут битовые последовательности, содержащие ровно 5 единиц. Например, 000000000011111. А подмножеством искомых исходов такие числа, где 15й бит -- малиновая банка, то есть единица. Например, 100000000001111. Чтобы не использовать битовые операции можно просто взять числа больше или равные 2^14 = 16384. Получается вот такой коротенький запрос:

SELECT 
    count() AS all_five_bits, 
    countIf(number >= 16384) AS last_bit_set, 
    last_bit_set / all_five_bits AS prob
FROM numbers(32767)
WHERE length(bitmaskToArray(number)) = 5

┌─all_five_bits─┬─last_bit_set─┬───────────────prob─┐
│          3003 │         1001 │ 0.3333333333333333 │
└───────────────┴──────────────┴────────────────────┘



Интуиция не подвела.

Comments

Не думаю, что задачи по математике съедобны.