На внутренней стороне конфетных фантиков напечатаны добрые пожелания. Сколько в среднем конфет понадобится, чтобы собрать все s разных пожеланий? задан 12 Мар '20 21:27 qoiro |
Это известная задача, она в каком-то виде на форуме уже была. Для начала лемма: если событие происходит с вероятностью p > 0, то для его наступления в среднем требуется 1/p испытаний. Это легко доказывается, например, с помощью рядов. Рассмотрим теперь число испытаний, которое нужно для получения s конфет. Представим эту случайную величину в виде суммы X(1)+X(2)+...+X(s), где X(1)=1, и X(i+1) есть число испытаний до получения (i+1)-го нового пожелания после получения i-го (при i < s). Матожидание X(i) равно s/(s-i), так как вероятность успеха составляет (s-i)/s: на рассматриваемом шаге i пожеланий уже были, и s-i являются новыми. Итого матожидание суммы как суммы матожиданий равно s/s+s/(s-1)+...+s/2+s/1=sH(s), где H(s)=1+1/2+...+1/s есть s-е гармоническое число. Оно растёт примерно как ln s. Скажем, при s=36 (колода карт) требуется примерно 150 испытаний. отвечен 12 Мар '20 22:01 falcao |