鳩の巣原理

鳩の巣原理は非常に単純な原理ですが以下のリンクでも紹介されているように多くの応用が可能です。

鳩ノ巣原理の意味と例（身近な例から超難問まで）

ここではその応用の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}$回試せば良いことになります。

これを元にするといくつかのグループに分解して少なくとも1つのグループは$m=2$となればよさそうに見えます。

鳩の巣原理を使う

鳩の巣原理を使ってこれを実現するためには以下の手順で行います。

すべてのヒューズを$(m-1)$のグループに分ければ少なくとも1つは動くヒューズを2個含む
この各グループごとにすべての2個の組み合わせを試せば2個含むグループで動く組み合わせを見つけることが出来る。

N=10, m=4の時

$(m-1)=3$なので3つのグループになるべく公平に分けます。このとき鳩の巣原理によりどれがのグループはOKを2個含んでいる（この場合はグループ３）ので、各グループごとにすべての2個の組み合わせを試せば必ず見つかることになります。

グループ	1	2	3
ヒューズの数	3	3	4
OK の数	1	1	2

この場合の試行回数$T$は以下のように求まります。

T = 2 \times \binom {3}{2} + 1 \times \binom {4}{2} \\
= 2*3 + 6 = 12

一般解

これを元に一般解は以下のようになります。

N = (m-1) \times q + r とすると \\
ヒューズの数が(q+1)個のグループはr個 \\
ヒューズの数がq個のグループは(m-1-r)個 \\
なので、\\
T = (m-1-r) \times \binom {q}{2} + r \times \binom {q+1}{2} \\
=  (m-1-r) q(q-1)/2 + r(q+1)q/2 \\
= q ((m-1)(q-1) + 2r)/2

N=10の時の$2 \le m \le 10$の時の結果は以下のようになります。

m	m-1	q	r	T
2	1	10	0	45
3	2	5	0	20
4	3	3	1	12
5	4	2	2	8
6	5	2	0	5
7	6	1	4	4
8	7	1	3	3
9	8	1	2	2
10	9	1	1	1

この考え方はProject Euler Problem 713: Turán's water heating systemを解くのに役に立ちます。