6

一位同事带着一个有趣的问题来找我，一个与她所在的“城里新人”小组有关的实际问题。

在接下来的 4 天里，每天有 18 位朋友想分组共进晚餐。规则如下：

  1. 每天，该小组将分为 4 组，每组 4 人，一组 2 人。
  2. 任何一对人在 4 天内最多只能见面一次。
  3. 任何给定的人最多只能成为大小 2 组的一部分。

暴力递归搜索一组有效的组分配显然是不切实际的。我已经提出了一些简单的逻辑来尽快修剪树的某些部分，但还不足以使其实用。

实际上，我开始怀疑遵守所有规则可能是不可能的，但我想不出一个组合论据来解释为什么会这样。

有什么想法吗？

4

1 回答 1

4

可以使用两个相互正交的 4 阶拉丁方格安排 16 个朋友 4x4 共 4 晚。将每个朋友分配到 4x4 网格中的不同位置。第一天晚上，逐行分组。第二，按列分组。第三，按拉丁方#1 中的相似条目分组（4x4 示例中的卡片等级）。第四，按拉丁方#2 中的类似条目分组（4x4 示例中的卡片套）。实际上，仿射平面构造产生了三个相互正交的拉丁方格，因此可以安排第五晚，确保每对朋友恰好见面一次。

也许可以延长 16 日的日程，利用未使用的第五晚的自由。

编辑：这是 5 晚 16 人的时间表。每一行都是一个晚上。每列是一个人。条目是他们被分配到的组。

[0, 0, 0, 0,  1, 1, 1, 1,  2, 2, 2, 2,  3, 3, 3, 3]
[0, 1, 2, 3,  0, 1, 2, 3,  0, 1, 2, 3,  0, 1, 2, 3]
[0, 1, 2, 3,  1, 0, 3, 2,  2, 3, 0, 1,  3, 2, 1, 0]
[0, 2, 3, 1,  1, 3, 2, 0,  2, 0, 1, 3,  3, 1, 0, 2]
[0, 3, 1, 2,  1, 2, 0, 3,  2, 1, 3, 0,  3, 0, 2, 1]
于 2012-09-25T17:24:26.087 回答