Question

【題目】在一次數(shù)學會議上，任意兩位數(shù)學家要么是朋友，要么是陌生人．在進餐期間，每位數(shù)學家在兩個大餐廳中的其中一個就餐，每位數(shù)學家所在的餐廳中包含偶數(shù)個他（或她）的朋友．證明：數(shù)學家能被分到兩個餐廳中的不同分法的數(shù)目是2的正整數(shù)次幕（即形如，其中，是某個正整數(shù)）．

Answer 1

【答案】見解析

【解析】

設參加會議的有位數(shù)學家．對用數(shù)學歸納法．

當時，該數(shù)學家可以在兩個餐廳中的任何一個餐廳就餐．因此，有種不同的分法．

假設當有位數(shù)學家參加會議時，有種不同的分法．

當有位數(shù)學家時，分兩種情形討論．

（1）若存在一位數(shù)學家沒有朋友，則該數(shù)學家可以在兩個餐廳中任何一個餐廳就餐．于是，位數(shù)學家時不同分法的數(shù)目是位數(shù)學家參加會議時不同分法的數(shù)目的兩倍．由歸納假設，知位數(shù)學家參加會議時不同分法的數(shù)目為．

（2）若每位數(shù)學家至少有一個朋友，再分兩種情形討論：一是存在一位數(shù)學家有奇數(shù)個朋友；二是每位數(shù)學家均有偶數(shù)個朋友．

（i）存在一位數(shù)學家，有奇數(shù)個朋友．

去掉，對于每一對的朋友，改變、之間的關(guān)系，即若、是朋友，則變?yōu)槟吧�人；�?/span>、是陌生人，則變?yōu)榕笥眩?/span>

先證明一個命題．

命題 去掉，對于每一對的朋友，改變、之間的關(guān)系．則滿足條件的不同分法的數(shù)目不變．

證明 由假設，知在去掉之前就餐的餐廳中，他的朋友有偶數(shù)個．若這個偶數(shù)為0，則當離開此餐廳后，此餐廳中的數(shù)學家仍然滿足條件；若這個偶數(shù)大于0，設為在此餐廳中的一個朋友，由假設，知在此餐廳中也有偶數(shù)個朋友，去掉后，在此餐廳中還剩下奇數(shù)個朋友．除了外，在此餐廳中有奇數(shù)個朋友，改變與的這奇數(shù)個朋友之間的關(guān)系，在此餐廳中朋友的數(shù)目變?yōu)榕紨?shù)．

在另一餐廳中，有奇數(shù)個的朋友．改變的朋友之間的關(guān)系，則每個的朋友與偶數(shù)個數(shù)學家之間改變了關(guān)系，于是，這些數(shù)學家朋友數(shù)目的奇偶性不變．

此外，由于恰有一個餐廳中包含偶數(shù)個的朋友，故不含的每一個分法均可以由包含的一個分法唯一確定．

回到原題．

在這種情形下，位數(shù)學家不同分法的數(shù)目與位數(shù)學家不同分法的數(shù)目相同．由歸納假設，知位數(shù)學家不同分法的數(shù)目是2的正整數(shù)次冪．因此，位數(shù)學家不同分法的數(shù)目也是2的正整數(shù)次冪．

（ii）每位數(shù)學家均有偶數(shù)個朋友．

在這種情形下的每種分法均有每位數(shù)學家在兩個餐廳中的朋友的數(shù)目為偶數(shù)．

設是任意一對朋友，去掉、，考慮每一對滿足下述條件的數(shù)學家，其中，是的朋友，是的朋友．則改變、之間的關(guān)系．同理，若是的朋友，是的朋友，也改變、之間的關(guān)系．若、均是和的朋友，則、之間的關(guān)系改變兩次，即、之間的關(guān)系沒有改變．

接下來考慮不同于、的任意一位數(shù)學家及要選擇的一個餐廳（在這種情形下，數(shù)學家的數(shù)目至少為3，即這樣的三人組是存在的）．設在此餐廳中有位朋友，在此餐廳中有位朋友．則、均為偶數(shù)．當去掉、后，在此餐廳中要么與、要么與、要么與（是、在此餐廳中共同的朋友的數(shù)目）、要么與0位數(shù)學家之間的關(guān)系發(fā)生了改變（這分別依賴于僅是的朋友、僅是的朋友、既是A又是的朋友、既不是又不是的朋友）．

因為、均為偶數(shù)，所以，朋友的數(shù)目的奇偶性沒有改變，仍為偶數(shù)．

由于不含、的每一個分法均可以由包含這對數(shù)學家的一個分法唯一確定：將、加入到其有奇數(shù)個朋友的餐廳中，然后改變所有的朋友和的朋友之間的關(guān)系，于是，在去掉之前和去掉之后建立了一個一—對應．

在這種情形下，位數(shù)學家不同分法的數(shù)目與位數(shù)學家不同分法數(shù)目相同．

由歸納假設，知位數(shù)學家不同分法的數(shù)目是2的正整數(shù)次冪．

因此，位數(shù)學家不同分法的數(shù)目也是2的正整數(shù)次冪．