Question

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

Answer 1

【答案】

【解析】

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

首先證明：.

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

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

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

同理，.

故.

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

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

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

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

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

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

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

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

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

綜上，.