朝日新聞2006年4月28日のパズル横丁問題

問題

赤帽子が3つ，白帽子が2つある。A,B,C,Dの4名に自分の帽子の色が判らないようにかぶせる。残った1つの帽子の色は判らないようにする。

4人は自分以外の帽子が見えるものとする。4人に同時に自分の帽子の色が判るか質問したとき，1名が判る，残る3名が判らないと答えた。

4人の中に一人嘘つきがいるとすると嘘をついた人の帽子の色は何色か?

解答への道(ヒント)

嘘つき問題は苦手なんだよなー。それでも今回は簡単なほう。

帽子は全部で●●●○○の5つ。自分の帽子の色が判るか判らないかは他の3人の帽子の組み合わせを考えると以下の3通りしかない。

問題には4人同時に質問したとある。同時にしないと他人の答えから類推できてしまうのでこの前提が必要になる。

しかし，4人同時に質問しても答えが同時とは書いてないぞ。なーんて突っ込みは野暮だな。

判る人の数と，判らない人の数の組み合わせは以下のようになる。

全ての場合を調べて，嘘をついた可能性のある人の帽子の色を調べる。

プログラムは大体以下のようになる。

全ての場合 {
  帽子を配る
  A,B,C,Dの4名の帽子の色が判るか判らないか判断する。
  判る1名,判らない3名になる可能性を調べ,その時嘘をついた人の帽子の色を調べる。
}
嘘つきの帽子の色が同じ色なら答えに。同じ色にならなければ答え無し。

もう少しコーディングに近いレベルで書くと以下のようになる。

for( int a=0; a< 2; a++) {
  for( int b=0; b< 2; b++) {
    for( int c=0; c< 2; c++) {
      for( int d=0; d< 2; d++) {
        int n = a+b+c+d;    // 赤色帽子の数
        if( n < 1 || n >= 4) continue; // 配られた中に赤は必ず1つあり，4つは無い
        int A,B,C,D;
        A = check( a,b,c,d); // 自分の帽子の色が判る?
        B = check( b,a,c,d);
        C = check( c,a,b,d);
        D = check( d,a,b,c);
        int m = A+B+C+D;    // 帽子の色が判った人の数
        …
      }
    }
  }
}

結果，帽子の色が出力されました。

UEFAチャンピオンズリーグは決勝がアーセナルとバルセロナになった。私にとって近年にないうれしい組み合わせだ。

解速度

即