Question

【题目】在一次数学会议上，任意两位数学家要么是朋友，要么是陌生人．在进餐期间，每位数学家在两个大餐厅中的其中一个就餐，每位数学家所在的餐厅中包含偶数个他（或她）的朋友．证明：数学家能被分到两个餐厅中的不同分法的数目是2的正整数次幕（即形如，其中，是某个正整数）．

Answer 1

【答案】见解析

【解析】

设参加会议的有位数学家．对用数学归纳法．

当时，该数学家可以在两个餐厅中的任何一个餐厅就餐．因此，有种不同的分法．

假设当有位数学家参加会议时，有种不同的分法．

当有位数学家时，分两种情形讨论．

（1）若存在一位数学家没有朋友，则该数学家可以在两个餐厅中任何一个餐厅就餐．于是，位数学家时不同分法的数目是位数学家参加会议时不同分法的数目的两倍．由归纳假设，知位数学家参加会议时不同分法的数目为．

（2）若每位数学家至少有一个朋友，再分两种情形讨论：一是存在一位数学家有奇数个朋友；二是每位数学家均有偶数个朋友．

（i）存在一位数学家，有奇数个朋友．

去掉，对于每一对的朋友，改变、之间的关系，即若、是朋友，则变为陌生人；若、是陌生人，则变为朋友．

先证明一个命题．

命题 去掉，对于每一对的朋友，改变、之间的关系．则满足条件的不同分法的数目不变．

证明 由假设，知在去掉之前就餐的餐厅中，他的朋友有偶数个．若这个偶数为0，则当离开此餐厅后，此餐厅中的数学家仍然满足条件；若这个偶数大于0，设为在此餐厅中的一个朋友，由假设，知在此餐厅中也有偶数个朋友，去掉后，在此餐厅中还剩下奇数个朋友．除了外，在此餐厅中有奇数个朋友，改变与的这奇数个朋友之间的关系，在此餐厅中朋友的数目变为偶数．

在另一餐厅中，有奇数个的朋友．改变的朋友之间的关系，则每个的朋友与偶数个数学家之间改变了关系，于是，这些数学家朋友数目的奇偶性不变．

此外，由于恰有一个餐厅中包含偶数个的朋友，故不含的每一个分法均可以由包含的一个分法唯一确定．

回到原题．

在这种情形下，位数学家不同分法的数目与位数学家不同分法的数目相同．由归纳假设，知位数学家不同分法的数目是2的正整数次幂．因此，位数学家不同分法的数目也是2的正整数次幂．

（ii）每位数学家均有偶数个朋友．

在这种情形下的每种分法均有每位数学家在两个餐厅中的朋友的数目为偶数．

设是任意一对朋友，去掉、，考虑每一对满足下述条件的数学家，其中，是的朋友，是的朋友．则改变、之间的关系．同理，若是的朋友，是的朋友，也改变、之间的关系．若、均是和的朋友，则、之间的关系改变两次，即、之间的关系没有改变．

接下来考虑不同于、的任意一位数学家及要选择的一个餐厅（在这种情形下，数学家的数目至少为3，即这样的三人组是存在的）．设在此餐厅中有位朋友，在此餐厅中有位朋友．则、均为偶数．当去掉、后，在此餐厅中要么与、要么与、要么与（是、在此餐厅中共同的朋友的数目）、要么与0位数学家之间的关系发生了改变（这分别依赖于仅是的朋友、仅是的朋友、既是A又是的朋友、既不是又不是的朋友）．

因为、均为偶数，所以，朋友的数目的奇偶性没有改变，仍为偶数．

由于不含、的每一个分法均可以由包含这对数学家的一个分法唯一确定：将、加入到其有奇数个朋友的餐厅中，然后改变所有的朋友和的朋友之间的关系，于是，在去掉之前和去掉之后建立了一个一—对应．

在这种情形下，位数学家不同分法的数目与位数学家不同分法数目相同．

由归纳假设，知位数学家不同分法的数目是2的正整数次幂．

因此，位数学家不同分法的数目也是2的正整数次幂．