【題目】在一次數(shù)學(xué)競賽中，某些選手是朋友關(guān)系.記所有選手的集合為X，對集合X的子集Y，若可以將這些人兩兩分組，且每組中兩名選手均是朋友關(guān)系，則稱子集Y“可兩兩分組”.已知集合X不可兩兩分組，且對于任意選手，若A、B不是朋友關(guān)系，則可兩兩分組，且X中沒有一個(gè)人與其他所有人均為朋友關(guān)系證明:對任意選手，若a、b為朋友關(guān)系，b、c為朋友關(guān)系，則a、c也為朋友關(guān)系

【答案】見解析

【解析】

考慮一個(gè)圖G，頂點(diǎn)由集合X組成，若X中兩人認(rèn)識，則將這兩人相連，否則不相連若一個(gè)圖中的點(diǎn)可以兩兩分組，且每組中兩個(gè)點(diǎn)均相連，則稱這種分組為圖G的一個(gè)“完美匹配”（可以看成是圖G的一個(gè)子圖）.于是，題目的條件變成了圖G不存在完美匹配，且若x、y不相連，則G＋xy（表示把這個(gè)圖G的xy也相連）存在一個(gè)完美匹配，且沒有一個(gè)點(diǎn)與所有點(diǎn)均相連.

用反證法.

若存在a、b、c使得a、b認(rèn)識，b、c認(rèn)識，但a、c不認(rèn)識，由于沒有人認(rèn)識其他所有人，故存在，使得b、d不認(rèn)識.

由假設(shè)可得G＋ac有一個(gè)完美匹配，記為；G＋bd也有一個(gè)完美匹配記為.

考慮與的對稱差

.

則容易得到S是一些互不相交的圈，且每個(gè)圈均由偶數(shù)個(gè)點(diǎn)組成，設(shè)ac屬于圈，bd屬于圈.

分兩種情形討論

若，則在圈外的點(diǎn)按照的分組方式分組，在圈中按照的分組方式即可得到原圖G的一個(gè)完美匹配，即得矛盾.

若，則這個(gè)圈從b出發(fā)沿邊bd開始，不妨設(shè)首先連到點(diǎn)a，即b到a的路徑（首先經(jīng)過邊bd）為P，于是，P＋ab為一個(gè)圈，其中，有一半的邊（間隔地）屬于對P＋ab這個(gè)圈外的點(diǎn)按的方式分組，而對P＋ab按ab及的方式分組即可得到原圖G的一個(gè)完美匹配，即得矛盾.

練習(xí)冊系列答案
相關(guān)習(xí)題

科目：高中數(shù)學(xué) 來源： 題型：

【題目】某醫(yī)院為篩查某種疾病，需要檢驗(yàn)血液是否為陽性，現(xiàn)有（）份血液樣本，有以下兩種檢驗(yàn)方式：（1）逐份檢驗(yàn)，則需要檢驗(yàn)次；（2）混合檢驗(yàn)，將其中（且）份血液樣本分別取樣混合在一起檢驗(yàn)．若檢驗(yàn)結(jié)果為陰性，這份的血液全為陰性，因而這份血液樣本只要檢驗(yàn)一次就夠了，如果檢驗(yàn)結(jié)果為陽性，為了明確這份血液究竟哪幾份為陽性，就要對這份再逐份檢驗(yàn)，此時(shí)這份血液的檢驗(yàn)次數(shù)總共為次．假設(shè)在接受檢驗(yàn)的血液樣本中，每份樣本的檢驗(yàn)結(jié)果是陽性還是陰性都是獨(dú)立的，且每份樣本是陽性結(jié)果的概率為．

（1）假設(shè)有5份血液樣本，其中只有2份樣本為陽性，若采用逐份檢驗(yàn)方式，求恰好經(jīng)過4次檢驗(yàn)就能把陽性樣本全部檢驗(yàn)出來的概率．

（2）現(xiàn)取其中（且）份血液樣本，記采用逐份檢驗(yàn)方式，樣本需要檢驗(yàn)的總次數(shù)為，采用混合檢驗(yàn)方式，樣本需要檢驗(yàn)的總次數(shù)為

（�。┰囘\(yùn)用概率統(tǒng)計(jì)的知識，若 ，試求關(guān)于的函數(shù)關(guān)系式；

（ⅱ）若，采用混合檢驗(yàn)方式可以使得樣本需要檢驗(yàn)的總次數(shù)的期望值比逐份檢驗(yàn)的總次數(shù)期望值更少，求的最大值．

參考數(shù)據(jù)：，，，，

查看答案和解析>>

科目：高中數(shù)學(xué) 來源： 題型：

【題目】已知函數(shù).

（1）若函數(shù)，求的極值；

（2）證明：.

（參考數(shù)據(jù)： ）

查看答案和解析>>

科目：高中數(shù)學(xué) 來源： 題型：

【題目】已知橢圓（）的左焦點(diǎn)為，點(diǎn)為橢圓上任意一點(diǎn)，且的最小值為，離心率為.

（1）求橢圓的方程；

（2）設(shè)O為坐標(biāo)原點(diǎn)，若動直線與橢圓交于不同兩點(diǎn)、（、都在軸上方），且.

（i）當(dāng)為橢圓與軸正半軸的交點(diǎn)時(shí)，求直線的方程；

（ii）對于動直線，是否存在一個(gè)定點(diǎn)，無論如何變化，直線總經(jīng)過此定點(diǎn)？若存在，求出該定點(diǎn)的坐標(biāo)；若不存在，請說明理由.

查看答案和解析>>

科目：高中數(shù)學(xué) 來源： 題型：

【題目】某餐廳通過查閱了最近5次食品交易會參會人數(shù) (萬人)與餐廳所用原材料數(shù)量 (袋)，得到如下統(tǒng)計(jì)表：

第一次

第二次

第三次

第四次

第五次

參會人數(shù) (萬人)

13

9

8

10

12

原材料 (袋)

32

23

18

24

28

（1）根據(jù)所給5組數(shù)據(jù)，求出關(guān)于的線性回歸方程.

（2）已知購買原材料的費(fèi)用 (元)與數(shù)量 (袋)的關(guān)系為，

投入使用的每袋原材料相應(yīng)的銷售收入為700元，多余的原材料只能無償返還，據(jù)悉本次交易大會大約有15萬人參加，根據(jù)(1)中求出的線性回歸方程，預(yù)測餐廳應(yīng)購買多少袋原材料，才能獲得最大利潤，最大利潤是多少？(注：利潤銷售收入原材料費(fèi)用).

參考公式： ， .

參考數(shù)據(jù)： ， ， .

查看答案和解析>>

科目：高中數(shù)學(xué) 來源： 題型：

【題目】編號分別為的12名籃球運(yùn)動員在某次籃球比賽中的得分記錄如下：

運(yùn)動員編號

得分

5

10

12

16

8

21

27

15

6

22

18

29

（1）完成如下的頻率分布表：

得分區(qū)間

頻數(shù)

頻率

3

合計(jì)

（2）從得分在區(qū)間內(nèi)的運(yùn)動員中隨機(jī)抽取2人，求這2人得分之和大于25的概率.

查看答案和解析>>

科目：高中數(shù)學(xué) 來源： 題型：

【題目】已知函數(shù)（為自然對數(shù)的底數(shù)）.

（1）討論函數(shù)的單調(diào)性；

（2）當(dāng)時(shí)，恒成立，求整數(shù)的最大值.

查看答案和解析>>

科目：高中數(shù)學(xué) 來源： 題型：

【題目】已知（m，n為常數(shù)），在處的切線方程為.

（Ⅰ）求的解析式并寫出定義域；

（Ⅱ）若任意，使得對任意上恒有成立，求實(shí)數(shù)a的取值范圍；

（Ⅲ）若有兩個(gè)不同的零點(diǎn)，求證： .

查看答案和解析>>

科目：高中數(shù)學(xué) 來源： 題型：

【題目】在直角坐標(biāo)系中，直線的參數(shù)方程為（為參數(shù)），直線與直線平行，且過坐標(biāo)原點(diǎn)，圓的參數(shù)方程為（為參數(shù)）．以坐標(biāo)原點(diǎn)為極點(diǎn)，軸的正半軸為極軸建立極坐標(biāo)系．

（1）求直線和圓的極坐標(biāo)方程；

（2）設(shè)直線和圓相交于點(diǎn)、兩點(diǎn)，求的周長．

查看答案和解析>>

同步練習(xí)冊答案