続 嘘つき天秤

偽コインの問題の解法としてDysonアルゴリズムというものがあるのを知る。
http://www.sci.hyogo-u.ac.jp/matsuyam/lecture_note/mathin96.pdf

で、こ れ は す ご い。

これを使うと嘘をつかない天秤の場合での測定回数+1で重り何個でも判定できる。しかも重いか軽いか分からなくても判定できる。これはすごい。

ただ偽者が入っているかどうかわからない場合はできないはず。
なぜなら基本ベクトル1とコードが1つしか違わないcwベクトルが必要になる場合がありえるから。と思ったが基本ベクトル周りのcwベクトルは3l/2しかないし置換こみでも9l/2で引いても十分重りの数に足りるなあ…。ただ割り当て方を変えるのってどうすればばば。

後は偽結果が確率論的にでる場合とか…かな。

追記

まいる。まあ色々すっ飛ばして書いていたからであろうけれど。何が一番大きい勘違いだったかというと、cwvコード(cwベクトルのコード)およびacwvコード(anti-cwベクトルのコード)が1文字変えても(隠しても)一致するものが無いように割り振れば(割り振れて)キーベクトルコードの1文字が嘘でも問題ないと思い込んでいたところ。と思う。
キーベクトルコードのどの場所が嘘か(嘘でないのか)わからない以上、コードのある部分を変えて(隠して)あるベクトルと対応したとしても、他の部分を変えて(隠して)他のベクトルと対応する可能性は残ってしまう。
じゃあコードを2つ変えても…という風になるような気がするけれど。何か"あともうちょっと感"がなぁ。罠？罠？
3の倍数でない重りの問題もあるのだけれど、そこも割り振り方で逐次的方法から機械的方法に移せないものか。例えば行列のやり方でいうと9個目のダミーを基本ベクトル1に置いていても条件Aは満たせたわけで。でもダイソン先生をしてそこを逐次的方法のまま残してるのだから罠といえば一番罠っぽいのはここなのかも。