12人,每周到一餐馆一次.分三桌,每桌4人.要求任意两人均至少有一次坐在同一坐上.问聚餐至少要进行几周?

Question

12人,每周到一餐馆一次.分三桌,每桌4人.要求任意两人均至少有一次坐在同一坐上.问聚餐至少要进行几周?

Answer 1

为探索解法，先把问题简化：
8人,每周到一餐馆一次.分两桌,每桌4人.要求任意两人均至少有一次坐在同一桌上.问聚餐至少要进行几周?
从8个元素中取2个元素的组合数C(8，2)=28，
从4个元素中取2个元素的组合数C(4，2)=6，
每次聚餐有6*2=12对在同一桌上，
∴聚餐至少要进行28/12≈3周，事实上，把8人编码，三次聚餐的坐法如下：
（1234），（5678）；
（1456），（2378）；
（1478），（2356）：即可满足要求。
原题
从12个元素中取2个元素的组合数C(12，2)=66，
从4个元素中取2个元素的组合数C(4，2)=6，
每次聚餐有6*3=18对在同一桌上，
∴聚餐至少要进行66/18≈4周.
如何实现，留给您练习，可以吗？