7*7的方格,每格最多放一个棋子,至少需要几枚,才能保证必有两行两列所有棋子加起来>=7.两行两列求...
Tạo vào: 19 tháng 8, 2026
Trả lời bằng GPT-5.6 Thinking bởi Chat01
Tạo vào: 19 tháng 8, 2026
Trả lời bằng GPT-5.6 Thinking bởi Chat01
7*7的方格,每格最多放一个棋子,至少需要几枚,才能保证必有两行两列所有棋子加起来>=7.两行两列求并再数棋子。
pythonimport scipy, numpy as np, math, itertools, sys, os, statistics print(scipy.__version__) try: from scipy.optimize import milp, LinearConstraint, Bounds print("milp available") except Exception as e: print(e)
pythonx=np.zeros((7,7),int) edges=[(0,0),(0,1),(1,1),(1,2),(2,2),(2,0),(3,3),(4,4),(5,5),(6,6)] for a,b in edges:x[a,b]=1 mx=0; arg=None for rs in pairs: for cs in pairs: u=sum(x[i,j] for i in range(7) for j in range(7) if i in rs or j in cs) if u>mx: mx=u;arg=(rs,cs) mx,arg (np.int64(6), ((0, 1), (0, 2)))
答案是 11 枚。
把棋盘上的棋子看成一个 的 0-1 表。我们要证明两件事:11 枚一定能找到两行两列,其并集里至少有 7 枚;而 10 枚还不一定。
反设放了 11 枚,但任取两行两列,它们的并集都至多有 6 枚。
取棋子最多的两行,设这两行共有 枚。显然 ,否则随便再取两列就已经至少 7 枚。
如果 ,那么取这两行后,再取任意两列时,这两列在这两行以外最多只能再贡献
枚棋子。因此两行以外总共至多有 1 枚棋子,于是全盘至多
与 11 枚矛盾。
另一方面,如果 ,由于这是棋子最多的两行,第二多的一行至多有 1 枚,所以全盘最多
也不可能有 11 枚。
所以只能是
删掉这两行,还剩
枚。对任意两列,这两列在所删两行之外的棋子数至多为
7 枚棋子分布在 7 列中,而且任意两列合计至多 2 枚。这迫使每列恰好有 1 枚剩余棋子。
完全对称地分析列,可以得到:棋盘上每行、每列最多都是 2 枚,而且行的度数必为
因此有 4 行各有 2 枚棋子。
现在任取其中两条“2 枚行”。前面的论证告诉我们:删去这两行后,每一列恰好还剩 1 枚。因此这两行不能在同一列都有棋子,否则该列会有
枚,与“每列最多 2 枚”矛盾。
所以这 4 条“2 枚行”中,任意两条所占的列都必须完全不相交。
但它们一共需要
个互不相同的列,而棋盘只有 7 列,矛盾。
所以放 11 枚时,一定存在两行两列,其并集中至少有 7 枚棋子。
下面这个摆法有 10 枚:
前三行、前三列中放成一个 6 环,另外四枚分别放在 。
可以检查:
因此这 10 枚棋子中,任何两行两列的并集都不满 7 枚。
所以最少需要
枚。