数学研发论坛

 找回密码
 欢迎注册
查看: 104|回复: 1

[讨论] 减少-1的数量

[复制链接]
发表于 2020-9-21 07:22:54 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
有一个(2n+1)*(2n+1)的矩阵A=(Ai,j),元素为-1或1.你可对它进行如下操作若干次,找到2n+1个元素,满足任意两个不同行且不同列;然后将这2n+1个元素分别乘以-1。请描述一种策略,它总是能将矩阵A中-1的数量降到不超过2n。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-9-21 08:02:43 | 显示全部楼层
首先证明, 对于任意选定的两行和两列,我们可以使用两次操作,使得除了这两行两列相交的位置符号发生变化以外,其它位置数字的符号都不改变。
然后使用上面的结论,我们可以对矩阵进行依次变换,使得除了最后一行最后一列以外,其余位置都是+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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-10-27 18:04 , Processed in 0.059418 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表