Не второе, первое, второе

[dimview]

Афанасий и Бонифаций режутся в азартную игру на щелбаны с такими правилами:

• Афанасий выбирает произвольную последователность из трёх выпадений монеты, например орёл-решка-решка, и сообщает её Бонифацию.
  
• Бонифаций выбирает любую другую последовательность из трёх выпадений, например решка-решка-орёл, и сообщает её Афанасию.
  
• Игроки кидают монету и записывают результаты до тех пор, пока не встретится одна из этих последовательностей. Чья последовательность реализовалась первой, тот и выиграл.
  

Честная ли это игра, то есть одинаковы ли шансы у Афанасия и Бонифация?

Это нечестная игра Пенни, в ней преимущество на стороне Бонифация. Если Афанасий выбирает свою последовательность случайно, шансы Бонифация выиграть 7:2. Оптимальная стратегия Афанасия — выбирать последовательность с разными значениями первого и второго выпадения, при этом шансы Бонифация снижаются до 2:1. Вот раскладка для всех возможных выборов Афанасия:

Афанасий	Бонифаций	Шансы Бонифация
TTT	HTT	7:1
HTT	HHT	2:1
THT	TTH	2:1
HHT	THH	3:1
TTH	HTT	3:1
HTH	HHT	2:1
THH	TTH	2:1
HHH	THH	7:1

Пропустившие лекции по теорверу могут проверить теоретические цифры монте-карлом:

// Monte-Carlo simulation of Penney's game
#include <iostream>
#include <random>

int main(void)
{
  unsigned games = 10000000;
  std::default_random_engine gen(42);
  std::uniform_int_distribution<unsigned long long> dist;
  std::cout << "a_seq\tb_seq\tb:a\n";
  for (unsigned a_seq = 0; a_seq < 8; a_seq++) { // Possible choices of player A
    unsigned b_seq = ((~a_seq & 2) >> 1)  // not-second
                   | (( a_seq & 1) << 1)  // first
                   | (( a_seq & 2) << 1); // second
    unsigned a_won = 0; // Number of times player A won
    unsigned b_won = 0; // Number of times player B won
    for (unsigned game = 0; game < games; game++) {
      unsigned long long x = dist(gen);
      for (unsigned flip = 0; flip < sizeof(x) * 8; flip++) {
        if ((x & 7) == a_seq) {
          a_won++;
          break;
        }
        if ((x & 7) == b_seq) {
          b_won++;
          break;
        }
        x >>= 1;
      }
    }
    std::cout << ((a_seq & 1) ? 'H' : 'T') 
              << ((a_seq & 2) ? 'H' : 'T')
              << ((a_seq & 4) ? 'H' : 'T') << "\t" 
              << ((b_seq & 1) ? 'H' : 'T')
              << ((b_seq & 2) ? 'H' : 'T')
              << ((b_seq & 4) ? 'H' : 'T') << "\t" 
              << (double)b_won / a_won << "\n";
  }
  return 0;
}

Мнемоника для Бонифация вынесена в заголовок. Если Афанасий выбрал последовательность (Первое, Второе, Третье), то Бонифацию нужно выбрать последовательность (Не-второе, Первое, Второе). В приведённом примере, где Афанасий выбрал (Первое=орёл, Второе=решка, Третье=решка), Бонифацию нужно выбирать (Не-второе=орёл, Первое=орёл, Второе=решка).