Question

【題目】將方格表的每個方格任意填入或，然后允許進(jìn)行如下操作：每次任意選擇一行（或列），將這一行（或列）中的數(shù)全部變號.若無論開始時方格表的數(shù)怎樣填，總能經(jīng)過不超過次操作，使得方格表每一行中所有數(shù)的和、每一列中所有數(shù)的和均非負(fù).試確定的最小值.

Answer 1

【答案】

【解析】

若方格表每一行中所有數(shù)的和、每一列中所有數(shù)的和均非負(fù)，則稱方格表具有“性質(zhì)”.

首先證明：.

事實(shí)上，當(dāng)開始時方格表中的數(shù)均為時，為使方格表具有性質(zhì)，設(shè)對行進(jìn)行了次操作，對列進(jìn)行了次操作.

若，或，則結(jié)論成立；

若，且，則必有一行沒有進(jìn)行操作，從而，對列進(jìn)行的操作不少于次，即.

同理，.

故.

其次，對方格表中同一行（或列）進(jìn)行偶數(shù)次操作等價于沒有對這一行（或列）進(jìn)行操作，對方格表中同一行（或列）進(jìn)行奇數(shù)次操作等價于對這一行（或列）進(jìn)行了一次操作，因此，對方格表進(jìn)行的不同操作有種.

接下來證明：這些操作結(jié)果中使方格表中所有數(shù)的和最大的方格表必具有性質(zhì).

若不然，設(shè)其中有一行（或列）中的數(shù)的和小于零.則對這一行（或列）進(jìn)行一次操作，得到的方格表中所有數(shù)的和變大，與假設(shè)矛盾.

這說明，能經(jīng)過有限次操作使得方格表具有性質(zhì).

最后證明：可以經(jīng)過不超過次操作使得方格表具有性質(zhì).

由上面的論證，不妨設(shè)對行進(jìn)行操作，對列進(jìn)行操作可使方格表具有性質(zhì).

若，則結(jié)論成立；

若，則，并且對方格表中未進(jìn)行操作的行與列都進(jìn)行一次操作的結(jié)果與對前面行列進(jìn)行操作的結(jié)果相同，于是，可以進(jìn)行

次操作使方格表具有性質(zhì).

綜上，.