2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Нестандартное решение олимпиадной задачи по теорверу
Сообщение17.09.2008, 20:05 
Аватара пользователя


17/05/08
358
Анк-Морпорк
Задача.
Какова вероятность того, что при бросании монеты серия из трёх орлов подряд выпадет раньше, чем серия из двух решек подряд?

Эта задача была на Всеукраинской студенческой олимпиаде по математике в 2005 году в Севастополе. Оценивалась она в 12 баллов (всего за правильное решение всех 10 задач можно было получить, по-моему, 60 баллов).

Решение.
Будем обозначать выпадение орла как 0, а решку – как 1. Найдём сначала, сколько существует последовательностей из 0 и 1 длины n таких, которые заканчиваются ровно тремя нулями и не содержат других троек нулей и пар единиц. Обозначим это количество как Х(n), а выделенное жирным условие как Условие 1. Оно нам потом ещё пригодится.

Понятно, что для n=1 или 2 таких последовательностей не существует. Для n=3 возможна только единственная: 000. Далее цепочки длины n+1 можно получать из цепочек длины n, подставляя в качестве первого символа 0 или 1, с тем, чтобы продолжало выполняться Условие 1. Первые несколько шагов представлены в таблице.

\begin{tabular}{|c|c|c|}
\hline n& X(n) & Возможные цепочки \\
\hline 1& 0 & - \\
\hline 2& 0 & - \\
\hline 3& 1 & 000 \\
\hline 4& 1 & 1000 \\
\hline 5& 1 & 01000 \\
\hline 6& 2 & 101000; 001000 \\
\hline 7& 2 & 0101000; 1001000 \\
\hline 8& 3 & 00101000; 10101000; 01001000 \\
\hline 9& 4 & 100101000; 010101000; 001001000; 101001000 \\
\hline
\end{tabular}
Более наглядно процесс образования цепочек большей длины показывает вот такое дерево:

Изображение

Поскольку всего цепочек из 0 и 1 длины n - $2^n$, то вероятность того, что три орла выпадут раньше двух решек после ровно n бросков, составляет $ \frac{X(n)}{2^n}$. Таким образом, для вычисления искомой вероятности требуется найти сумму $ \frac{X(1)}{2^1}+  \frac{X(2)}{ 2^2}+  \frac{X(3)}{ 2^3}+  \frac{X(4)}{ 2^4}+…$

Для этого сначала нужно найти общую формулу X(n). Введём 3 вспомогательных величины.
A(n) – количество цепочек из 0 и 1 длины n, которые удовлетворяют Условию 1 и начинаются с 00
B(n) – количество цепочек из 0 и 1 длины n, которые удовлетворяют Условию 1 и начинаются с 01
C(n) – количество цепочек из 0 и 1 длины n, которые удовлетворяют Условию 1 и начинаются с 10

При образовании цепочки длины n+1 перед каждой цепочкой, начинающейся с 00 для соблюдения Условия 1 можно ставить только 1, перед цепочками на 10 – только 0, а перед цепочками на 01 можно ставить и 0 и 1.

Получаем:
A(n+1) = B(n)
B(n+1) = C(n)
C(n+1) = A(n)+B(n)

Далее
A(n+2) = B(n+1) = C(n)
B(n+2) = C(n+1) = A(n)+B(n)
C(n+2) = A(n+1)+B(n+1) = B(n)+ C(n)

И ещё один шаг:
A(n+3) = B(n+2) = A(n)+B(n)
B(n+3) = C(n+2) = B(n)+ C(n)
C(n+3) = A(n+2)+B(n+2) = A(n)+B(n)+ C(n)

Тогда
X(n+3) = A(n+3)+B(n+3)+C(n+3) = 2A(n)+3B(n)+2C(n) = X(n+1)+X(n)
Мы получили для X(n) рекуррентную формулу.

К сожалению, я тогда не умел решать разностные уравнения, но интуитивно чувствовал, что, по аналогии с последовательностью Фибоначчи, X(n) можно в общем виде представить в виде суммы нескольких геометрических прогрессий, основанием одной из которых должен быть корень уравнения $\lambda^3=\lambda+1$, о чём и написал в решении. Тогда и сумма $\sum \limits_{n=1}^{\infty}{\frac{X(n)}{2^n}}$ разложится в несколько геометрических прогрессий, которые затем легко свернутся.

За решение тогда поставили то ли 1 балл, то ли вообще 0. Я, разумеется, пошёл аппелировать. На аппеляции я в первый раз встретился с dm’ом. Он разобрался в моём решении, сказал, что ход моих мыслей верный и рассказал, как нужно решать разностные уравнения. Другое дело, что дальнейшее решение по предполагаемому мной пути заняло бы время, намного большее уже потраченного. Однако свои 6 баллов я получил и в итоге вышел на 2е место с разрывом с первым в 1 балл (если бы не ступил при решении детской 4-х балльной задачи – было б первое).

Вечером пришла идея, как найти искомую сумму ряда, не решая характеристического уравнения $\lambda^3=\lambda+1$, а зная только произведение, сумму и сумму попарных произведений его корней из теоремы Виета. После достаточно объёмных преобразований сумма находилась. Я показал записи Дмитрию Юрьевичу и мы тогда решили, что это была бы интересная тема для статьи про нестандартное решение задачи на теорию вероятности.

Однако дома я всё откладывал оформление на потом и тема как-то забылась. Ну а сейчас наконец-то собрался и решил описать своё решение. Тем более что, позже покрутив эту задачу, я понял, как можно ещё проще найти сумму ряда.

Итак, дано:
X(n+3) = X(n+1)+X(n)
Найти:
$\sum \limits_{n=1}^{\infty}{\frac{X(n)}{2^n}}$

Пусть
$S= \frac{X(3)}{2^3}+ \frac{X(4)}{ 2^4}+ \frac{X(5)}{2^5}+\frac{X(6)}{2^6}+\frac{X(7)}{2^7}+…$
(члены X(1) и X(2), равные 0, просто опустим)

Разделим сумму на 4
$\frac{S}{4}=\frac{X(3)}{2^5}+ \frac{X(4)}{ 2^6}+ \frac{X(5)}{2^7}+\frac{X(6)}{2^8}+\frac{X(7)}{2^9}+…$

А тепер разделим её на 8
$\frac{S}{8}=\frac{X(3)}{2^6}+ \frac{X(4)}{ 2^7}+ \frac{X(5)}{2^8}+\frac{X(6)}{2^9}+\frac{X(7)}{2^10}+…$

И сложим последние 2 величины:
$\frac{S}{4}+\frac{S}{8}=\frac{X(3)}{ 2^5}+ \frac{X(3)+X(4)}{2^6}+ \frac{X(4) +X(5)}{ 2^7}+ \frac{X(5) +X(6)}{2^8}+\frac{X(6) +X(7)}{2^9}+\frac{X(7) +X(8)}{2^{10}}+…=\frac{X(3)}{ 2^5}+ \frac{X(6)}{2^6}+ \frac{X(7)}{ 2^7}+ \frac{X(8)}{2^8}+\frac{X(9)}{2^9}+\frac{X(10)}{2^{10}}+…=\frac{X(3)}{ 2^5}+S-\frac{X(3)}{2^3}- \frac{X(4)}{ 2^4}- \frac{X(5)}{2^5}$

Подставив значения, решаем уравнение:
$\frac{S}{4}+\frac{S}{8}=\frac{1}{32}+S-\frac{1}{8}-\frac{1}{16}-\frac{1}{32}$
Откуда S=0.3

Следовательно, при бросании монеты с вероятностью 30% 3 орла подряд выпадут раньше двух решек подряд.

Вот так вот, через 3 с половиной года наконец-то выкладываю своё решение в виде статьи. У себя на http://intelmath.narod.ru думаю продолжить писать статьи на математические и околоматематические темы, идеи которых возникали давно, но всё откладывались в долгий ящик.

 Профиль  
                  
 
 
Сообщение18.09.2008, 10:25 
Заслуженный участник
Аватара пользователя


23/08/07
4780
Нов-ск
$P$ --- искомая вероятность (что $000$ встретится раньше, чем $11$)
$P_0$ --- искомая вероятность, если первым выпал $0$
$P_1$ --- искомая вероятность, если первым выпал $1$

$P=\frac{1}{2} \left(  \frac{1}{2} +\frac{1}{2}  P_1 \right)$
$P=\frac{1}{2}  P_0 +\frac{1}{2}  P_1$
$P_1=\frac{1}{2} P_0$

Откуда $P=\frac{3}{10}$

 Профиль  
                  
 
 
Сообщение18.09.2008, 14:33 
Заблокирован


16/03/06

932
TOTAL писал(а):
$P$ --- искомая вероятность (что $000$ встретится раньше, чем $11$)
$P_0$ --- искомая вероятность, если первым выпал $0$
$P_1$ --- искомая вероятность, если первым выпал $1$

$P=\frac{1}{2} \left(  \frac{1}{2} +\frac{1}{2}  P_1 \right)$
$P=\frac{1}{2}  P_0 +\frac{1}{2}  P_1$
$P_1=\frac{1}{2} P_0$

Откуда $P=\frac{3}{10}$

А почему $P_1=\frac{1}{2} P_0$ ? Ведь эти вероятности равны друг другу("выпал первым единственный О" или "выпала первой единственная 1" составляют полную группу событий).

Вероятность одной из заданных комбинаций выпасть первой, оказывается, зависит от количества выполненных бросков (то есть не постоянная).

Р1(ООО)=0 - _____________Р1(РР)=0 - при 1 броске
Р2(ООО)=0________.Р2(РР)=1/4=0,25 - при 2 бросках
Р3(ООО)=1/3=0,333..___.Р3(РР)=0,66...- при 3 бросках
Р4(ООО)=3/11=0,27...___Р4(РР)=0,73...- при 4 бросках
Р5(ООО)=7/24=0,29...___Р5(РР)=0,71...- при 5 бросках

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

 Профиль  
                  
 
 
Сообщение18.09.2008, 15:03 
Аватара пользователя


17/05/08
358
Анк-Морпорк
TOTAL
Красиво! По-моему, оригинальное решение, которое, конечно, короче моего было, и то длиннее.

Архипов
Архипов в сообщении #145141 писал(а):
А почему $P_1=\frac{1}{2}P_0$ ?


Если первый раз выпадает единица, то если и после этого выпадет единица, то событие вооще не наступит, а если же выпадет 0 (с вероятностью $\frac {1}{2}$), то вероятность превратится в $P_0$
Поэтому $P_1=\frac{1}{2}*0+\frac{1}{2}P_0$

Т.к. учитывается первое выпадение 000 или 11, то можно действительно считать, что броски прекращаются сразу после выпадения одной из этих последовательностей.

 Профиль  
                  
 
 Re:
Сообщение24.10.2014, 18:47 


15/06/13
27
TOTAL в сообщении #145112 писал(а):
$P$ --- искомая вероятность (что $000$ встретится раньше, чем $11$)
$P_0$ --- искомая вероятность, если первым выпал $0$
$P_1$ --- искомая вероятность, если первым выпал $1$

$P=\frac{1}{2} \left(  \frac{1}{2} +\frac{1}{2}  P_1 \right)$
$P=\frac{1}{2}  P_0 +\frac{1}{2}  P_1$
$P_1=\frac{1}{2} P_0$

Откуда $P=\frac{3}{10}$


Объясните, пожалуйста, как получаются 1-е и 3-е равенства

 Профиль  
                  
 
 Re: Нестандартное решение олимпиадной задачи по теорверу
Сообщение31.10.2014, 20:56 


15/06/13
27
Люди добрые, скажите как получается первая формула

 Профиль  
                  
 
 Re: Нестандартное решение олимпиадной задачи по теорверу
Сообщение31.10.2014, 23:16 
Супермодератор
Аватара пользователя


20/11/12
5729
 !  Gelhenec, замечание за искусственный подъем темы бессодержательным сообщением.

 Профиль  
                  
 
 Re: Нестандартное решение олимпиадной задачи по теорверу
Сообщение01.11.2014, 15:53 


19/03/09
124
Странно, численно P гдето 0.428.
Мож кто найдет ошибку:
Код:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int brand()
{
  return rand()&1;
}
void test()
{
  int n1=0, n2=0;
  srand(time(0));
  int ii = 33*1000*1000;
  for(int i=0;i<ii;i++)
  {
    int a1 = brand();
    int a2 = brand();
    int a3 = brand();
    int z;
    while(1)
    {
      if(a1==1 && a2==1) { z=1; break; }
      if(a1==0 && a2==0 && a3==0) { z=2; break; }
      a1 = a2;
      a2 = a3;
      a3 = brand();
    }
    if(z==1) n1++;
    if(z==2) n2++;
  }
  printf("%f\n",(double)n2/n1);
}
int main(int ac,char *av[])
{
  int nn = av[1] ? atoi(av[1]):10;
  for(int n=0;n<nn;n++) test();
  return 0;
}


0.428754
0.428650
0.428485
0.428363
0.428855
0.428594
0.428613
0.428539
0.428444
0.428675

 Профиль  
                  
 
 Re: Нестандартное решение олимпиадной задачи по теорверу
Сообщение01.11.2014, 17:44 


26/08/11
1876
Deggial в сообщении #924890 писал(а):
Странно, численно P гдето 0.428.
Мож кто найдет ошибку:

Почему печатаете $\dfrac{n_2}{n_1}$? Надо $\dfrac{n_2}{n_1+n_2}$ печатать - отношение числа успехов к общему числу испытаний
И поскольку в действительности $p_2=\dfrac{3}{10},p_1=\dfrac{7}{10}$ вот и получается у Вас $\dfrac{3}{7}\approx 0.4285$

 Профиль  
                  
 
 Re: Нестандартное решение олимпиадной задачи по теорверу
Сообщение01.11.2014, 21:00 
Заслуженный участник


27/06/08
3387
Волгоград
Gelhenec в сообщении #924844 писал(а):
Люди добрые, скажите как получается первая формула

Внешняя $\frac12$ - это вероятность того, что два 0 выпадут раньше, чем две 1.
После этого с вероятностью $\frac12$ выпадет третий 0 и с такой же вероятностью 1.

 Профиль  
                  
 
 Re: Нестандартное решение олимпиадной задачи по теорверу
Сообщение02.11.2014, 04:22 


19/03/09
124
Нашли bug, спс.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group