朝日新聞2005年10月21日のパズル横丁問題

問題

私は正直か嘘つきかのどちらかである。私が以下のように言ったとき,私が正直であるには,□に「ある」,「なし」のどちらを入れれば良いか。

私は「私は「私は「私は「私は「私は「私は嘘つきで□」と言ったことが□」と言ったことが□」と言ったことが□」と言ったことが□」と言ったことが□」と言ったことが□

但し,私が正直な場合正直なことだけを言い,嘘つきならあり得ないことしか言いません。

解答への道(ヒント)

(2005.11.4)新聞の解答欄を見ると正解者3名だって。私も見事に外れ。よって,以下の解説は間違いということになる。新聞の解答欄を見ても何が間違っていたのかよく判らない。

嘘つき問題は頭で考えるとややこしい。図形問題と逆である。

今回はプログラムを作っても答えが出ず延々と悩み続けた。試験に出題されたら時間配分を間違えて0点を取りそうな問題だ。

最初考えたことは以下のような表である。一番内側の発言について。

発言 私は正直 私は嘘つき
私は嘘つきである 発言は偽 発言は真
私は嘘つきでない 発言は真 発言は偽

それより外側の発言について。

発言 ○○の真偽 私は正直 私は嘘つき
私は○○と言ったことがある 発言は真 発言は偽
発言は偽 発言は真
私は○○と言ったことがない 発言は偽 発言は真
発言は真 発言は偽

そこで「ある」,「なし」を虱潰す以下のようなコーディングを考えた。

const int N6 = 6;               // 6回「ある」,「ない」を繰り返す
const int N = 1<<N6;            // 6回の「ある」,「ない」の組合せ

for( int i=0; i< N; i++) {  // ある,ないの組合せ,下位ビットからある(1),ない(0)を取り出す
  check( YES/*正直者が*/, YES/*「私は嘘つきで(ある)」*/, NO /*は(偽)*/, 0/*6回*/, i/*と言ったことが「ある(ON)/なし(OFF)」の組合せ*/);
  check( NO /*嘘つきが*/, YES/*「私は嘘つきで(ある)」*/, YES/*は(真)*/, 0/*6回*/, i/*と言ったことが「ある(ON)/なし(OFF)」の組合せ*/);
  check( YES/*正直者が*/, NO /*「私は嘘つきで(ない)」*/, YES/*は(真)*/, 0/*6回*/, i/*と言ったことが「ある(ON)/なし(OFF)」の組合せ*/);
  check( NO /*嘘つきが*/, NO /*「私は嘘つきで(ない)」*/, NO /*は(偽)*/, 0/*6回*/, i/*と言ったことが「ある(ON)/なし(OFF)」の組合せ*/);
}

check()関数は以下のようにした。

void check( YesNo man/*正直者(YES)/嘘つき(NO)*/,
            YesNo usotuki/*最初の「私は嘘つきで(ある/ない)*/,
            YesNo truefalse/*私は○○と言ったことが{ある|ない},○○の真偽*/,
            int cnt/*回数*/,
            int diffarunai/*正直者は○○が(真)なら「ある」と言い,偽なら「ない」と言う*/
                          /*嘘つきは○○が(真)なら「ない」と言い,偽なら「ある」と言う*/
            )
{
  if( cnt >= N6) {
    ps( "%sは「私は嘘つきで%s(%s)」と言ったことが",man?"正直者":"嘘つき", usotuki?"ある":"ない", logtf[0]?"真":"偽");
    for( int i=0; i< N6; i++) {
      ps( "⇒ ");
      ps( "%s", logarunai[i]?"ある":"ない");
    }
    ps( " ⇒この発言は %s である", truefalse?"真":"偽");
    if( man == truefalse) ps( "★");
    ps( "\n");
    return;
  }
  logarunai[cnt] = diffarunai&1;
  logtf[cnt]     = truefalse;

  if(  man &&  truefalse && ((diffarunai&1)==1)) check( man, usotuki, YES, cnt+1, diffarunai>>1); // (正直者)は「(真)を言ったことが(ある)」⇒真
  if(  man &&  truefalse && ((diffarunai&1)==0)) check( man, usotuki, NO , cnt+1, diffarunai>>1); // (正直者)は「(真)を言ったことが(ない)」⇒偽
  if(  man && !truefalse && ((diffarunai&1)==1)) check( man, usotuki, NO , cnt+1, diffarunai>>1); // (正直者)は「(偽)を言ったことが(ある)」⇒偽
  if(  man && !truefalse && ((diffarunai&1)==0)) check( man, usotuki, YES, cnt+1, diffarunai>>1); // (正直者)は「(偽)を言ったことが(ない)」⇒真

  if( !man &&  truefalse && ((diffarunai&1)==1)) check( man, usotuki, NO,  cnt+1, diffarunai>>1); // (嘘つき)は「(真)を言ったことが(ある)」⇒偽
  if( !man &&  truefalse && ((diffarunai&1)==0)) check( man, usotuki, YES, cnt+1, diffarunai>>1); // (嘘つき)は「(真)を言ったことが(ない)」⇒真
  if( !man && !truefalse && ((diffarunai&1)==1)) check( man, usotuki, YES, cnt+1, diffarunai>>1); // (嘘つき)は「(偽)を言ったことが(ある)」⇒真
  if( !man && !truefalse && ((diffarunai&1)==0)) check( man, usotuki, NO,  cnt+1, diffarunai>>1); // (嘘つき)は「(偽)を言ったことが(ない)」⇒偽
}

ものの見事に迷宮に入り込みました。上記プログラムを実行すると,以下のような出力を得る。

正直者は「私は嘘つきである(偽)」と言ったことが⇒ ない⇒ ない⇒ ない⇒ ない⇒ ない⇒ ない ⇒この発言は 偽 である
嘘つきは「私は嘘つきである(真)」と言ったことが⇒ ない⇒ ない⇒ ない⇒ ない⇒ ない⇒ ない ⇒この発言は 真 である
正直者は「私は嘘つきでない(真)」と言ったことが⇒ ない⇒ ない⇒ ない⇒ ない⇒ ない⇒ ない ⇒この発言は 真 である★
嘘つきは「私は嘘つきでない(偽)」と言ったことが⇒ ない⇒ ない⇒ ない⇒ ない⇒ ない⇒ ない ⇒この発言は 偽 である★
正直者は「私は嘘つきである(偽)」と言ったことが⇒ ある⇒ ない⇒ ない⇒ ない⇒ ない⇒ ない ⇒この発言は 真 である★
嘘つきは「私は嘘つきである(真)」と言ったことが⇒ ある⇒ ない⇒ ない⇒ ない⇒ ない⇒ ない ⇒この発言は 偽 である★
正直者は「私は嘘つきでない(真)」と言ったことが⇒ ある⇒ ない⇒ ない⇒ ない⇒ ない⇒ ない ⇒この発言は 偽 である
嘘つきは「私は嘘つきでない(偽)」と言ったことが⇒ ある⇒ ない⇒ ない⇒ ない⇒ ない⇒ ない ⇒この発言は 真 である
………

正直であることを特定できない...

何が悪いのか延々悩みました。もしかして,途中の発言自体「正直は本当のことしか言わない」,「嘘つきは嘘しか言わない」のかと思ったのは土曜日の昼である。

もしやと思い,以下の制約を付け加えてみる。

  if( man != truefalse) return;

ありゃ,出力が2行に減った。

嘘つきは…中略…⇒この発言は 偽 である★
正直者は…中略…⇒この発言は 真 である★

これが答えかな。

48時間ダイエットで少しお腹が凹んできたのが実感できる。既に前回食事から48時間を経過。

解速度