第6問

A=(a_{ij})

(

i,j=1,2,\ldots,n

) を非負整数要素の正方行列とする。

a_{ij}=0

ならば第

i

行と第

j

列の要素の和が少なくとも

n

であると仮定する。行列の全要素の和が少なくとも

n^2/2

であることを証明せよ。

ステップ 7/7: ブロックの評価を結合する

2S=2X+2Y+2Z\ge(2X+Y)+Y+Z\ge kn+k(n-k)+(n-k)^2=n^2

詳しい解説

最後に $2S=2X+2Y+2Z=(2X+Y)+Y+Z$ 。3つの評価を使うと $2S\ge kn+k(n-k)+(n-k)^2=n^2$ 、従って $S\ge n^2/2$ 。