鳩の巣原理
鳩の巣原理は計算機科学の分野でも証明に使われる。
ハッシュテーブルにおいて想定されるキーの種類がテーブルの配列長を上回る場合、テーブルのインデックスが衝突しえないような値を出力するハッシュ関数(完全ハッシュ関数)は存在しないということが、この原理によって証明できる。
可逆圧縮アルゴリズムの圧縮処理後にデータサイズが小さくなる入力データが存在する場合、圧縮処理後にデータサイズが大きくなる入力データも必ず存在することが、鳩の巣原理を用いて証明できる。具体的には下記の通り。
「圧縮処理後にデータサイズが小さくなる入力データが存在し、圧縮処理後にデータサイズが大きくなる入力データが存在しない」と仮定する。
圧縮処理後にデータサイズが小さくなる入力データのうち、最も小さい入力データをFとし、そのデータサイズをMとする。Fの圧縮処理後のデータサイズをNとする(MとNの単位はビット)。
圧縮処理後にデータサイズが小さくなるため、N < Mである。さらに圧縮処理後にデータサイズが大きくなる入力データが存在しないため、Nビットのデータは圧縮処理後もNビットとなる。
Nビットのデータは2種類ある。前述のNと合わせ、圧縮処理後にNビットとなるデータは少なくとも2+1種類存在する。
しかしNビットのデータが2種類しかないので、鳩の巣原理により少なくとも2種類のデータが圧縮後同じデータになり、解凍が不可能(どちらに戻すべきか判別できない)である。
したがって最初の仮定は誤りであり、「圧縮処理後にデータサイズが小さくなる入力データが存在しない」(可逆圧縮アルゴリズムではない)か「圧縮処理後にデータサイズが大きくなる入力データが存在する」となる。