Fair game

и задачки для интервью.
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Fair game

Post by venco »

Ваш приятель предлагает сыграть в такую игру.
Вы оба ставите на кон по рублю. Затем вы выбираете себе последовательность из трёх исходов броска монеты, например, орёл-орёл-решка. Затем приятель тоже выбирает себе какую-нибудь другую последовательность из 3 исходов.
После этого вы бросаете одну монету пока три последних броска не совпадут с вашим или приятельским вариантом. Чей вариант выпал, тот и забирает деньги.
Стоит ли соглашаться на такую игру?
User avatar
KP580BE51
Уже с Приветом
Posts: 15007
Joined: 14 Jun 2005 11:50
Location: Ukraine

Re: Fair game

Post by KP580BE51 »

venco wrote:Стоит ли соглашаться на такую игру?

Да. Если делать нефиг.
Prist
Уже с Приветом
Posts: 280
Joined: 06 Apr 2004 21:25

Post by Prist »

Приятель тогда может выбрать серию, заканчивающуюся на -орёл-орёл. И в половине случаев выпадания в последовательности двух орлов для него это будет уже выигрыш и конец игры, а в другой половине случаев ваши шансы только 50-50. Я бы не стал так играть.
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Вы тоже можете выбрать любую комбинацию...
PavelM
Уже с Приветом
Posts: 13316
Joined: 13 Jun 1999 09:01
Location: Yekaterinburg -> Montreal

Post by PavelM »

поскольку выбор не скрывается, второй игрок имеет преимущество как уже сказали выше
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Хорошо, тогда со стороны приятеля, что ему надо выбирать, и с какой вероятностью он при этом выиграет?
rGlory
Уже с Приветом
Posts: 5102
Joined: 11 Aug 2004 02:49

Post by rGlory »

Чем это отличается от игры с одним броском монеты? Длительностью игры? Те же 50/50 Или я не понял условие, или это какой-то розыгрыш?
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Никакого розыгрыша. Обычная задача на вероятности с не совсем очевидным результатом.
User avatar
Quintanar
Уже с Приветом
Posts: 1609
Joined: 03 Feb 2004 11:19
Location: Moscow

Post by Quintanar »

Так ответ зависит от выбора первого игрока. В части случаев можно выбрать себе последовательность так, что вероятность выигрыша будет 7/8 (при РРР выбрать ОРР, например), в части 3/4 (при РРО выбрать ОРР), и в остальных - 2/3 (при ОРР выбрать ООР).
Это можно вычислить посмотрев на граф переходов между состояниями. Поскольку нас интересуют только два предыдущих хода, то состояний 4 - РР, РО, ОР, ОО. В каждом из них мы первоначально оказываемся с вероятностью 1/4. В другое переходим с вероятностью 1/2. Для случая РРР мы видим, что можем легко изолировать вражеское состояние оборвав ведущий в него путь, поэтому вероятность выигрыша у него всего 1/8. РРО тоже можно изолировать, но там нет исходящих путей, поэтому вероятность у противника выше в два раза - 1/4. Другие случаи сложнее, там надо высчитывать вероятности для нескольких возможных вариантов. Но про большинство из них сразу можно сказать, что они невыгодны.
Ya cayo el telon de acero y derribamos el muro de Berlin
y ahora todos juntos como hermanos vamos de la mano a comer a un Burger King
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Поздравляю всех с правильным и полным решением.
Надеюсь те, кто думал, что эта игра эквивалентна броску одной монеты, всё поняли.
:wink:
rGlory
Уже с Приветом
Posts: 5102
Joined: 11 Aug 2004 02:49

Post by rGlory »

venco wrote:Поздравляю всех с правильным и полным решением.
Надеюсь те, кто думал, что эта игра эквивалентна броску одной монеты, всё поняли.
:wink:

Я понял насчет PPP. А если я выберу РОР, то я проиграю?
Last edited by rGlory on 08 Sep 2006 17:00, edited 1 time in total.
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Это самый простой вариант.
Если вы выбрали РРР, а приятель - ОРР, то вы выиграете только если сразу выпадет РРР. Иначе, перед самой первой последовательностью РРР будет О, т.е. ОРР выпадет раньше. В результате вероятность вашего выигрыша - 1/8.
Аналогично если вы выберете ООО, а приятель - РОО.
Для других комбинаций чуть сложнее, но приятель всегда в выигрыше.
Наилучший для вас выбор - ОРО, ОРР, РОО, РОР. При этом приятель будет выигрывать с вероятностью 2/3.
rGlory
Уже с Приветом
Posts: 5102
Joined: 11 Aug 2004 02:49

Post by rGlory »

Что выберет приятель, если я выберу РОР?
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

РОР -> РРО
User avatar
Flash-04
Уже с Приветом
Posts: 63377
Joined: 03 Nov 2004 05:31
Location: RU -> Toronto, ON

Post by Flash-04 »

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

venco, для полного решения нужно построить таблицы комбинаций "я - игрок" и просчитать для каждой из пары вероятности (чте мне делать откровенно лень :() но разве здесь не должно быть симметрии? т.е. если есть комбинация невыгодная для вас, при выборе ее приятелем, она станет невыгодной для него?
rGlory
Уже с Приветом
Posts: 5102
Joined: 11 Aug 2004 02:49

Post by rGlory »

Понятно, век живи, век учись :great:
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Flash-04 wrote:т.е. если есть комбинация невыгодная для вас, при выборе ее приятелем, она станет невыгодной для него?


В том то и дело, что симметрии нет.
Вот все варианты, ваш выбор, выбор приятеля, и вероятность его выигрыша:

Code: Select all

ООО РОО 7/8
ООР РОО 3/4
ОРО ООР 2/3
ОРР ООР 2/3
РОО РРО 2/3
РОР РРО 2/3
РРО ОРР 3/4
РРР ОРР 7/8
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Можно заметить, что есть цикл, в котором каждая следующая комбинация побеждает предыдущую:

ООР -> РОО -> РРО -> ОРР -> ООР
rGlory
Уже с Приветом
Posts: 5102
Joined: 11 Aug 2004 02:49

Post by rGlory »

Насколько я понял можно сформулировать по другому - в любую двухбуквенную комбинацию есть два перехода. Одна из комбинаций, имеющая переход в данную, перехода из нее не имеет. Ее и нужно выбирать, а сам переход это третья буква.

То есть если первый выбрал РОР, это РО с переходом Р. В РО можно попасть из двух состояний: РР с переходом О и ОР с переходом О. ОР сама зависит от РО, поэтому выбираем РР->О
rGlory
Уже с Приветом
Posts: 5102
Joined: 11 Aug 2004 02:49

Post by rGlory »

Я тут програмку накидал для проверки, на слово я все равно не поверил :wink:

Code: Select all

#include <iostream>
#include <deque>


int main()
{
   const int tries = 100000;

   std::deque<bool> p1( 3 ), p2( 3 );

   p1[0] = true; p1[ 1 ] = true; p1[ 2 ] = false;
   p2[0] = true; p2[ 1 ] = true; p2[ 2 ] = true;

   srandom( time(0) );
   int win1 = 0, win2 = 0;
   for( int i = 0; i < tries; ++i ) {

      std::deque<bool> shoot;
      while( true ) {
         shoot.push_back( random() % 2 );
         if( shoot.size() < 3 ) continue;

         if( p1 == shoot ) {
            win1++;
            break;
         }

         if( p2 == shoot ) {
            win2++;
            break;
         }

         shoot.pop_front();
      }
   }
   std::cout << "p1 wins: " << win1 << " p2 wins: " << win2 << std::endl;
}
User avatar
Flash-04
Уже с Приветом
Posts: 63377
Joined: 03 Nov 2004 05:31
Location: RU -> Toronto, ON

Post by Flash-04 »

venco wrote:В том то и дело, что симметрии нет.

еще раз посмотрел условие, приятель выбирает комбинацию после, т.е. зная что у вас. Тогда конечно симметрии нет.
Более того, можно тогда не анализировать игру, и исходя из предположения что есть неравноправные комбинации, сразу сделать вывод, что приятель как минимум будет иметь шансы не мешьше ваших.
User avatar
AndreyT
Уже с Приветом
Posts: 3009
Joined: 14 Apr 2004 01:11
Location: SFBA (было: Минск, Беларусь)

Post by AndreyT »

Flash-04 wrote:
venco wrote:В том то и дело, что симметрии нет.

еще раз посмотрел условие, приятель выбирает комбинацию после, т.е. зная что у вас. Тогда конечно симметрии нет.
Более того, можно тогда не анализировать игру, и исходя из предположения что есть неравноправные комбинации, сразу сделать вывод, что приятель как минимум будет иметь шансы не мешьше ваших.


Откуда можно сделать такой вывод, не проводя анализа игры? Без анализа игры, как можно быть уверенным, что не существует строго выигрышной комбинации, т.е. комбинации, которая "побеждает" любую другую с точки зрения вероятности? Тогда, если приятель не имеет возможности отказаться от участия в игре после вашего выбора, его шансы не обязательно не меньше ваших.
Best regards,
Андрей
User avatar
Flash-04
Уже с Приветом
Posts: 63377
Joined: 03 Nov 2004 05:31
Location: RU -> Toronto, ON

Post by Flash-04 »

AndreyT wrote:Откуда можно сделать такой вывод, не проводя анализа игры?

достаточно показать что есть хотя бы одна такая пара комбинаций, когда ваш приятель получает преимущество. дальнейший анализ проводить не нужно.
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Не достаточно.
Надо показать, что для любого вашего выбора у приятеля найдётся лучший ответ.
User avatar
vm__
Уже с Приветом
Posts: 11756
Joined: 10 Feb 2005 16:08
Location: CMH

Post by vm__ »

venco wrote: Надо показать, что для любого вашего выбора у приятеля найдётся лучший ответ.

"Если друг оказался вдруг,
И не друг, и не враг - а так...."
Нафик такого приятеля! Он еще в МММ сагитирует... :mrgreen: :mrgreen: :mrgreen:

Return to “Головоломки”