【題目】設(shè)V是空間中2019個點構(gòu)成的集合,其中任意四點不共面某些點之間連有線段,記E為這些線段構(gòu)成的集合.試求最小的正整數(shù)n,滿足條件:若E至少有n個元素,則E一定含有908個二元子集,其中每個二元子集中的兩條線段有公共端點,且任意兩個二元子集的交為空集.

【答案】最小的n2795

【解析】

先證明一個引理:設(shè)G=(V,E)是一個簡單圖,且G是連通的,則G含有個兩兩無公共邊的角.再利用引理和反證法,結(jié)合組合數(shù)的凸性即可求得結(jié)果.

為了敘述方便,稱一個圖中的兩條相鄰的邊構(gòu)成一個,先證明一個引理:

設(shè)G=(V,E)是一個簡單圖,且G是連通的,

G含有個兩兩無公共邊的角(這里[a]表示實數(shù)a的整數(shù)部分).

引理的證明:對E的元素個數(shù)|E|歸納證明.

當(dāng)|E|=0,1,2,3時,結(jié)論顯然成立.

下面假設(shè)|E|≥4,并且結(jié)論在|E|較小時均成立.

只需證明,在G中可以選取兩條邊ab構(gòu)成一個角,在G中刪去a、b這兩條邊后,剩下的圖含有一個連通分支包含|E|2條邊.

對這個連通分支應(yīng)用歸納假設(shè)即得結(jié)論成立.

考慮G中的最長路,其中是互不相同的頂點.

因為G連通,故k≥3.

情形1.

由于P是最長路,v1的鄰點均在中,設(shè),其中3≤ik.

是一個角,在E中刪去這兩條邊.

v1處還有第三條邊,則剩下的圖是連通的;

v1處僅有被刪去的兩條邊,則v1成為孤立點,其余頂點仍互相連通.總之在剩下的圖中有一個連通分支含有|E|2條邊.

情形2.

是一個角,在G中刪去這兩條邊后,都成為孤立點,其余的點互相連通,

因此有一個連通分支含有條邊.

情形3,且v2中某個點相鄰.

是一個角,在G中刪去這兩條邊后,v1成為孤立點,其余點互相連通,

因此有一個連通分支含有條邊.

情形4,且v2與某個相鄰.

由于P是最長路,故u的鄰點均在之中.

是一個角,在G中刪去這兩條邊,則v1是孤立點.

若處僅有邊uv2,則刪去所述邊后u也是孤立點,而其余點互相連通.

u處還有其他邊uvi,3≤ik,則刪去所述邊后,除v1外其余點互相連通.

總之,剩下的圖中有一個連通分支含有條邊.

引理獲證.

回到原題,題中的VE可看作一個圖G=(V,E)

首先證明n≥2795.

設(shè).

中,首先兩兩連邊,再刪去其中15條邊(例如),共連了條邊,則這61個點構(gòu)成的圖是連通圖.再將剩余的20161=1958個點配成979對,每對兩點之間連一條邊,則圖G中一共連了1815+979=2794條線段.

由上述構(gòu)造可見,G中的任何一個角必須使用相連的邊,

因此至多有個兩兩無公共邊的角.

故滿足要求的n不小于2795.

另一方面,若|E|≥2795,可任意刪去若干條邊,只考慮的情形.

設(shè)Gk個連通分支,分別有個點,及條邊.

下面證明中至多有979個奇數(shù).

反證法,假設(shè)中有至少980個奇數(shù)由于是奇數(shù),

中至少有981個奇數(shù),k≥981.

不妨設(shè)都是奇數(shù),顯然.

,則有,

利用組合數(shù)的凸性,即對xy≥3,有,

可知當(dāng)m1,,m980,m9802以及一個59構(gòu)成時,取得最大值.

于是,

這與①矛盾.從而中至多有979個奇數(shù).

對每個連通分支應(yīng)用引理,可知G中含有N個兩兩無公共邊的角,

其中.

綜上,所求最小的n2795.

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

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

【題目】年上半年,隨著新冠肺炎疫情在全球蔓延,全球超過個國家或地區(qū)宣布進(jìn)人緊急狀態(tài),部分國家或地區(qū)直接宣布“封國”或“封城”,隨著國外部分活動進(jìn)入停擺,全球經(jīng)濟(jì)缺乏活力,一些企業(yè)開始倒閉,下表為年第一季度企業(yè)成立年限與倒閉分布情況統(tǒng)計表:

企業(yè)成立年份

2019

2018

2017

2016

2015

企業(yè)成立年限

1

2

3

4

5

倒閉企業(yè)數(shù)量(萬家)

5.28

4.72

3.58

2.70

2.15

倒閉企業(yè)所占比例

21.4%

19.1%

14.5%

10.9%

8.7%

1)由所給數(shù)據(jù)可用線性回歸模型擬合的關(guān)系,請用相關(guān)系數(shù)加以說明;

2)建立關(guān)于的回歸方程,預(yù)測年成立的企業(yè)中倒閉企業(yè)所占比例.

參考數(shù)據(jù):,,,,

相關(guān)系數(shù),樣本的最小二乘估計公式為.

查看答案和解析>>

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

【題目】若函數(shù)有最大值,則實數(shù)的取值范圍是( )

A.B.C.D.

查看答案和解析>>

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

【題目】設(shè){an}是一個首項為2,公比為qq1)的等比數(shù)列,且3a12a2,a3成等差數(shù)列.

1)求{an}的通項公式;

2)已知數(shù)列{bn}的前n項和為Sn,b1=1,且1n2),求數(shù)列{anbn}的前n項和Tn.

查看答案和解析>>

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

【題目】設(shè)F是橢圓的左焦點,過點F且斜率為正的直線與E相交于AB兩點,過點AB分別作直線AMBN滿足AMl,BNl,且直線AM、BN分別與x軸相交于MN.試求|MN|的最小值.

查看答案和解析>>

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

【題目】我國南北朝時期的數(shù)學(xué)家祖暅提出了一條原理:“冪勢既同,則積不容異”即夾在兩個平行平面之間的兩個幾何體,被平行于這兩個平面的任意平面所截,如果截得的兩個截面的面積總相等,那么這兩個幾何體的體積相等.橢球是橢圓繞其長軸旋轉(zhuǎn)所成的旋轉(zhuǎn)體,如圖,將底面半徑都為.高都為的半橢球和已被挖去了圓錐的圓柱(被挖去的圓錐以圓柱的上底面為底面,下底面的圓心為頂點)放置于同一平面上,用平行于平面且與平面任意距離處的平面截這兩個幾何體,截面分別為圓面和圓環(huán),可以證明=圓環(huán)總成立.據(jù)此,橢圓的短半軸長為2,長半軸長為4的橢球的體積是(

A.B.C.D.

查看答案和解析>>

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

【題目】已知函數(shù),對于函數(shù)有下述四個結(jié)論:①函數(shù)在其定義域上為增函數(shù);②對于任意的,,都有成立;③有且僅有兩個零點;④若,則在點處的切線與在點處的切線為同一直線.其中所有正確的結(jié)論有( )

A.①②③B.①③C.②③④D.③④

查看答案和解析>>

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

【題目】隨著共享單車的成功運(yùn)營,更多的共享產(chǎn)品逐步走人大家的世界,共享汽車、共享籃球、共享充電寶等各種共享產(chǎn)品層出不窮廣元某景點設(shè)有共享電動車租車點,共享電動車的收費標(biāo)準(zhǔn)是每小時2不足1小時的部分按1小時計算甲、乙兩人各租一輛電動車,若甲、乙不超過一小時還車的概率分別為;一小時以上且不超過兩小時還車的概率分別為;兩人租車時間都不會超過三小時.

求甲、乙兩人所付租車費用相同的概率;

設(shè)甲、乙兩人所付的租車費用之和為隨機(jī)變量,求的分布列與數(shù)學(xué)期望

查看答案和解析>>

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

【題目】已知定義域為的函數(shù)的圖象為曲線,曲線在點的切線為(其中).

(Ⅰ)求實數(shù)的值;

(Ⅱ)證明:(i;

ii

查看答案和解析>>

同步練習(xí)冊答案