n を正の整数とする。(n+1)×n 型に並んだ n(n+1) 個の部屋がある。隣り合う二部屋の間には扉が一つある。扉の部分集合を選んで施錠し、次を満たす二部屋 S、G が存在するようにする方法の数を求めよ。
(i) S は第 1 行、G は第 (n+1) 行にある。
(ii) 施錠されていない扉のみを使って S から G に到達できる。
f は G の辺の 2n2+(n−1)2 個の部分集合上の全単射であり、到達可能な H をそれぞれ到達不可能な f(H) と対にするので、到達可能な部分集合と到達不可能な部分集合は互いに全単射をなし、2n2+(n−1)2 個の部分集合全体を二分する。よってちょうど 2n2+(n−1)2−1 個の部分集合が到達可能である。