😊出会いの泉😊

注目すべきは、陰性報告をしてきた 3 人が、「測定にかけなかった」方のコインですね。
あとは、カークマンの組分け問題は（多分ファノ平面で考えた場合でも？）、任意の 2 つの組の間に必ず共通人物が 1 人だけ存在することも注目に値します。

DD++ さん。

たびたびのヒントを有難うございます。
おかげさまで
偽コイン候補が「３個以下」であるとは示せました。
しかしながら丁度３個あるというところまではまだいきついておりません。
なにか単純なことを見落としているにちがいありません。

もう少しだけ考えてみます。

陽性報告数 4 だけど矛盾が含まれている場合の話ですよね？

陰性報告をした 3 人を A, B, C とします。
A が嘘つきだと仮定すると、A が測定にかけていて、B と C が測定にかけていないコインは本物候補になります。
さて、そのようなコインは何枚存在するでしょうか？

DD++ さん。
おっしゃる通りですね！！！
最大のヒントをまことにありがとうございます！！！

皆様へ。
あとでボチボチと証明のアウトラインを書いていく所存です。

せっかく DD++ さんにヒントをいただいておりますのに、【丁度３個である】ほうの証明をまだ書き下せておりません。ポンチ絵については漸く出来上がりましたけれども。申し訳ないことです。

[2191]の投稿で私は【３個以下】の証明なら出来たと申しておりました。
今日はこちらのほうのメモ書きを下記に投稿いたします。

金貨の名前を
z, a, b, c, d, e, f, g
とします。
技術者７名には添え字として 1 から 7 を与えます。
ガイガーカウンターによる
検査結果を
q とします。
q は、7名の技術者による陰性(0)、陽性(1) の結果を示す
𝑞₁, 𝑞₂, 𝑞₃, ... , 𝑞₇
として表します。

いま、偽金貨が a である状況下で、
技術者が q の検査結果を返したとします。
また、パリティ検査により、
q は a に対してハミング距離が 2 であると判明したものとします。

一般性を失わないようにするために、
q や、z, a から g までに使われる添え字である、 1 から 7 までについて
{h, k, m, n, p, s, t} = {1, 2, 3, 4, 5, 6, 7}
とします。蛇足ですが両辺の集合の各要素は一対一対応しますけれども順不同です。
以下の記述で一般性を失わないための約束てす。

また、𝑎₁ のビット反転したものを 𝑎̅₁ などと、オーバーラインで表すこととします。

偽金貨 𝑎 にたいする 検査結果が 𝑞 として与えられるものとします。2 ビットの反転は、ビット位置 h, k で発生していることとします。
図示すれば、次の２行の各ビットの上と下とは真理値は等しいです。

𝑎̅ₕ, 𝑎̅ₖ, 𝑎ₘ, 𝑎ₙ, 𝑎ₚ, 𝑎ₛ, 𝑎ₜ
𝑞ₕ, 𝑞ₖ, 𝑞ₘ, 𝑞ₙ, 𝑞ₚ, 𝑞ₛ, 𝑞ₜ

この 𝑞 が 𝑏 をも偽金貨の候補として考えられることしましょう。図示しますと以下の３パターンのみに分かれます。

◆パターン１
𝑎̅ₕ, 𝑎̅ₖ, 𝑎ₘ, 𝑎ₙ, 𝑎ₚ, 𝑎ₛ, 𝑎ₜ
𝑞ₕ, 𝑞ₖ, 𝑞ₘ, 𝑞ₙ, 𝑞ₚ, 𝑞ₛ, 𝑞ₜ
𝑏̅ₕ, 𝑏̅ₖ, 𝑏ₘ, 𝑏ₙ, 𝑏ₚ, 𝑏ₛ, 𝑏ₜ

◆パターン２
𝑎̅ₕ, 𝑎̅ₖ, 𝑎ₘ, 𝑎ₙ, 𝑎ₚ, 𝑎ₛ, 𝑎ₜ
𝑞ₕ, 𝑞ₖ, 𝑞ₘ, 𝑞ₙ, 𝑞ₚ, 𝑞ₛ, 𝑞ₜ
𝑏ₕ, 𝑏̅ₖ, 𝑏̅ₘ, 𝑏ₙ, 𝑏ₚ, 𝑏ₛ, 𝑏ₜ

◆パターン３
𝑎̅ₕ, 𝑎̅ₖ, 𝑎ₘ, 𝑎ₙ, 𝑎ₚ, 𝑎ₛ, 𝑎ₜ
𝑞ₕ, 𝑞ₖ, 𝑞ₘ, 𝑞ₙ, 𝑞ₚ, 𝑞ₛ, 𝑞ₜ
𝑏ₕ, 𝑏ₖ, 𝑏̅ₘ, 𝑏̅ₙ, 𝑏ₚ, 𝑏ₛ, 𝑏ₜ

分析します。
パターン１では、
a と b とは、ハミング距離が 0 となってしまい、本来あるべきハミング距離が４であることと矛盾します。パターン１はありえません。
パターン２では
a と b とは、ハミング距離が 2 となってしまい、本来あるべきハミング距離が４であることと矛盾します。パターン２はありえません。
パターン３では
a と b とは、ハミング距離が 4 となり、本来あるべきハミング距離が４であることと矛盾しません。パターン３はありえます。
これらより、パターン３のみが、a と b との間の関係を示しています。パターン３を再掲します。

𝑎̅ₕ, 𝑎̅ₖ, 𝑎ₘ, 𝑎ₙ, 𝑎ₚ, 𝑎ₛ, 𝑎ₜ
𝑞ₕ, 𝑞ₖ, 𝑞ₘ, 𝑞ₙ, 𝑞ₚ, 𝑞ₛ, 𝑞ₜ
𝑏ₕ, 𝑏ₖ, 𝑏̅ₘ, 𝑏̅ₙ, 𝑏ₚ, 𝑏ₛ, 𝑏ₜ

さて、第三の金貨 c が偽造金貨の候補だとしましょう。
ありえるパターンは以下のみです。

𝑎̅ₕ, 𝑎̅ₖ, 𝑎ₘ, 𝑎ₙ, 𝑎ₚ, 𝑎ₛ, 𝑎ₜ
𝑞ₕ, 𝑞ₖ, 𝑞ₘ, 𝑞ₙ, 𝑞ₚ, 𝑞ₛ, 𝑞ₜ
𝑏ₕ, 𝑏ₖ, 𝑏̅ₘ, 𝑏̅ₙ, 𝑏ₚ, 𝑏ₛ, 𝑏ₜ
𝑐ₕ, 𝑐ₖ, 𝑐ₘ, 𝑐ₙ, 𝑐̅ₚ, 𝑐̅ₛ, 𝑐ₜ

a と b との関係は、a と c, b と c との関係にもそのまま通用するからです。

測定結果である q について、a, b, c が偽金貨の候補である場合には、ビット反転の関係は上に尽きることとなります。

ここで、更に、金貨 d が偽金貨の候補足り得るかと問いを立てます。

h,k,m,n,p,s 以外のふたつの位置で、d は q にたいしてビット反転していなくてはなりませんがこれは不可能です。

ここまでをまとめれば、
測定結果 q が与えられたならば、偽金貨であることがありえるのは、a,b,c, の３枚までで、4枚以上ではあり得ないことがわかりました。

なお、３枚以下であることを示しただけであって、３枚丁度を示したわけではないことを付記しておきます。

あれ？
私はわりと答えそのもののつもりで書いてたんですが……

陽性報告が 4 人だった場合、
・全員正直
・陽性報告と陰性報告それぞれで 1 人嘘つき
のいずれかですよね？
前者はハミング距離 0 で話は終わっています。
後者の場合、陰性報告者のうち 2 人が測定から外したコインが本物候補です。
そしてそれは任意の陰性報告者 2 人組の間に共通で測定しなかったコインが（誰も測らなかったやつ以外で）必ずちょうど 1 枚あり、合計で 3C2 = 3 枚存在します。

DD++ さん、たびたびお手を煩わせてしまいまして申し訳ございませんでした。有難うございます。

■問題の振り返りをします。
No.2129Dengan kesaktian Indukmu9月8日 00:09
の問題では 10 人のケースでは解あり、では9人では？ となったのがことの発端です。

９人のうち、第一段階で７人を投入、そこで偽金貨が特定できればよし、そのなかに虚偽のレポートをしてくる技術者が２人いるケースもありうるがその場合には偽金貨が特定できないものの、偽金貨の候補が【丁度】３枚になるので、第二段階として残りの正直な技術者２名が偽金貨を特定できるだろう、ゆえに技術者は9人で十分だ、という筋書きなのでした。

今回は第一段階のアルゴリズムを決定し、なおかつ【丁度３人】問題について、個人的な結論を皆さんにご報告いたします。

///////////
ご注意:ここまでの流れと陰性陽性の扱いが逆転してしまっています。申し訳ありません。
(ひとえに私の直観にあわせてしまっただけなのですが……)
///////////

■第一段階での測定について
i を 1 から 7 までの添字として使います。
j を 1 から 8 までの添字として使います。

7人いる技術者に、1 から 7 と名前をつけます。添字としてはもっぱら i を使います。

陽性集合 Pj を以下のように定義します。
P1 = {2, 3, 5}
P2 = {3, 4, 6}
P3 = {4, 5, 7}
P4 = {5, 6, 1}
P5 = {6, 7, 2}
P6 = {7, 1, 3}
P7 = {1, 2, 4}
P8 = {1, 2, 3, 4, 5, 6, 7}
※余談ですが P1 から P7 は、FANO平面となっています。P8 は余計ものです。

陰性集合 Nj を以下のように定義します。
N1 = {7, 6, 4, 1}
N2 = {1, 7, 5, 2}
N3 = {2, 1, 6, 3}
N4 = {3, 2, 7, 4}
N5 = {4, 3, 1, 5}
N6 = {5, 4, 2, 6}
N7 = {6, 5, 3, 7}
N8 = {}

8 枚の金貨に以下のように名前をつけます。
C{Pj, Nj}
すなわち、金貨の名前については陽性集合と陰性集合の組みの集合で定義します。

長くなりましたので、投稿をいったん区切ります。

■第一段階での測定について(つづき)
7人の技術者に次のように測定の指示をだします。すなわち、
i 番目の技術者は、Pj の要素に i を含むような金貨 C{Pj, Nj} をガイガーカウンターで計測します。

◆早見表 | 1 2 3 4 5 6 7 ←技術者
C{P1, N1} | 0 1 1 0 1 0 0
C{P2, N2} | 0 0 1 1 0 1 0
C{P3, N3} | 0 0 0 1 1 0 1
C{P4, N4} | 1 0 0 0 1 1 0
C{P5, N5} | 0 1 0 0 0 1 1
C{P6, N6} | 1 0 1 0 0 0 1
C{P7, N7} | 1 1 0 1 0 0 0
C{P8, N8} | 1 1 1 1 1 1 1
※この早見表では、1 が立っている金貨を計測します。

陽性のレポートをした技術者の集合を T と名づけます。

Tから偽金貨のゆくえを探すということとなります。
たとえば T={2,3,5} ならば偽金貨は C{P1, N1} ということとなります。


■計測結果Tの評価について
簡単なものから順に。

① T = Pj となる j があるとき
※７人ともに正しいレポートを提出したこととなります。
偽金貨は、C{Pj, Nj}。


②Tの要素数が 2 のとき
※すなわち陽性を陰性と偽ったレポートがひとつあったことになります。

j = 8 を除外できます。
Pj ⊃ T なる j が唯一に定まります。
偽金貨は、C{Pj, Nj}。


③Tの要素数が 4 のとき
※陰性を陽性と偽ったレポートがひとつあったことになります。

j = 8 を除外できます。
Pj ⊂ T なる j が唯一に定まります。
偽金貨は、C{Pj, Nj}。


④Tの要素数が 6 のとき
※陰性を陽性と偽ったレポートがひとつあったことになります。

偽金貨は、C{P8, N8}。

ここまで①②③④は T と偽金貨の Pj とのハミング距離が 0 または 1 なのでした。

(続きます)

■計測結果Tの評価について(つづき)
⑤Tの要素数が 1 のとき
※陽性を陰性と偽ったレポートがふたつあったことになります。
j = 8 を除外できます。

このとき T の要素を信じることができます。誤ったふたつのレポートの影響を受けていないためです。
T ⊂ Pj
となる j は３つあります。(FANO平面の性質です)
３つある偽金貨の候補 C{Pj, Nj} については第二段階で、(これ以上は誤ったレポートが発生しないため) 処理可能となります。


⑥Tの要素数が 5 のとき
偽金貨の候補としてふたつのグループが考えられます。
⑥‐１
※C{P8, N8} について、陽性を陰性と誤ったレポートが２通発生したケースです。
偽金貨の候補として
これがひとつめのグループです。
⑥‐２
※j=8 を除外しての C{Pj, Nj} について、陰性を陽性と誤ったレポートが２通発生したケースです。
誤ったレポートを出した技術者の添字の値を m,n とします。
{m} ⊂ Pj なる C{Pj, Nj} は ３個あります。
これは FANO平面の性質です。
{n} ⊂ Pj なる C{Pj, Nj} は ３個あります。
これも FANO平面の性質です。
{m,n} ⊂ Pj なる C{Pj, Nj} は １個あります。
これは FANO平面の性質です。
誤ったレポート m,n を含んだC{Pj, Nj}は
3+3-1=5 より、５個あります。
j=8 を除外しての C{Pj, Nj} の７個のうち、
本物の金貨として除外できるのは５個となり、偽金貨の候補は２個となります。
やや迂遠な論法でしたが、
T ⊃ Pj を満たす j は２つあるということとなります。
⑥‐３
以上より、この⑥のケースでは、偽金貨の候補の枚数は３枚となりました。

(つづきます。次は私にとっての天王山で、DD++ さんからお知恵を拝借した部分です。)

(本日は夕飯の支度をしなければならない身分ですので、ひょっとすると明日になるかもしれません。)

私にとっても直観と逆でしたので、この変更はありがたいです。

6-2 は、陽性を陰性と偽った報告がない以上、陰性報告は全て信じてよく、それで 5 枚が本物と確定できますね。

DD++ さん、[2217]← あっと叫びました。
それはそうですね……自明なものを私のようにこねくりまわしてはダメですね……

気を取り直して。以下では、A∖B を差集合の表記とします。
　

⑦Tの要素数が 3 のとき
(ただし、①のケースは除きます。)
※陽性を陰性にする誤ったレポート１通と、陰性を陽性にする誤ったレポートを１通と、計２本の誤ったレポートが発生しているケースです。

話の都合上、T に基づいてUを作ります。Uが全体集合でなくてすみません。
U = {1, 2, 3, 4, 5, 6, 7}∖T
そして、偽金貨のC{Pj, Nj}について
Pj = {x, y, z}
Nj = {p, q, r, s}
とします。
T = {p, y, z,}
U = {x, q, r, s}
が測定の結果として得られていることとなります。

Tの３つの要素のうち、偽レポートがひとつあるので、その可能性は丁度３通りあります。
偽物を大文字で書くと
Pj = {X, y, z}
Pj = {x, Y, z}
Pj = {x, y, Z}
のどれかが実現していることとなります。
Tに含まれる３つの要素のうち２つを選ぶと、それぞれに対応して金貨がひとつ定まるということとなります。

以上より、この⑦のケースでは、偽金貨の候補の枚数は３枚となりました。


さて、結論です。
以上をまとめますと、第一段階で７人中に２人分の偽レポートが発生したときには、偽金貨候補は常に３個であることがわかります。
誤りレポートの数が 0 ないし 1 であるときには、偽金貨は確定します。


《感想》
もうちょっと簡単に書ければ良いのですが。

先に提示させていただいた早見表で
再び、0 と 1 とをビットフリップした上で、下記に再掲させていただきます。

C{P1, N1} | 1 0 0 1 0 1 1 //C4
C{P2, N2} | 1 1 0 0 1 0 1 //C6
C{P3, N3} | 1 1 1 0 0 1 0 //C7
C{P4, N4} | 0 1 1 1 0 0 1 //C3
C{P5, N5} | 1 0 1 1 1 0 0 //C5
C{P6, N6} | 0 1 0 1 1 1 0 //C2
C{P7, N7} | 0 0 1 0 1 1 1 //C1
C{P8, N8} | 0 0 0 0 0 0 0 //C0

なお、各行の右端は、これから始める説明の都合上、各金貨に新しく名前づけしたものです。

ビット列の排他的論理和の記号として「⊕」を使うこととします。
たとえば、 0110 ⊕ 1010 = 1100 です。

1 ≤ n ≤7 について
C0 ⊕ Cn = Cn
は、自明ですね。

ビックリしたのが、以下のようになっていることです。

C3 = C2 ⊕ C1
C5 = C4 ⊕ C1
C6 = C4 ⊕ C2
C7 = C4 ⊕ C2 ⊕ C1

つまり、C1,C2,C4 さえ知っていれば、
他については、２進数の仕掛けによって割り出せるということになります。

これは私にとっては非自明なことですので
皆様にもご報告する次第です。

OEIS の
A075931
List of codewords in binary lexicode with Hamming distance 5 written as decimal numbers.
から、
0,31,227,252,805,826,966,985,1354,1365,1449,1462,1647,1648,1676,1683
までを利用して
符号長 11 、最小ハミング距離 5 の符号のビット列を以下のように作成しました。
"12 0 3 00 4 0000"←↓見出し
"00 0 0 00 0 0000",//0
"00 0 0 00 1 1111",//1
"00 0 1 11 0 0011",//2
"00 0 1 11 1 1100",//
"01 1 0 01 0 0101",//4
"01 1 0 01 1 1010",
"01 1 1 10 0 0110",
"01 1 1 10 1 1001",
"10 1 0 10 0 1010",//8
"10 1 0 10 1 0101",
"10 1 1 01 0 1001",
"10 1 1 01 1 0110",
"11 0 0 11 0 1111",
"11 0 0 11 1 0000",
"11 0 1 00 0 1100",
"11 0 1 00 1 0011",

見出しについて説明します。
"12 0 3 00 4 0000"
で、1,2,3,4 は、データビット(4ビット)として使えるビット位置です。上位から昇順にしています。
"12 0 3 00 4 0000"
"01 1 0 01 1 1010",
上の例では、0101 を意味しており、10進では 5 です。これが、確かに 0 オリジンで 5 番目のビット列であることに留意して頂ければ幸いです。
上の一覧表は、4ビットのデータビットの符号語を、11ビットにエンコードしたものとなっています。

前回の投稿、No.2220 で発生していた摩訶不思議な現象が、上でもおきているのかについてプログラムで検証しましたところ、オーケーとなりました。
"00 0 0 00 1 1111",//1
"00 0 1 11 0 0011",//2
"01 1 0 01 0 0101",//4
"10 1 0 10 0 1010",//8
を知っていれば、
他の11個の符号語は、排他的論理和でもって計算できるのです。
いや、これ自明だろうとお感じになられるかたもいらっしゃるかもしれません。

しかしながらですね、
この A075931 の数列は、0 から順に 1 づつ　カウントアップしていき、テーブル上にためてある(先行する)全ての数とハミング距離が5以上となる数をみつけてはテーブルに追加して溜め込んでいるだけで、作っているんです。貪欲アルゴリズムでもってグリーディに。有る意味では汚い作り方。

なのに、[2220]の投稿で触れた法則がある、そもそも、A075931 で、私が勝手に設定した【見出し】が、符号語の値を直に示しているなんて、不思議で不思議でならないのです。

たとえば、最小ハミング距離が 6 で、符号長が 13 、符号語数も 13 の、次の符号には、今話題にしている[法則]を私はみつけられません。

"0011101111101",
"1001110111110",
"0100111011111",
"1010011101111",
"1101001110111",
"1110100111011",
"1111010011101",
"1111101001110",
"0111110100111",
"1011111010011",
"1101111101001",
"1110111110100",
"0111011111010",

データビットがどこなのかも曖昧ですしね。
サイクリックですから。

綺麗な仕掛けで作った割には、
グリーディに作ったものに、有る意味、負けているのです。

この謎、面白くてしょうがないです。

2221 で私は無手勝流にデータビットの位置を決めていたのですが、(つまりチェックビットの位置を決めていたのですが)

とっくの昔にコンウェイさんが決めて？ました。どうやったんやろ？　
このテーブルが大きくなるとこれらの位置はさかわるとのこと。まあ。