17100：3桁中2桁が正しければ入れるパスワード...000〜999の1000通りがある場合、具体的に入れる例を挙げよ...

問題17100(鍵コメT様からの前問に絡めた提示問 Orz〜)

「各桁に使われる文字の種類が2n種類で，3桁中2桁が正しければ入れるパスワード」
ならば，2n^2回以内で可能のようです．
n=5の場合は50回以内にログインできることになります.

「000〜999の1000通りがあり得る場合に，具体的にどんな50個を入力するばよいか」
(もちろん解はたくさんありますが，一例をあげること)

解答

・わたしの...

考えてみたけど...50個じゃできないわ...^^;

000...1

110

220

330

440

550

660

770

880

990...3*9=27

123,456,789...3*6=18

147,158,169,248,259,267,349,357,368...9*6=54

合計=1+27+18+54=100個

くらいしか思いつけず...^^;

・鍵コメT様からの想定解♪

100個用意するなら，もっとずっと簡単に，「000〜099」でいけます．
正しいパスワードが何でも，2桁目と3桁目が一致するものが含まれますね．

この組み合わせでは，「1桁目が一致し得る」ことを利用していないので，
改善の余地があります．
例えば，「099」を不要にしようと思えば，
正しいパスワードが099,199,299,399,499,599,699,799,899,999の場合に
対応ができればよいです．

099ははじめから対応済み(例えば「009」が2桁一致)．
199に対応するには，019を119に変えればよい．
299に備えて，029を229に変え，
399に備えて，039を339に変え，
499に備えて，049を449に変え，
599に備えて，059を559に変え，
699に備えて，069を669に変え，
799に備えて，079を779に変え，
899に備えて，089を889に変え，
999に備えて，090を990に変える
ことで，099が不要になり，99個でいけることになります．

50個の実例をあげます．

「1,2桁目が0〜4，3桁目は(先頭2桁の和)÷5の余り」の数を用意します．
000,011,022,033,044,
101,112,123,134,140,
202,213,224,230,241,
303,314,320,331,342,
404,410,421,432,443
この25数で，先頭2桁がともに0〜4であるものはすべて網羅されます．
それだけではなく，
1,3桁目や2,3桁目についても0〜4のすべての組み合わせが登場するので，
「1,3桁目がともに0〜4であるもの」，「2,3桁目がともに0〜4であるもの」
もすべて網羅されることになります．

追加で，この25数それぞれに555を足した25数を用意します．
555,566,577,588,599,
656,667,678,689,695,
757,768,779,785,796,
858,869,875,886,897,
959,965,976,987,998
上と同様に，この25数で，
「先頭2桁がともに5〜9」「1,3桁目がともに5〜9」「2,3桁目がともに5〜9」
であるものがすべて網羅されます．

正しいパスワードには，0〜4と5〜9の一方は2回登場するので，
以上の50数を試みれば，必ず入れることになります．
(例) 「718」であれば，5〜9が2回．50数中で「7?8」を探すと，768が存在．

*なるほどぉ☆

0〜9を2つのグループa,bに分けたものを数えれば...aaa,aab,aba,baa,bba,bab,abb,bbbで、必ずどちらかのグループに含まれるわけなのねぇ♪

そのグループ分け自体が問題にできそうなレベルだわ ^^;;...v