問題はこちら (Aizu Online Judge)
全然わからないのでインターネットを検索すると，「Bobが勝つ $\iff$ 最大マッチング数がM」であるから最大マッチング数を求めれば良い，という内容の記事が見つかった．なるほどそうなのか...．
詳しい証明はついていないようだが，多分次のようになるのだろうと思った．
($\Leftarrow$)
Bob の戦略としては，最初に M マッチをひとつ固定しておいて，Alice の指定した点に対して，それとマッチする点を答えれば良い．
($\Rightarrow$)
最大マッチングがMでないとして，Aliceの戦略を作る．Aliceが選択する点 (Bobの失策) の集合を U, Bobが選択する点 (Aliceの失策) の集合を V，2部グラフのエッジ (直接関係するAliceとBobの失策の組) の集合を $E$ ($\subseteq U \times V$) とする．記法を一つ導入して，$A \subseteq U$ に対して，$AE = \{v \in V \mid (a,v) \in E \text{ for some } a \in A\}$ と書くことにする．
Hallの定理 より，$|XE| < |X|$ なる $X\subseteq U$ が存在する．このような $X$ のうちで個数最小のものを1つとる (その個数を$k$とする)．また，$x \in X$ を一つ取り，$X' = X - \{x\}$，$Y = X'E$ とする．$X$の最小性より，Hallの定理を今度は$X'$に対して用いると，$X'$ と $Y$ の間で $k-1$ マッチングが存在することがわかる．$k > |XE| \geq |X'E| \geq |X'| = k - 1$ より $|XE| = |X'E|$．したがって，$XE = X'E = Y$．とくに $(x, y) \in E$ なら，$y \in Y$ である．
したがって，Aliceの戦略としては，以下のようにすれば良い．$X'$ と $Y$ の間の $k-1$ マッチングを一つ固定する．初手は $x$ を選択する．Bob が次の手 $y$ を取れるとすれば，$y \in Y$ であるから，マッチングに従って$X'$の要素を選択できる．以下，Bobが取る手は必ず$Y$の要素になるので，マッチングに従って$X'$の要素を選択する．(終)
