减少-1的数量
有一个(2n+1)*(2n+1)的矩阵A=(Ai,j),元素为-1或1.你可对它进行如下操作若干次，找到2n+1个元素，满足任意两个不同行且不同列；然后将这2n+1个元素分别乘以-1。请描述一种策略，它总是能将矩阵A中-1的数量降到不超过2n。 首先证明， 对于任意选定的两行和两列，我们可以使用两次操作，使得除了这两行两列相交的位置符号发生变化以外，其它位置数字的符号都不改变。然后使用上面的结论，我们可以对矩阵进行依次变换，使得除了最后一行最后一列以外，其余位置都是+1.
然后假设最后一行前2n个数中有s个-1,最后一列前2那个数中有t个-1,不妨假设$s\le t$, 于是可以将它们的前s个-1按顺序一一匹配。
比如最后一行的前s个-1分别在$A(2n+1, u_i)$ ($1\le i \le s$), 最后一列的前t个-1分别在$A(v_i, 2n+1)$,(其中$1\le i \le t$).
于是我们对于每个i($1\le i \le s$),采用两次操作仅改变$A(u_i,v_i), A(2n+1,u_i), A(v_i,2n+1), A(2n+1,2n+1)$的符号。
于是全部操作完毕以后，最多还余下$t+1$个-1. 如果这时余下的-1数目还有2n+1个，正好每行都有一个-1，而且前s行的-1都不在最后一列而且各自在不同列，但是后面2n+1-s行的-1都在最后一列。
然后我们通过前面的交换方案，将最后一列的-1两两交换前面某个全1的列中，最后得到一个矩阵，正好有2n+1个-1，所有的-1都在不同的行，而且每列之多2个-1.
然后从这些-1中挑选尽量多的，使得每列最多挑选一个，于是至少会选择n+1个-1，然后补足一些1到2n+1个不同的行和列对它们进行符号改变，必然使得余下-1数目小于2n+1
页:
[1]