この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

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

難易度 2大学院の講義の演習問題レベル証明問題大学院数学凸最適化・組合せ最適化

$n \geq 2$ を整数、 $k$ を $1 \leq k \leq n - 1$ を満たす整数とし、
$P = {x \in R^{n} : 0 \leq x_{i} \leq 1 (i = 1, \dots, n), i = 1 \sum n x_{i} = k}$
とおく。ここで $P$ の頂点とは、 $P$ の端点、すなわち「 $y, z \in P$ かつ $x = \frac{1}{2} (y + z)$ ならば $y = z = x$ 」を満たす点 $x \in P$ のことをいう。

$P$ の頂点全体が、成分がすべて $0$ または $1$ で、 $1$ の個数がちょうど $k$ 個であるベクトル全体と一致することを示し、特に $P$ の頂点の個数が $(k n)$ であることを証明せよ。

この問題で使うもの

多面体の頂点（基底解）（説明と入口の問題）
組合せ（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

頂点（端点）全体が ${0, 1}$ ベクトルで $1$ が $k$ 個のもの全体と一致することを、2 つの包含に分けて示しましょう。

ヒント 2

$0$ - $1$ ベクトルが端点であることは、 $y_{i} + z_{i} = 0$ や $y_{i} + z_{i} = 2$ と制約 $0 \leq y_{i}, z_{i} \leq 1$ から各成分が決まることを使います。逆向きでは、 $0 < x_{i} < 1$ となる成分が少なくとも 2 つあることが鍵です。

ヒント 3

$0 < x_{j} < 1$ 、 $0 < x_{l} < 1$ となる $j \neq = l$ があれば、 $x \pm ε (e_{j} - e_{l})$ は小さい $ε > 0$ に対して成分和を変えずに $P$ に留まります。分数成分がただ 1 つだと、成分和が整数 $k$ であることに矛盾します。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

$1$ が $k$ 個の $0$ - $1$ ベクトル $v$ が $P$ に属し、 $v = \frac{1}{2} (y + z)$ のとき $v_{i} = 0, 1$ それぞれの場合に $y_{i} = z_{i} = v_{i}$ となることを、制約 $0 \leq y_{i}, z_{i} \leq 1$ から示している（3 点）
$x \in P$ が $0$ - $1$ ベクトルでなければ $0 < x_{i} < 1$ の成分があり、成分和が整数 $k$ であることからそのような成分が少なくとも 2 つあることを示している（3 点）
2 つの分数成分 $j, l$ を使って $x \pm ε (e_{j} - e_{l})$ のような $P$ 内の相異なる 2 点を作り、 $ε$ の取り方で制約が保たれることを確かめ、 $x$ が頂点でないと結論している（3 点）
頂点全体が上の $0$ - $1$ ベクトル全体と一致することから、 $1$ の位置の選び方として個数 $(k n)$ を導いている（1 点）

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

模範解答を読む

$V = {v \in {0, 1}^{n} : \sum_{i} v_{i} = k}$ とおく。「(A) $V$ の各点は $P$ の頂点である」「(B) $P$ の頂点は $V$ に属する」の 2 つを示せば、頂点全体は $V$ と一致する。

(A) $V \subseteq {P の頂点}$ 。 $v \in V$ をとる。成分は $0$ か $1$ で和は $k$ なので $v \in P$ 。 $y, z \in P$ で $v = \frac{1}{2} (y + z)$ とする。各 $i$ について:
- $v_{i} = 0$ のとき、 $y_{i} + z_{i} = 2 v_{i} = 0$ であり、 $y, z \in P$ より $y_{i} \geq 0$ 、 $z_{i} \geq 0$ 。非負の 2 数の和が $0$ だから $y_{i} = z_{i} = 0$ 。
- $v_{i} = 1$ のとき、 $y_{i} + z_{i} = 2$ であり、 $y_{i} \leq 1$ 、 $z_{i} \leq 1$ 。したがって $y_{i} = 2 - z_{i} \geq 1$ となり $y_{i} = 1$ 、同様に（ $y$ と $z$ の役割を入れ替えて） $z_{i} = 1$ 。
どちらの場合も $y_{i} = z_{i} = v_{i}$ なので $y = z = v$ 。よって $v$ は $P$ の頂点である。

(B) ${P の頂点} \subseteq V$ 。 対偶を示す。 $x \in P$ が $V$ に属さないと仮定し、 $x$ が頂点でないことを示す。 $x \in P$ で $x \in / V$ ならば、 $x$ のある成分は $0$ でも $1$ でもない（もしすべての成分が $0$ か $1$ なら、 $\sum_{i} x_{i} = k$ より $x \in V$ となってしまう）。 $F = {i : 0 < x_{i} < 1}$ とおくと $F \neq = \emptyset$ 。

$∣ F ∣ \geq 2$ であることを示す。 $∣ F ∣ = 1$ 、 $F = {j}$ と仮定すると、 $j$ 以外の成分はすべて $0$ か $1$ なので $\sum_{i \neq = j} x_{i}$ は整数 $m$ であり、 $x_{j} = k - m$ は整数となる。これは $0 < x_{j} < 1$ に反する。よって $F$ は相異なる 2 つの添字 $j, l$ を含む。

$ε = min {x_{j}, 1 - x_{j}, x_{l}, 1 - x_{l}}$ とおくと $ε > 0$ 。 $e_{i}$ を第 $i$ 標準基底ベクトルとし、
$y = x + ε (e_{j} - e_{l}), z = x - ε (e_{j} - e_{l})$
とおく。 $y, z$ は $j, l$ 以外の成分が $x$ と同じで、 $y_{j} = x_{j} + ε \leq 1$ 、 $y_{l} = x_{l} - ε \geq 0$ 、 $z_{j} = x_{j} - ε \geq 0$ 、 $z_{l} = x_{l} + ε \leq 1$ （ $ε$ の定め方による）であり、各成分は $[0, 1]$ に入る。また $e_{j} - e_{l}$ の成分和は $0$ なので $\sum_{i} y_{i} = \sum_{i} z_{i} = k$ 。よって $y, z \in P$ で、 $x = \frac{1}{2} (y + z)$ 、かつ $y - z = 2 ε (e_{j} - e_{l}) \neq = 0$ より $y \neq = z$ 。したがって $x$ は頂点ではない。これで (B) が示された。

個数。 (A)(B) より $P$ の頂点全体は $V$ に一致する。 $V$ の元は、 $n$ 個の座標のうち値 $1$ をとる $k$ 個の座標の選び方と 1 対 1 に対応するので、 $∣ V ∣ = (k n)$ 。

以上により、 $P$ の頂点は $1$ をちょうど $k$ 個もつ $0$ - $1$ ベクトル全体であり、その個数は $(k n)$ である。

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

この問題で使うもの

ヒント

採点の観点と模範解答

次のおすすめ

この問題の確認

間違いを報告する

関連する問題