在家吃饭解答

constant

你家有两张餐桌，一张坐10人，一张坐9人。19个人吃饭。你想要任意两个人都在同一桌至少吃一次饭。最少要几次？如果20个人和两张11人和9人的餐桌呢？
 
野菜花已经完全解决了这个问题。为了多挣钱，把我的解答也贴在这里。

不难看出4次一定够了，而且大部分时候3次也够，真正要证明的是什么时候3次不够。www.ddhw.com

设两桌各坐m人和n人，且m>=n。每个人按每顿饭坐的桌子分配一个三元数组，例如（1，1，2），（2，1，1）。（最近怎么老是三元数组？）一共有8种可能，但一个数组和它的补数组（例如（1，1，2）和（2，2，1））不能并存。所以只有4个。把这4组人记为A，B，C，D。可能的坐法有

1。ABC，D；ABD，C；ACD，B；
2。AB，CD；AC，BD；AD，BC；
3。AB，CD；AC，BD；BC，AD；

这三种坐法中，第一种要求m>=2n，第二种要求n是偶数，第三种要求m是偶数。也就是说，当m<2n，且m和n都是奇数时3次不够。其它情况从上面可以看出3次够了。

用同样方法可以证明两次一定不够，因为只能分成两组。

www.ddhw.com

 

寒潭清

  向constant看齐,努力做挣分能手