朝日新聞2005年7月29日のパズル横丁問題

問題

カレー屋A,B,C,Dがある。匂いを嗅いだだけで味が判るものとする。

カレー屋を順に訪れ,匂いを嗅いで今まで嗅いだ匂いより美味しければカレーを食べ,そうでなければ次の店を訪れる。

但し後戻りできないものとする。

N店までは匂いを嗅ぐだけとしたとき,一番美味しいカレーを食べることが出来る確率が一番高くなるのはNが0〜3の何れか?

解答への道(ヒント)

何処かで見たような問題。カレー屋でなく,確かお見合いの話だった。

宝くじは当たらない,お見合いは早めに相手を決めろ!,っていうのは確率の勉強をしていると良く聞く話。それでも宝くじを買う人は買うし,お見合いを30回以上やっている人もいる。

確率の問題は昔から苦手だ。大学時代スクラッチカードの当たる確率を求めたらみんなバラバラの答えになったのには笑った。学科が学科だけに本当は笑えない話なんだけどね。

確率の場合,場合の数を求めれば正解が出てくるのだが,場合の数を求めるのに苦労する。

この問題の場合も同じ味の店が存在するかどうかで場合の数が変わってしまう。

結果的に正解は同じになるんだけど,どっちが正しいのかよく判らない。

同じ味の店が存在する場合,全ての場合の数は4x4x4x4=256通り。

味は全て順位付けできるものとした場合4!=4x3x2x1=24通り。

同じ味の店が存在すると仮定してプログラムしたら以下のようになる。日本語のコメントが無いと何がなんだか判らない。

void eat( int N)
{
  int cnt = 0;                  // 全ての場合の数
  int hit = 0;                  // 一番おいしいカレーを食べた場合の数
  int aji[10];                    // A,B,C,Dのお店の味の評価。
  //--------------------------------------------------------------------
  // A,B,C,Dのお店の味の全ての可能性を考える。
  // 異なる店が同じ味になる可能性も考える。
  //--------------------------------------------------------------------
  for( int a=1; a<= 4; a++) {
    for( int b=1; b<= 4; b++) {
      for( int c=1; c<= 4; c++) {
        for( int d=1; d<= 4; d++) {
          aji[0] = a;
          aji[1] = b;
          aji[2] = c;
          aji[3] = d;
#if 0 // 同じ味の店が存在しない場合ここを有効にする。
          { 
            int dup[5] = {0};
            if( dup[a] > 0) continue;
            dup[a]++;
            if( dup[b] > 0) continue;
            dup[b]++;
            if( dup[c] > 0) continue;
            dup[c]++;
            if( dup[d] > 0) continue;
            dup[d]++;
          }
#endif
          ++cnt;
          //------------------------------------------------------------
          // 一番おいしい味を求める。
          //------------------------------------------------------------
          int ajimax = 0;
          for( int i=0; i< 4; i++) {
            if( aji[i] > ajimax) ajimax = aji[i];
          }
          //------------------------------------------------------------
          // Nまでの店の前を通り過ぎ一番良い味(nmax)を記憶する。
          //------------------------------------------------------------
          int nmax = 0;
          for( i=0; i< N; i++) {
            if( aji[i] > nmax) nmax = aji[i];
          }
          //------------------------------------------------------------
          // 残りの店を調べ,それ以降に以前出現した味よりも良い味があればそれを食べる。
          // 良い味が出ない場合問題。
          //------------------------------------------------------------
          for( ; i< 4; i++) {
            if( aji[i] > nmax) {
              //--------------------------------------------------------
              // 今までよりおいしいカレーが出現した。
              //--------------------------------------------------------
              if( aji[i] == ajimax) hit++;
              break;
            }
          }
          if( i == 4) {
            //----------------------------------------------------------
            // 後戻りできないので渋々最後の店でカレーを食べた。
            //----------------------------------------------------------
            if( aji[3] == ajimax) {
              //--------------------------------------------------------
              // でも今までより美味しくは無いが,結果的にこれが一番おいしいカレーだった。
              //--------------------------------------------------------
              hit++;
            }
          }
        }
      }
    }
  }
  ps( "N:%d, cnt:%d, hit:%d\n", N, cnt, hit);
}

これをN=0〜3で呼び出す。最大のhitを出力した時のNが求める答えになる。

解速度