カントールの定理

カントールの定理 (Cantor's theorem)

無限集合を含む任意の集合 A の部分集合の集合 (= 冪集合) A^* の濃度は A より大きい.

\\\#A \lt 2^{\\\#A}

証明

  • 対角線論法により AA^* が 1 対 1 対応でない i.e. \#A \neq \#A^* であることを示す
  • かつ AA^* の要素が 1 対 1 対応であることから \#A \lt \#A^* であることを示す

A \rightarrow B: \{0, 1\} への 1 対 1 対応を与える写像 f を考えるとき,写像 f による像 b = f(a)b = 1 となる a \in A の集合は A^* の要素の 1 つとなる.
したがって,A^*b の取り方が異なる写像 f の集合と同一とみなせる.
この写像 f の集合と集合 A が 1 対 1 対応すると仮定し,a \in A の各 a_1, a_2, ...f \in A^* の各 f_{a_1}, f_{a_2}, ... がそれぞれ対応するとする (下表 fa 列).
例えば,a_1 を 1 に,a_2 を 0 に,...,a' を 0 に,... に写す写像 f_{a_2}a_2 と対応づける.

いま,写像 g:A^* \rightarrow A^*; 1 - fa(a) を定義する.
これは,各写像 f_{a_i} が写す a_i の値 (下表の赤色部分) を反転させてできる写像である.
写像 gA \rightarrow B: \{0, 1\}写像の 1 つ,つまり写像 f の 1 つだから,g = f_{a'} \ in A^* となる写像 f_{a'} が存在するはず.
しかし,写像 f_{a'} による a'写像f_{a'}(a') となるはずだが,写像 g による a'写像1 - f_{a'}(a') であるため,g \neq f_{a'} となり矛盾する.
よって f の集合と集合 A が 1 対 1 対応するという仮定は誤りであるから,両者は 1 対 1 対応とならない.
したがって \#A \neq \#A^*

f:id:espe0n:20201123114826p:plain

また,A^* の部分集合のうち,A の 1 つの要素からなる集合 {a} の集合は A の要素と 1 対 1 対応である.
以上より \#A \lt \#A^*

全然関係ないんですが,数式って Markdown 編集だと中央に表示できないんです?(HTML 編集で <center>[tex:]</center> ならできるって情報は見かけた -> tex内のエスケープをさらにもう 1 つ追加して <center></center> で囲ったら表示できた)

蟻本 : Evacuation (POJ No.3057)

蟻本 p.206 の Evacuation (POJ No.3057) のノート.

(時刻-ドア, 人) 間の二部グラフの最大マッチング = 全員が脱出するまでの時間 となる.
最大マッチングが全人数に満たない場合は impossible.

ドアの集合を D,人の集合を P とし,各 d_i \in D についてすべての p_i \in P までの最短距離を BFS で求める.
この距離が,p_id_i を使って脱出するときの最短時間となる.
得られた距離をもとにグラフを作成する.

コード
- C++ : https://github.com/1izard/algorithm-training/blob/master/Ant/chapter3/cpp/evacuation.cpp
- Python : https://github.com/1izard/algorithm-training/blob/master/Ant/chapter3/python/evacuation.py

for (int k = dist[dX[i]][dY[i]][pX[j]][pY[j]]; k <= N; ++k) は各時刻について走査.
dist[dX[i]][dY[i]][pX[j]][pY[j]] = 最短時刻で,この時刻以降この人はこのドアから任意の時刻に脱出できるので,脱出までに最も時間がかかった場合の時刻 N までインクリメントして (時刻-ドア,人) 間に辺をつなぎ続ける.

int D = dX.size();
int P = pX.size();
for (int i = 0; i < D; ++i) {
  for (int j = 0; j < P; ++j) {
    if (dist[dX[i]][dY[i]][pX[j]][pY[j]] >= 0) {
      for (int k = dist[dX[i]][dY[i]][pX[j]][pY[j]]; k <= N; ++k) {
        add_edge((k - 1) * D + i, N * D + j);
      }
    }
  }
}

add_edge((k - 1) * D + i, N * D + j)(k - 1) * D + iN * D + j を, 例えば 10 進数 23 を 2 * 10 + 3 と基数に基づいて考えるように,ドアの総数 D を基数と捉えると各時刻 t1, t2, t3, ... について各ドアを下の表のような順で頂点としていることがわかる.

f:id:espe0n:20201120002112p:plain

例えば次のような入力の場合,グラフはこんな感じになる.

4 4
XXXX    
D..X    d1 p1 p2
X..D       p3 p4 d2
XXXX

f:id:espe0n:20201120001906p:plain

最後に t1, t2, ..., tN までの時刻の全てのドアと人をマッチングしていく.
早い時刻から可能な限りドアと人をマッチングさせるので,初めてマッチング数が人数 P に等しくなったときが最短時刻になる.

int cnt = 0;
memset(match, -1, sizeof(match));
for (int u = 0; u < N * D; ++u) {
  memset(used, 0, sizeof(used));
  if (dfs(u)) {
    if (++cnt == P) {
      printf("%d\n", u / D + 1);
      return;
    }
  }
}
printf("impossible\n");