鳩の巣原理を使って2個のヒューズ探し問題を解く - Qiita

鳩の巣原理 鳩の巣原理は非常に単純な原理ですが以下のリンクでも紹介されているように多くの応用が可能です。 鳩ノ巣原理の意味と例（身近な例から超難問まで） ここではその応用の1つをを紹介します。 2個のヒューズ探し問題 [問題] 壊れた回路を直すためにヒューズが2個必要です、N個のヒューズがありますがその内、壊れていないのは$m$だけです。見た目には違いは分かりません。2個を装着して初めて2個とも機能することが分かります。少なくとも何回試せば機能する2個のヒューズを見つけることが出来るでしょう？ N=3, m=2の時 この場合3個の内2個はOKと分かっているので、すべての組み合わせ$\Large \binom {3}{2}$を試せば良いので答えは3回となります。 一般に$m=2$の時には$\Large \binom {N}{2}$回試せば良いことになります。 これを元にするといくつかのグルー