凸最適化・組合せ最適化の問題

難易度 4大学院入試の難問レベル大学院数学凸最適化・組合せ最適化

$F_{2} = {0, 1}$ を 2 元体とし、 $E = F_{2}^{4} ∖ {0}$ （15 個のベクトルからなる集合）とする。 $E$ 上のマトロイド $M$ を、部分集合 $I \subseteq E$ が $F_{2}$ 上 1 次独立であるとき、かつそのときに限り独立集合であるものとして定める（ $M$ の階数は $4$ ）。 $M^{*}$ を $M$ の双対マトロイド、すなわち $M$ の基の補集合 $E ∖ B$ 全体を基の族とするマトロイドとする。

ベクトル $v \in E$ の成分のうち $1$ であるものの個数を $hw (v)$ と書き、重み $w : E \to Z$ を
$w (v) = ⎩ ⎨ ⎧ 123 (hw (v) = 2, 4) (hw (v) = 1) (hw (v) = 3)$
で定める。 $M^{*}$ の基 $B^{*}$ の重みを $w (B^{*}) = \sum_{v \in B^{*}} w (v)$ とするとき、 $w (B^{*})$ が最大となる $M^{*}$ の基 $B^{*}$ の個数を求めよ。

この問題で使うもの

双対マトロイドと切り詰め（説明と入口の問題）
貪欲法による最大重み基（説明と入口の問題）
マトロイドの独立集合・基・階数（説明と入口の問題）
組合せ（説明と入口の問題）

この問題を解けるようになるまで（38 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

$M^{*}$ の基と $M$ の基は補集合で対応し、 $w (B^{*}) = w (E) - w (E ∖ B^{*})$ となる。 $M^{*}$ の最大重み基は、 $M$ のどんな基に対応するか考えよう。

ヒント 2

基 $B$ が最小重み基であることは、各しきい値 $t$ で $∣ B \cap {w \leq t} ∣ = r ({w \leq t})$ が成り立つことと同値である。重み $1$ の元全体は、どんな部分空間の非零ベクトル全体になっているか。

ヒント 3

重み $1$ の元全体は $x_{1} + x_{2} + x_{3} + x_{4} = 0$ で定まる 3 次元部分空間の非零ベクトル 7 個で、階数は $3$ 。最小重み基は、そこから 1 次独立な 3 元を選び、重み $2$ の元を 1 つ加えたものになる。それぞれの選び方の数を数えよう。

答えと解説

答えを見る

112

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

双対への言い換え. $B^{*}$ が $M^{*}$ の基であることと $B = E ∖ B^{*}$ が $M$ の基であることは同値で、
$w (B^{*}) = w (E) - w (B)$
である。したがって $w (B^{*})$ が最大となる $M^{*}$ の基は、 $w (B)$ が最小となる $M$ の基 $B$ の補集合とちょうど 1 対 1 に対応する。求める個数は「 $M$ の最小重み基の個数」に等しい。

重みの分類. $E$ の元を分類すると
- $hw (v)$ が偶数（ $2$ または $4$ ）のもの: $(2 4) + 1 = 7$ 個、重み $1$
- $hw (v) = 1$ のもの: $e_{1}, e_{2}, e_{3}, e_{4}$ の $4$ 個、重み $2$
- $hw (v) = 3$ のもの: $4$ 個、重み $3$

偶数重みのベクトルに $0$ を加えた集合は $H = {x \in F_{2}^{4} : x_{1} + x_{2} + x_{3} + x_{4} = 0}$ であり、これは 3 次元部分空間である。よって $E_{1} = H ∖ {0}$ （重み $1$ の元全体）について $r (E_{1}) = 3$ 。また $e_{i} \in / H$ なので $r (E_{1} \cup {e_{1}, \dots, e_{4}}) = 4$ 。

最小重み基の特徴づけ. マトロイドの基 $B$ が最小重み基であるための必要十分条件は、すべての $t$ について
$∣ B \cap {v : w (v) \leq t} ∣ = r ({v : w (v) \leq t})$
が成り立つことである（貪欲法の正当性から、各しきい値の集合をできるだけ多く使う基がちょうど最適基である）。
- $t = 1$ : $∣ B \cap E_{1} ∣ = 3$ 。 $B \cap E_{1}$ は 1 次独立な 3 元集合なので、 $M ∣ E_{1}$ （ $H$ の非零ベクトル 7 個のなすファノマトロイド）の基である。
- $t = 2$ : $∣ B \cap (E_{1} \cup {e_{1}, \dots, e_{4}}) ∣ = 4$ 。よって $B$ の残り 1 元は $e_{1}, \dots, e_{4}$ のいずれかである。

逆に、 $E_{1}$ から 1 次独立な 3 元 ${a, b, c}$ （これは $H$ の基）を選び、 $e_{i}$ を 1 つ加えると、 $e_{i} \in / H = span {a, b, c}$ より ${a, b, c, e_{i}}$ は $M$ の基で、重みは $1 + 1 + 1 + 2 = 5$ となり最小である。

個数の計算. $M ∣ E_{1}$ の基の個数は、 $E_{1}$ の 3 元部分集合 $(3 7) = 35$ 個から、従属なもの（ ${a, b, a + b}$ の形、すなわち $H$ の 2 次元部分空間の非零元 3 個）を除いたものである。 $H ≅ F_{2}^{3}$ の 2 次元部分空間は $7$ 個なので、基は $35 - 7 = 28$ 個。

$e_{i}$ の選び方は $4$ 通りなので、 $M$ の最小重み基は $28 \times 4 = 112$ 個。

（参考: $w (E) = 7 \cdot 1 + 4 \cdot 2 + 4 \cdot 3 = 27$ なので、 $M^{*}$ の基の重みの最大値は $27 - 5 = 22$ である。）

よって求める個数は $112$ 。

別解

$M^{*}$ の基は $M$ の基 $B$ の補集合 $E ∖ B$ で、 $w (E ∖ B) = w (E) - w (B)$ 。よって $w (B^{*})$ が最大となる基の個数は、 $M$ の基 $B$ （ $F_{2}^{4}$ の基となる 4 個のベクトルの集合）のうち $w (B)$ が最小となるものの個数に等しい。

重みの内訳: $hw = 1$ が 4 個（重み 2）、 $hw = 2$ が 6 個（重み 1）、 $hw = 3$ が 4 個（重み 3）、 $hw = 4$ が 1 個（重み 1）。

重み 1 のベクトルは $hw$ が偶数のもの 7 個で、これらは偶数重みベクトル全体の 3 次元部分空間 $W$ の非零元全体（ファノ平面の 7 点）。 $W$ の元は高々 3 個しか 1 次独立にできないので、基 $B$ に含まれる重み 1 のベクトルは高々 3 個。残りの 1 個は $W$ の外（奇数重み）で、重みは $hw = 1$ なら 2、 $hw = 3$ なら 3。したがって $w (B) \geq 3 \cdot 1 + 2 = 5$ で、等号は「 $W$ の 1 次独立な 3 元 + $hw = 1$ のベクトル 1 個」のときに限る（重み 1 が 2 個以下だと $w (B) \geq 1 + 1 + 2 + 2 = 6$ ）。

個数: $W$ の 3 元で 1 次独立なもの = 7 点から 3 点を選ぶ $(3 7) = 35$ 通りから共線な 7 組（ファノ平面の直線）を除いた 28 通り。 $hw = 1$ のベクトルは 4 通りで、 $W$ の外にあるので 3 元と常に 1 次独立。よって $28 \times 4 = 112$ 。

検算: $W$ の基の個数 $∣ G L_{3} (F_{2}) ∣/3! = 168/6 = 28$ と一致。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
プログラムで答えを計算し直し、一致を確認しました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる