公式解説に加えて，2 つの解法を紹介します．

(1) 911 回で解く方法

• 集合 \(A\)：未鑑定
• 集合 \(B\)：これの要素はすべて本物．
• 集合 \(C\)：これの要素はすべて偽物．
• 集合 \(X, Y\)：同じグループに入っているものは同種，逆のグループのものは異種

\(A=\{1,2,\ldots,1000\}\)，他は空集合として初期化します．

次を行います．

1. \(|X|=11\) または \(|Y|=11\) であるとき，そのグループは偽物ではない，したがって本物である．これらを \(B\), \(C\) にうつし，\(X\), \(Y\) を空集合に初期化する．
2. \(|A|=0\) ならば終了する．
3. \(|X|=|Y|=0\) ならば，適当な \(A\) の要素を \(X\) にうつし，1. に戻る．
4. 4. に到達した時点で \(|A|, |X|>0\) である．適当な \(A\) の要素を \(X\) の要素のひとつと比較して，結果によって \(X\) または \(Y\) に振り分け，1. に戻る．

最終的に \(|A|=0\) に到達し，すべてのコインが \(B\), \(C\), \(X\), \(Y\) に振り分けられます．

ここで，1. が実行されるのはどのようなタイミングでしょうか？ \(n\) 回目に 1, が実行されるのは，\(A\) からちょうど \(11n\) 枚の本物を取り出した直後であることが順に分かります．したがって，1. はちょうど \(90\) 回行われます．特に，アルゴリズム終了時点ですべての本物が確定します．

すると，3. は少なくとも \(89\) 回行われることが分かります．1. が行われたあと 3. が行われない可能性があるのは，2. が行われる高々 \(1\) 回だけだからです．

すると，\(A\) の要素が減るのは 3. または 4. しかなく，最初に \(|A|=1000\) であることと 3. の回数が \(89\) 回以上であることから， 4. が行われる回数は \(911\) 回以下であることが分かります．

(2) 951 回で解く方法

他の自然な解法として，\(951\) 回で解く方法があります．\(1000\) 枚のコインを \(20\) 個組 \(50\) グループに分割し，各グループを \(19\) 回ずつで \(2\) グループに分割すると，ほとんどの場合うまくいきます

ちょうど \(49\) グループで \((20,0)\) と分割され，\(1\) グループで \((10,10)\) と分割された場合だけ答が確定できません．\((10,10)\) と分割されるグループが出来てしまった場合だけは，最後に適切な追加鑑定すると \(951\) 回で解けます．

しかし残念ながら，これでは絶妙に本問の制約を達成することはできません．

が，あと \(1\) 回減らすためには最悪ケースだけを上手く回避するようなロジックをひとつ追加すればよく，これはそれほど難しくありません．例えば \((10,10)\) になりうるグループを優先して ，すべてのグループを並列で鑑定を進めていく方法などが考えられると思います．