将 1-12 分组为 4 组，重复次数最少

Question

假设有 12 个人每周都想聚在一起玩游戏。 他们4人一组，想玩偶数次

4 周后，似乎没有任何组合可以让每个球员都与所有 11 个对手比赛。我还没能证明这一点，但我还没有找到解决办法。

那么N的最小值是多少才能保证在(N*4)周后每个玩家都至少和所有其他玩家一起玩过N次？ N=2可以吗？

Answer 1

这与讨论您正在查看的内容的 Social Golfer Problem -- an unsolved problem in mathematics. Here's a relevant post from math.stackexchange 非常相似。如果您关注的是它背后的数学原理，您可能想在那里重新发布它，因为它不太适合 Whosebug。

如果您只是关心试图解决它的算法（并且不想只是暴力破解它），this paper presents a bunch approaches to solving problems of this type. It's a pretty dense read, but it's a place to start. There's also a list of explicit solutions 在某些情况下，但我不知道它有多大用处将给你（因为问题略有不同）。

如果您真的只是想证明 N 的下限，因为它是离散的并且您正在检查的情况相对较小，那么您最好的选择可能是组合一个强力搜索算法，并递增 N直到成功。

最后，这里有一些可能有用也可能没用的其他链接： http://www.bridgeguys.com/Conventions/movements_for_bridge.html http://www.jdawiseman.com/papers/tournaments/individual-pairs/individual-pairs.html http://www.csplib.org/Problems/prob010/
https://www.metalevel.at/sgp/

Answer 2

感谢指点 - 他们给了我想要的答案。

简单来说，如您所说，对于N=1，无解。 对于 11 轮的 12 名玩家存在解决方案，例如 http://www.jdawiseman.com/papers/tournaments/individual-pairs/ip-pure_12.html - 这实际上更进一步并断言每个玩家与其他玩家合作一次，并反对他们两次。这有效地涵盖了 N=3

的情况

N=3 的解的存在和 N=1 的解的缺乏几乎消除了 N=2 的解的可能性。