MathLabs

第2問

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

四つの互いに素な帯と交差マスが格子全体を覆う。各帯の和は1以下、交差マスも1以下なので全体は5以下である。達成例と合わせて最大値は5。