判別の効率

（１）道行く外国人に質問し、ある姓を持つ外国人を集めたいとします。
例えば「Bush」「Clinton」「Obama」（アルファベット順）のうち
どれかの姓の外国人を集めたいとき、
外国人に会うたびに「Bushさんですか」「Clintonさんですか」「Obamaさんですか」と
一人に３回の質問をする必要があります。

つまりｎ種の姓の人を集めたいなら、一人にｎ回の質問が必要だとします。

（２）しかしここで、アルファベット26種をｘ個のグループに等分することを考えます。
前半１３、後半１３とする２分割とか、
９，９，８と分ける３分割です。３分割だと３等分ではなくなりますが、
そこは適当でいいとして１～２６分割ができるとします。
そして、姓の頭文字が最初のグループに入っているか？　次のグループに入っているか？
という質問も、一つと数えることにします。
この質問も、最初のグループから最後のグループへという順番で聞いていくことにします。

（２）の質問のあとに（１）の質問をすることで、質問の数をなるべく少なくすることを考えます。

初めの、ｎ＝３種の姓の人を集める例を考えると、
ｘ＝１のとき、（２）の質問は不要で、やはり一人につき３回の質問が必要になります。
ｘ＝２のとき、Bushは（２）の質問１回（「B」はアルファベットの前半なので）、
（１）の質問１回（３人のうちアルファベット順１番目なので。）で、合計２回。
Clintonは（２）が１回、（１）が２回で計３回。
Obamaは（２）が２回、（１）が１回（アルファベットの後半であると分かったので、頭文字が前半である姓について質問する必要がないから）で計３回。
一人平均2.5回の質問数になると思います。

質問数をなるべく少なくしたいときのｎとｘの関係はどうなるか、教えてください。

質問者からの補足コメント

• 回答No.１の方へ。
  前半についてはその通りでした。
  計３回というのは間違いで、計２回でした。すみません。
  
  後半については、
  質問数の数え方は、１つの姓について聞けば１回と数えることにしてください。
  「あなたは Bush さんまたは Clinton さんですか」という質問は、
  ２つの姓について聞いているのでダメというルールでお願いします。
  
  ｎとｘの関係式のようなものが得られるのではないかと思うのですが。

    補足日時：2016/04/17 00:07

• ｘ＝１のとき、誰にでも３回の質問が必要なように書きましたが、
  誰にでもではありませんでした。
  例にあてはめて考えると、ブッシュには１回の質問、クリントンには２回で終了ですね。
  そしてオバマとその他には、３回の質問が必要でした。

    補足日時：2016/04/17 00:36

• 細かく考えて頂いて有難うございます。
  
  質問数についてですが、これは、道行く外国人１００人に聞く場合の質問数や、
  １０００人に聞く場合の質問数、をなるべく少なくしたいという条件を考えていました。
  例えば１０００人に順に質問する場合、Bush と Clinton と Obamaなどという珍しい姓は
  実際はほとんどいないと思われるので、
  合計質問数は、ｘ＝１のときおそらく３０００回になると思います。
  たまたまブッシュさんが一人いて２９９８回になるという具合だと思います。
  １０００人を一堂に集めて質問するのではなく、個々に質問することにしてください。
  
  そうすると、合計何人に質問するのか分からなければ法則は得られないとか、
  珍しい姓を集めるのか、それともメジャーな姓を集めるのか決めなければ法則が得られないという
  ことになるかもしれません。

  No.2の回答に寄せられた補足コメントです。 補足日時：2016/04/17 06:37

• 相手の人数や姓の珍しさは決めなくても普遍的な法則が得られるかもしれないと思っていたので
  書かなかったのですが、必要になったときのため、
  私が一番得たい（んじゃないかと思われる）条件の目安を一応書いておくと、
  外国人の人数は４００人くらいで、集めたい姓はｎ＝２００種類くらい、
  全ての姓の種類は１０００くらいで、姓の珍しさはどれも一様である。
  姓に使われるアルファベットも一様であることにしてください。実際はXで始まる姓は少ないだろうとかは考えなくていいとします。
  
  この目安に、半分～３倍くらいの幅をもたせた辺りが一番知りたい数字です。
  例えば１０００人に聞きたいときもあれば、１００種類の姓しか集めないこともあり、
  姓の種類は全部で２０００だったりすることもあるなど。

    補足日時：2016/04/17 07:04

• 姓の頭文字のグループは、アルファベットを等分割したグループにしてください。
  A、Bの２文字で１グループにして、C～Zをもう一つのグループとして計２グループとする、
  などは等分割ではないのでダメということにしてください。
  グループごとの文字数は可能な限り同じに近づけることにします。
  （３分割ならば９、９、８しか認めないことにします。）
  アルファベットの順番を変えて並べてから等分割する、というのも無しにしてください。
  集めたい姓の頭文字を調べて、それに合わせて都合のいいアルファベットの分割数を決めるというのも無しにしてください。
  どんな姓を集めたいかは不明で、集めるのはｎ種とだけ分かっている、としてください。

  No.3の回答に寄せられた補足コメントです。 補足日時：2016/04/17 07:22

• 回答No.２に対する補足を一部忘れていたので書きます。
  
  ＞最初に「あなたの頭文字は A〜M ですか」と聞いて,
  ＞Yes なら「あなたの頭文字は A〜G ですか」と聞く
  
  これは無しにしてください。
  アルファベットの等分割は１度きりとします。
  例えばｘ＝３分割ならばA～I（９個）とJ～R（９個）と最後（８個）のグループしかなく、
  誰に対しても「頭文字はA～Iですか」と聞き、（答えがNoなら）「J～Rですか」と聞き、終了とします。この順番で質問しなくてはならず、人によってｘの値を変更してはいけないことにして下さい。
  ３分割について聞いたので、次に１３分割について聞く、というような
  「ｘを変更しての再質問」はダメとします。

    補足日時：2016/04/17 07:41

No.1 回答者： tumagie 回答日時： 2016/04/16 14:10

条件がよくわからないのでご確認したいのですが,

＞Obamaは（２）が２回、（１）が１回（アルファベットの後半であると分かったので、頭文字が前半である姓について質問する必要がないから）で計３回。

「アルファベットの前半でない」とわかった時点で Bush でも Clinton でもない訳ですから,
(2) の質問 1 回目の「アルファベットの前半ですか」に「No」と答えが返ってきた時点で (1) の質問「Obama さんですか」をすればいいので,
計 2 回で済むと思うのですが, これは条件に反するのでしょうか.

さらに言えば, 例えば,

最初に「あなたは Bush さんまたは Clinton さんですか」と質問して,
Yes → 「あなたは Bush さんですか」
No → 「あなたは Obama さんですか」

と質問することにすれば,
1回目 Yes 2回目 Yes → Bush
1回目 Yes 2回目 No → Clinton
1回目 No 2回目 Yes → Obama
(1回目 No 2回目 No → それ以外)

となって, Bush にも Clinton にも Obama にも 2 回の質問で済むと思いますが, これはルール違反なのでしょうか.

この回答へのお礼

ありがとうございました。

お礼日時：2016/04/18 02:51

No.2 回答者： tumagie 回答日時： 2016/04/17 01:59

＞質問数の数え方は、１つの姓について聞けば１回と数えることにしてください。

わかりました.

＞ｘ＝１のとき、誰にでも３回の質問が必要なように書きましたが、
＞誰にでもではありませんでした。
＞例にあてはめて考えると、ブッシュには１回の質問、クリントンには２回で終了ですね。
＞そしてオバマとその他には、３回の質問が必要でした。

確かにそうですね.

ところで, 「質問数をなるべく少なくしたい」の「質問数」というのは
「Bush と Clinton と Obama への質問数の平均」だと思っていたのですが, (最初の本文中に「その他」の質問数に関する言及がなかったので),
もしかして「Bush と Clinton と Obama と その他 (を1人としてカウントしたとき) の質問数の平均」なのでしょうか.
例えば x=1 の場合,
前者なら (1+2+3) / 3 = 2
後者なら (1+2+3+3) /4 = 2.25
という計算になりますが….

あと, しつこくて恐縮なのですが, これも念の為確認しておきたいのですが,
例えば最初に「あなたの頭文字は A〜M ですか」と聞いて, Yes なら「あなたの頭文字は A〜G ですか」と聞く, みたいなのは無しで, 質問文のようなやり方のみを考えるということでいいのですよね？

この回答へのお礼

ありがとうございました。

お礼日時：2016/04/18 02:51

No.3 回答者： tumagie 回答日時： 2016/04/17 02:27

すみません, まだ確認すべきことがありました.

＞３分割だと３等分ではなくなりますが、
＞そこは適当でいいとして１～２６分割ができるとします。

例えば, Bush と Clinton と Obama と Roosevelt の 4 つの姓が 対象だった場合, x=2 として, 頭文字が

A〜B と C〜Z に分ける (Bush だけ先のグループ, 残りは後のグループ)
A〜C と D〜Z に分ける (Bush と Clinton だけ先のグループ, 残りは後のグループ)
A〜Oと P〜Z に分ける (Roosevelt だけ後のグループ)

というように色々な分割があって, 分割のしかたによって質問回数も違ってきますが,
どの分割をするかは自由ということでいいのでしょうか.

#そういう前提で, プログラムを組みながらちょっと考えていますが, たぶん x と n の綺麗な関係式を得るのは難しいと思います.
#x が 2 以上のときは, 上記のように, グループの分割のやり方がいろいろあるというのが, この問題を難しくしています.
#返答を頂き次第, n=2〜10 あたりに対しプログラムを組んで計算した x の値をここに貼ります.

この回答へのお礼

ありがとうございました。

お礼日時：2016/04/18 02:51

No.4 ベストアンサー 回答者： tumagie 回答日時： 2016/04/17 14:05

わかりました. では, とりあえず

・姓 1, 姓 2,..., 姓 n の n 種類の姓を集める (n≒200)
・姓の個数は全部で N 個 (N≒1000)
・姓を x 個に等分割

ということで考えていきましょう.
(質問する外国人の人数は 400 人程度とのことですが, これは答えを出す上では関係ありませんね. 要は 1 人に質問したときの質問回数の期待値だけが問題なので.)

姓の珍しさは一様 (すべての姓が 1/N の確率であらわれる) とし,
姓に使われるアルファベットも一様ということで,
x 個に分割したときにどのグループにも N/x 個の姓が属すると仮定してしまいましょう.
また, 集めたい 1,2,...,n の n 種の姓についてもアルファベットの偏りはなく,
x 個に分割したときにどのグループにも n/x 個の姓が属すると仮定しましょう.
(本当は, N/x や n/x が割り切れない場合多少のズレが生じますが, とりあえず割り切れると仮定してしまいましょう.
更には, 26/x が割り切れなかったらアルファベットでは x 個に等分割できないといった問題もありますが,
アルファベットとかそういうことは考えないで, とにかく N 個の姓を x 個のグループに等分割した, このとき集めたい n 個の姓も等分割された,
ということにしておきます.)
なにか仮定に不都合な箇所があれば, ご指摘ください.

このとき, 質問 (2) に要する回数は, x 等分したときのグループを順にグループ 1, グループ 2, ..., グループ x とすれば

グループ 1 に属する人に 1 回
グループ 2 に属する人に 2 回
…
グループ x-1 に属する人に x-1 回
グループ x に属する人に x-1 回 (今までの質問すべてに No だった時点でグループ x に属するとわかる)

ですから,
平均で (1+2+…+(x-1)+(x-1))/x = (x(x+1)/2-1)/x = (x+1)/2 - 1/x
回の質問をすることになります.

次に質問 (1) ですね.
質問している対象の人がどこのグループに属していようと, 質問する平均回数は変わりませんから,
グループ 1 に属しているものとしてしまいましょう. すると,

姓 1 の人には 1 回
姓 2 の人には 2 回
…
姓 n/x の人には n/x 回
その他の姓 (姓 1,…, 姓 n のいずれでもない姓) の人には n/x 回

ということになります.
すると, 姓 1,…, 姓 n の人たちには平均で (1+2+…+n/x)/(n/x) = (n/x + 1)/2 回の質問をすることになります.
その他の姓の人には n/x 回の質問をすることになります.
仮定から, 集めたい姓とその他の姓の人の割合は n:(N-n) ですから,
全体としては平均で ((n/x + 1)/2 * n + n/x * (N-n)) / N = n^2/2Nx + n/2N + n/x - n^2/Nx = n/2N + n/x - n^2/2Nx 回の質問をすることになります.
(面倒なので括弧を省きましたが, 例えば n^2/2Nx という分数は 2Nx までが分母だと思って読んでください.)

結局,
質問 (2) には (x+1)/2 - 1/x 回
質問 (1) には n/2N + n/x - n^2/2Nx 回の質問をすることになるので, 合計で

(x+1)/2 - 1/x + n/2N + n/x - n^2/2Nx
= x/2 + (n(1-n/2N)-1)/x + 1/2 + n/2N

回の質問をすることになります.
これを最小にするには, x/2 + (n(1-n/2N)-1)/x を最小にすればよいです.
n≧3 とすれば, (n(1-n/2N)-1)/x は正なので相加相乗平均の不等式が使えて,
x/2 + (n(1-n/2N)-1)/x ≦ 2√((n(1-n/2N)-1)/2)
であり, 等号は x/2 = (n(1-n/2N)-1)/x のときに成立します.
したがって x = √(2n - n^2/N - 2) が得られました. (正確には整数とは限らないので切り上げ or 切り下げをする必要がありますが.)

途中に計算ミスなどがないか不安ですが, 一応 x が n と N を用いた式で表せました.
(n が N に比べ十分に大きいなら, x≒√(2n) ということになりますね.)

実際に n=200, N=1000 で計算してみますと,
x = √(2*200 - 200^2/1000 - 2) = √358 ≒ 19
ですね.
この場合なら, n/x や N/x が割り切れないとはいえ, n や N が x に比べて割りと大きいので,
最初の「n/x や N/x は割り切れるとする」といった仮定による誤差は, おそらく大して問題にはならないと思われます.

この回答へのお礼

こんないい感じの式が得られるとは思いませんでした。使わせて頂きます。
丁寧に解説してくださってありがとうございました。
しかし自分では経験をよほど積まないと答えは出せないだろうなと思いました。
経験はどうしても必要ですね。

お礼日時：2016/04/18 02:48

No.5 回答者： tumagie 回答日時： 2016/04/17 14:23

補足:

集めたい姓の人は姓全体からするとかなり少ないとした上で, かなり大雑把に見積もるのなら

・質問 (2) は x グループに分けて質問するので, 平均的にはだいたい x/2 回の質問をする
・質問 (1) は (集めたくない姓の人に) n/x 回の質問をする

ので, 大体 x/2 + n/x 回の質問をすることになる. これは相加相乗平均の不等式により x=√(2n) で最小になる…とやれば十分ですね.

この回答へのお礼

本物の姓なら何十万もありそうなのでこの式で考えると楽ですね。
８種類の姓を集めたいときはアルファベット４等分グループを作るのがいいんですね。
３３８種類以上の姓を集めるなら、アルファベットは２６等分がいい
等、考えると面白いですね。

お礼日時：2016/04/18 03:02