鳩の巣原理特集 - 問題解決の宝石箱

Competitive Programming Advent Calendar 2016 23日目の記事です。

鳩の巣原理と、競技プログラミングでの使われ方を紹介します。

鳩の巣原理とは

昔々あるところに、5羽の鳩がおりました。彼らをすべて巣箱に入れたいのですが、あいにく巣は4つしかありませんでした。すると以下の図のように、どこか1つの巣には2羽以上の鳩が入ってしまいます。

f:id:hama_DU:20161219005149p:plain

f:id:hama_DU:20161219005151p:plain

適当な入れ方をすると、2羽より多い巣があったり、空の巣があるかもしれません。でも、どんな入れ方をしても「どこかの巣には2羽以上」入ることが保証されます 。

f:id:hama_DU:20161219005134p:plain

一般に n 羽の鳩を m < n 個の巣にいれるとき、どこか 1 つの巣には鳩が2羽以上入ります。

更に一般化。巣に入っている鳩の最大数を最小化しようとすると、各巣になるべく均等に鳩を配る形になります。このとき、鳩の数の最大値は ${ \lceil n / m \rceil }$ *1 となり、これが最大値の下限になります。以下の図は n = 10, m = 4 とした例で、最低でも3羽以上の鳩が入っている巣があることを示しています。

f:id:hama_DU:20161219005204p:plain

例

鳩の巣原理自体は一見当たり前に思えますが、「鳩」と「巣」をなにと捉えるかで様々な応用が効きます。まず準備運動として、鳩の巣原理を応用した事例をいくつか示して使い方をなんとなく眺めてみることにしましょう。

<1の位>

任意の11個の整数の中に、1の位が等しい数のペアが存在する。

<証明>

11個の整数を「鳩」、1の位に出現する10種類の数「0」「1」「2」・・・「9」を巣と考える。すると、鳩の巣原理により少なくとも2つの整数（鳩）が、同じ1の位の数（巣）に分類される。

<グラフの次数>

任意の2頂点以上の無向単純グラフに、次数の等しい頂点のペアが存在する。

<証明>

グラフの頂点数を n とおく。
次数が n-1 の（他のすべての頂点と繋がっている）頂点があるかないかで場合分けする。

ある場合
次数 0 の頂点が存在しないので、次数は 1 以上 n-1 以下で、n-1 種類。
これを n-1 個の巣、頂点を n 羽の鳩と捉えると、
鳩の巣原理により、ある 2 頂点は同じ次数を持つ。

ない場合
次数 n-1 の頂点が存在しないので、次数は 0 以上 n-2 以下で、n-1 種類。
これを n-1 個の巣、頂点を n 羽の鳩と捉えると、
鳩の巣原理により、ある 2 頂点は同じ次数を持つ。

<割り切れるペアを持つ部分集合>

集合 {1, 2, ... , 50} の大きさ 26 の任意の部分集合には、一方がもう片方を割り切るようなペアが存在する。

<証明>

{1, 2, ... , 50}を適切に分割すると、以下の性質を満たす
互いに素な部分集合を25個作れることを示す。

【部分集合に含まれる任意の異なる2数を選んだとき、一方が他方を割り切る】

1以上50以下の奇数はちょうど25個ある。それらを別々の集合に分ける。
偶数は2で割れるだけ割ると奇数になり、割る前の偶数たちをその奇数と同じ集合に入れる。
すると、

{1, 2, 4, 8, 16, 32}, {3, 6, 12, 24, 48}, {5, 10, 20, 40}, {7, 14, 28} ...

といった形の25個の集合が得られる。それぞれの集合が性質を満たすことは明らかである。

以上より、鳩は26羽、巣は25個となる。鳩の巣原理により、ある 2つの数が同じ集合に属する。つまり一方が片方を割り切ることが言える。

なんとなく使い方のイメージは掴めたでしょうか。ある問題で「鳩の巣原理が使えるかも？」と思ったら、「巣」と、それより多い「鳩」が何かをそれぞれ考えることで、「同じグループに属するペア」の存在を容易に示すことができるかもしれません。

競技プログラミングにおける鳩の巣原理

ここまでは数学の話でした。競技プログラミングで鳩の巣原理が使われる問題のパターンを幾つか紹介します。

解の存在保証

「指定された条件を満たす解を一つ」出す問題で、解の存在を保証するために使われることがあります。典型ですが、次の問題について考えてみましょう。

【合計がNの倍数になる部分列】

${N}$ 個の非負整数 ${A = \{a_{0}, a_{1}, ... , a_{n-1} \} }$ が与えられる。
${A}$ の空でない部分列を選んで、合計を ${N}$ の倍数にできるだろうか。
できる場合、その部分列を具体的に答えよ。できない場合、その旨を報告せよ。

${1 \leq N \leq 10^{6} }$
${1 \leq a_{i} \leq 10^{9}}$

${A}$ の先頭から ${0 \leq x \leq N}$ 個の和を ${ p_{x} }$ とおくと、 ${p}$ は ${N+1}$ 個の数値を持ちます。 ${p}$ とこれらを ${N}$ で割ったあまりを「鳩」「巣」と考えれば、必ず余りの数が等しい、異なる部分和がありますね！

f:id:hama_DU:20161218230101p:plain

よって、答えは必ず存在します。2つの部分和の差を取ると ${N}$ の倍数になるので、それを出力すればよいです。

探索範囲の上限の保証

解法に直接役立ちはしないものの、探索の範囲を限定できる証明に使われることがあります。少し古いですが、SRM485 Div1Medium の問題を紹介します。

【SRM485 Div1Medium RectangleAvoidingColoring】

${N \times M}$ のグリッドセルの幾つかのマス目が白か黒で塗られている。
残りのマス目を白か黒で塗りたい。その時、以下の条件を満たすようにする。

【グリッドのどの長方形を選んでも、4隅が同じ色にならない】

塗り方は何通りあるだろうか。

${1 \leq N \leq 50 }$
${1 \leq M \leq 50 }$

制約が大きく探索が難しそうに思えますが、結論を言ってしまうと 5x5 以上の大きさの場合は、必ず4隅が等しい長方形が存在することが示せます。すると、短い方の長さが4以下の場合だけを考えればよいので、bitDPなどで数え上げができます。

【証明】

大きさ5x5のグリッドの先頭の行に着目する。
鳩の巣原理より、そのうちの少なくとも3色は同じ色になる。
一般性を失わず、その色を白とできる。
(黒が3色以上あったとすると、白黒を反転させれば以下同文になる)
f:id:hama_DU:20161218215426p:plain

先頭の色が白の列を3つピックアップする。
先頭以外の4行について、行に含まれる白の数の最大数で場合分けする。

a: 白の数が2つ以上の行があるとき
該当する2列を抜き出せば、4隅が白の四角形ができる。

f:id:hama_DU:20161218231026p:plain

b: 白の数が最大で1つしかないとき
行に出現するパターンは、■■■、■■□、■□■、□■■ の4通りしかない。
そのうち、どれかの行が ■■■ である場合は、残りの3行と組み合わせて4隅が黒の四角形ができる。■■■ を含む行がない場合は、鳩の巣原理によりパターンが等しい行のペアがあり、4隅が黒の四角形ができる。

f:id:hama_DU:20161218215520p:plain

応用問題

最後に、鳩の巣原理を使って解ける面白い問題を発見したので紹介します。「鳩の巣原理を使う」こと自体はネタバレなのですが、「鳩」と「巣」が何になるかが難しいので、まだ解いてない人は是非考えてみてください。出典は Wunder Fund 2016-F : Double Knapsack です。editorialは出ていますが、後日解説を書きます。

2016/12/26追記: 書きました。

hama-du-competitive.hatenablog.com

【Wunder Fund 2016-F : Double Knapsack】

長さ ${N}$ の正の数列が 2 つ与えられる( ${A, B}$ とおく)。
数列に含まれる数は 1 以上 ${N}$ 以下の整数である。
${A, B}$ から空でない部分列をそれぞれ適当に選択したとき、合計が等しくなるようにできるだろうか？
もしできる場合は、具体的に構成せよ。できなければ、その旨を報告せよ。