Question

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

Answer 1

【答案】見解析

【解析】

設(shè)參加會(huì)議的有位數(shù)學(xué)家．對(duì)用數(shù)學(xué)歸納法．

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

假設(shè)當(dāng)有位數(shù)學(xué)家參加會(huì)議時(shí)，有種不同的分法．

當(dāng)有位數(shù)學(xué)家時(shí)，分兩種情形討論．

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

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

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

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

先證明一個(gè)命題．

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

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

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

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

回到原題．

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

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

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

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

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

因?yàn)?/span>、均為偶數(shù)，所以，朋友的數(shù)目的奇偶性沒有改變，仍為偶數(shù)．

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

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

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

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