MathLabs

第2問

2012×2012の正方形格子の各マスに、0以上1以下の実数を入れる。格子を、格子の辺に平行な線で二つの空でない長方形のマス集合に分割する。どの分割でも少なくとも一方の長方形内の数の和が1以下であるとする。全ての数の和の最大値を求めよ。
ステップ 4/5: 列について繰り返す
前のステップ次のステップ
C(1,b−1)≤1,C(b+1,n)≤1,0≤ra,b≤1.C(1,b-1)\le1,\quad C(b+1,n)\le1,\quad 0\le r_{a,b}\le1.
詳しい解説

同様に列区間和Cを定義する。同じ議論により、bの上側ではなく左右の列の和がともに1以下となる列bを得る。a行b列のマスは1以下である。