プリズム

数理的アプローチ


$Tau( \frac{1}{2} \sum_{j \in N}{d_j} ; d) = \frac{1}{2} d$

投稿日時:

最終更新日時:

タグ:

(証明)

$N=\{1,\ldots,n\}, d=(d_1,\ldots,d_n), E=\frac{1}{2} \sum_{j \in N}{d_j}$とおく。また、$d_1 = \max \{ d_1,\ldots,d_n \}$となるように$d_j (j \in N)$を並べ替えておく。

$n=1$の時、$Tau(E;d)=\frac{1}{2}d$は明らかに成立する。

$n \ge 2$の時を考察する。$d_j > 0 (j \in N)$と$2E = \sum_{j \in N}{d_j}$ より、$d_j \lt E (j \in \{ 2, \ldots, n \})$である。従って、$d’=(d’_1, \ldots, d’_n), d’_j = \min \{ E, d_j \} (j \in N)$とおけば、$d’=(\min\{E,d_1\}, d_2, \ldots, d_n)$となる。$E’ = \frac{1}{2} \sum_{j \in N}{d’_j}$とおけば、$Prop(E, d’) = \frac{E}{E’} \frac{1}{2} d’$となる。ここで、$E \ge E’$であるので、$Prop_j (E, d’) \ge \frac{1}{2} d_j (j \in \{ 2, \ldots, n \})$である。

ゆえに、$Tau(E;d) = \left(E – \frac{1}{2} \sum_{j \in \{ 2, \ldots, n \}}{d_j}, \frac{1}{2} d_2, \ldots, \frac{1}{2} d_n \right) = \frac{1}{2} d$となる。(証明終わり)