朝日新聞2006年6月23日のパズル横丁問題

問題

正直者と嘘つきが10人並んでいる。正直者は正しく答え,嘘つきは正直者と逆の答えを言う。

先頭から順に9人に「次の人は嘘つきですか?」と質問したとき,その答えから嘘つきが何人いるか判るのはどのような場合か?

解答への道(ヒント)

はっきり言おう。嘘つき問題は苦手だ。

正直者が○,嘘つきが●の場合,例えば以下のように並んでいるとする。

○○●○○●○●●○

このとき先頭から質問していくと

NYYNYYYNY

という回答になる。

最初考えたのは以下のようなプログラム。答えのパターン数が1になる出力があればそれが解と思った。

#include "puzutl.h"

map<string,int> pattern;

void ans( int user)
{
  char ans[9+1/*NIL*/]; // 質問の答え, Y:はい, N:いいえ
  YesNo         honest;
  for( int i=0; i< 9; i++) {    // 先頭から9人に答えを聞く
    honest      = user&1;
    user        >>= 1;
    if( honest) {
      // 正直者は「次の人は嘘つきか?」に対し正しく答える
      if( user&1) ans[i] = 'N'; // 次の人は正直者
      else        ans[i] = 'Y'; // 次の人は嘘つき
    }
    else {
      // 嘘つき,逆を答える
      if( user&1) ans[i] = 'Y'; // 次の人は正直者
      else        ans[i] = 'N'; // 次の人は嘘つき
    }
  }
  ans[i]        = NIL;
  map<string,int>::iterator ite = pattern.find( ans);
  if( ite == pattern.end()) {
    // 初めて出現する答えのパターン
    pattern.insert( pair<string,int>(ans, 1));
  }
  else {
    // 既に出現した答えのパターン。
    (*ite).second++;
  }
}

int main( int argc, cstring argv[])
{
  for( int user=0; user< 1024; user++) {
    ans( user);
  }
  // 全てのパターンを出力してみる。
  map<string,int>::iterator ite;
  for( ite=pattern.begin(); ite != pattern.end(); ite++) {
    string s = (*ite).first.c_str();
    int cnt = (*ite).second++;
    ps( "%s %d\n", s.c_str(), cnt);
  }
  return    0;
}

しかし出力されるのは以下のように全て2ばかり。

NNNNNNNNN 2
NNNNNNNNY 2
NNNNNNNYN 2
NNNNNNNYY 2
NNNNNNYNN 2
NNNNNNYNY 2
………

この時点で特定の回答パターンを求める問題じゃないことに気づく。

回答時の正直者の数を勘定するように変更したらそれらしき答えになる。

答えは1件出力されました。

 

ワールドカップ1次リーグ敗退。2002年のワールドカップは無かったものとして考えれば,今回の目標は「1勝」だと思っていたが,その前に「勝ち点1」という目標があった。

それを達成できたことで満足すべきか。

ちなみに98年のフランス大会は「得点1」が目標だと思っていたので,目標を達成できたと思っている。

4年後には1勝(勝ち点3でない)を目指して欲しいけど,その前に予選を突破できるかどうかが問題になる。

このままでは次回はアジア枠は減少するだろうし,オーストラリアもアジア予選に入ってくる。

 

アップロード前に順位を確認。

イランD組4位勝ち点1,日本F組4位勝ち点1,韓国G組3位勝ち点4,サウジアラビアH組4位勝ち点1。

アジア枠がーーーー

解速度