第2問

2012×2012の正方形格子の各マスに、0以上1以下の実数を入れる。格子を、格子の辺に平行な線で二つの空でない長方形のマス集合に分割する。どの分割でも少なくとも一方の長方形内の数の和が1以下であるとする。全ての数の和の最大値を求めよ。

ステップ 1/5: 達成例を示す

r_{a,b}=c_{a,b}=1\text{ on a central cross of five cells, and }0\text{ elsewhere}.

詳しい解説

一つのマスとその上下左右の四マスに1を置き、他を0とする。どの直線分割でも一方の側の和は高々1なので、総和5が達成される。