奧數(shù)容斥原理專項訓(xùn)練講義前言：為何要學(xué)習(xí)容斥原理？在奧數(shù)的世界里，我們常常會遇到這樣一類問題：需要計算具有某些特征的對象的數(shù)量，但這些特征之間并非相互獨立，而是存在交叉重疊。此時，簡單的加法或減法往往難以奏效，甚至?xí)?dǎo)致重復(fù)計算或遺漏。容斥原理（PrincipleofInclusion-Exclusion）便是解決這類計數(shù)問題的銳利武器。它通過巧妙地“包含”與“排除”，幫助我們精準(zhǔn)地計算出目標(biāo)集合的元素個數(shù)，是組合數(shù)學(xué)中不可或缺的基礎(chǔ)工具，也是奧數(shù)競賽中的?？?。掌握容斥原理，不僅能解決特定類型的題目，更能培養(yǎng)我們邏輯思維的嚴(yán)謹(jǐn)性與條理性。一、容斥原理的基本概念與核心思想1.1從簡單的計數(shù)困境說起想象一個場景：一個班級中有學(xué)生參加了數(shù)學(xué)興趣小組或語文興趣小組，其中參加數(shù)學(xué)小組的有A人，參加語文小組的有B人，兩個小組都參加的有C人。如果我們想知道參加了至少一個興趣小組的學(xué)生有多少人，直接將A和B相加，顯然會把兩個小組都參加的C人重復(fù)計算一次。因此，正確的人數(shù)應(yīng)該是A+B-C。這里，我們先“包含”了所有參加數(shù)學(xué)和語文小組的人，然后“排除”了重復(fù)計算的部分，這就是容斥原理最樸素的思想。1.2容斥原理的核心思想容斥原理的核心在于：為了計算幾個集合的并集的元素個數(shù)，我們先將每個集合的元素個數(shù)相加（包含），然后減去所有兩兩集合相交的元素個數(shù)（排除），再加上所有三個集合相交的元素個數(shù)（再包含），接著減去所有四個集合相交的元素個數(shù)（再排除），以此類推，直到包含/排除完所有可能的交集。這個過程體現(xiàn)了“多退少補(bǔ)”的計數(shù)哲學(xué)。二、容斥原理的基本公式2.1兩個集合的容斥原理設(shè)A、B是兩個有限集合，則它們的并集的元素個數(shù)計算公式為：A∪B=A+B-A∩B其中，|A|表示集合A的元素個數(shù)，|B|表示集合B的元素個數(shù)，|A∩B|表示集合A與集合B的交集的元素個數(shù)。理解與應(yīng)用要點：*韋恩圖（VennDiagram）：畫韋恩圖是理解和應(yīng)用容斥原理的絕佳輔助手段。兩個集合的韋恩圖由兩個相交的圓組成，分別代表A和B，重疊部分即為A∩B。*適用場景：當(dāng)問題中涉及兩個有重疊部分的群體，并要求計算“至少屬于其中一個群體”的總量時，可直接套用。例題1：一個班有40名學(xué)生，其中25人喜歡打籃球，20人喜歡踢足球，有10人既喜歡打籃球又喜歡踢足球。問：這個班至少喜歡其中一項運(yùn)動的學(xué)生有多少人？解析：設(shè)A={喜歡打籃球的學(xué)生}，B={喜歡踢足球的學(xué)生}。則|A|=25，|B|=20，|A∩B|=10。根據(jù)兩個集合的容斥原理，至少喜歡一項運(yùn)動的學(xué)生人數(shù)為|A∪B|=|A|+|B|-|A∩B|=25+20-10=35（人）。點睛：直接相加會重復(fù)計算兩種運(yùn)動都喜歡的10人，故需減去一次。2.2三個集合的容斥原理當(dāng)問題涉及三個集合時，情況稍顯復(fù)雜，但原理相通。設(shè)A、B、C是三個有限集合，則它們的并集的元素個數(shù)計算公式為：A∪B∪C=A+B+C-A∩B-A∩C-B∩C+A∩B∩C公式解讀：*首先將A、B、C三個集合的元素個數(shù)相加（|A|+|B|+|C|）。*由于每兩個集合的交集都被重復(fù)計算了一次，所以需要減去所有兩兩交集的元素個數(shù)（-|A∩B|-|A∩C|-|B∩C|）。*經(jīng)過上述兩步后，三個集合的公共交集（A∩B∩C）被加了三次，又減了三次，相當(dāng)于沒有被計算，因此需要再加上一次（+|A∩B∩C|）。例題2：某班學(xué)生參加語文、數(shù)學(xué)、英語三科競賽，每人至少參加一科。已知參加語文競賽的有20人，參加數(shù)學(xué)競賽的有25人，參加英語競賽的有22人，參加語文和數(shù)學(xué)兩科的有8人，參加語文和英語兩科的有7人，參加數(shù)學(xué)和英語兩科的有6人，三科都參加的有3人。問：這個班共有多少名學(xué)生？解析：設(shè)A={參加語文競賽的學(xué)生}，B={參加數(shù)學(xué)競賽的學(xué)生}，C={參加英語競賽的學(xué)生}。已知|A|=20，|B|=25，|C|=22，|A∩B|=8，|A∩C|=7，|B∩C|=6，|A∩B∩C|=3。因為每人至少參加一科，所以班級總?cè)藬?shù)即為|A∪B∪C|。根據(jù)三個集合的容斥原理：A∪B∪C=(20+25+22)-(8+7+6)+3=67-21+3=49（人）點睛：三個集合的容斥，關(guān)鍵在于理解為何要加回三個集合的交集。畫圖能清晰看到各部分的重疊情況。三、容斥原理的靈活運(yùn)用與解題技巧3.1利用韋恩圖輔助分析韋恩圖是容斥原理的“可視化工具”。在解決復(fù)雜問題時，畫出清晰的韋恩圖，將各部分?jǐn)?shù)量標(biāo)出（或用字母表示未知量），能幫助我們直觀地理解題意，找到數(shù)量關(guān)系。例題3：在1到100的自然數(shù)中，能被2或3整除的數(shù)有多少個？解析：*設(shè)A={1到100中能被2整除的數(shù)}，B={1到100中能被3整除的數(shù)}。*目標(biāo)是求|A∪B|。*|A|=100//2=50（“//”表示取整除商）*|B|=100//3=33*|A∩B|={1到100中能同時被2和3整除的數(shù)}={能被6整除的數(shù)}=100//6=16*由兩個集合容斥原理：|A∪B|=50+33-16=67。點睛：此類“能被...整除”的問題是容斥原理的典型應(yīng)用。注意計算交集時是求公倍數(shù)。3.2逆向思維與容斥原理有時，直接計算并集的元素個數(shù)比較困難，我們可以先計算總數(shù)中不滿足任何條件的元素個數(shù)，再用總數(shù)減去這個數(shù)，得到滿足至少一個條件的元素個數(shù)。這就是“正難則反”的逆向思維。例題4：在1到100的自然數(shù)中，既不是2的倍數(shù)，也不是3的倍數(shù)，還不是5的倍數(shù)的數(shù)有多少個？解析：*總共有100個數(shù)。*要求的是“既不是2，也不是3，也不是5的倍數(shù)”的數(shù)的個數(shù)，即求|非A∩非B∩非C|，其中A、B、C分別表示能被2、3、5整除的數(shù)。*根據(jù)摩根定律，|非A∩非B∩非C|=總數(shù)-|A∪B∪C|。*先求|A∪B∪C|：*|A|=50,|B|=33,|C|=20*|A∩B|=16(能被6整除),|A∩C|=10(能被10整除),|B∩C|=6(能被15整除)*|A∩B∩C|=3(能被30整除)*|A∪B∪C|=50+33+20-16-10-6+3=74*所以，既不是2、3、5倍數(shù)的數(shù)有：100-74=26（個）。點睛：當(dāng)題目中出現(xiàn)“不...不...不...”等多重否定時，逆向思考結(jié)合容斥原理往往能化繁為簡。3.3容斥原理在“至多”、“至少”問題中的應(yīng)用例題5：一個班有45名學(xué)生，參加數(shù)學(xué)小組的有28人，參加語文小組的有22人，參加英語小組的有26人。同時參加數(shù)學(xué)和語文的有12人，同時參加數(shù)學(xué)和英語的有15人，同時參加語文和英語的有10人。問：至少參加兩個小組的學(xué)生有多少人？三個小組都參加的學(xué)生至多有多少人？解析：第一問：“至少參加兩個小組”包括參加兩個小組和參加三個小組的學(xué)生。設(shè)參加兩個小組的學(xué)生集合為D，參加三個小組的學(xué)生集合為E（即|A∩B∩C|=x）。參加數(shù)學(xué)和語文但不參加英語的有：12-x參加數(shù)學(xué)和英語但不參加語文的有：15-x參加語文和英語但不參加數(shù)學(xué)的有：10-x所以至少參加兩個小組的人數(shù)為(12-x)+(15-x)+(10-x)+x=37-2x。（此處也可理解為：|A∩B|+|A∩C|+|B∩C|-2|A∩B∩C|，因為三個交集的部分被加了三次，所以要減去2次）第二問：求三個小組都參加的學(xué)生至多有多少人，即求x的最大值。由于各部分人數(shù)不能為負(fù)數(shù)：12-x≥0?x≤1215-x≥0?x≤1510-x≥0?x≤10同時，參加單個小組的人數(shù)也不能為負(fù)數(shù)。例如，只參加數(shù)學(xué)的人數(shù)為：28-(12-x)-(15-x)-x=28-27+x=1+x≥0，恒成立。同理可驗證其他單個小組人數(shù)。故x的最大值為10。點睛：分析清楚“至少參加兩個”包含的范圍，以及各子集人數(shù)非負(fù)是解決此類問題的關(guān)鍵。四、鞏固練習(xí)練習(xí)1：一個年級有100名學(xué)生，訂閱《小學(xué)生數(shù)學(xué)報》的有58人，訂閱《小學(xué)生語文報》的有65人，兩種報紙都訂閱的有30人。問：(1)只訂閱《小學(xué)生數(shù)學(xué)報》的有多少人？(2)至少訂閱一種報紙的有多少人？(3)兩種報紙都不訂閱的有多少人？練習(xí)2：在1到100的自然數(shù)中，能被3或7整除的數(shù)有多少個？練習(xí)3：某班有學(xué)生50人，參加美術(shù)興趣小組的有28人，參加音樂興趣小組的有25人，參加體育興趣小組的有20人。其中，美術(shù)和音樂都參加的有10人，美術(shù)和體育都參加的有8人，音樂和體育都參加的有9人，三個小組都參加的有5人。問：(1)只參加一個興趣小組的有多少人？(2)沒有參加任何興趣小組的有多少人？練習(xí)4：求1到100中，不能被2、3、7中任何一個數(shù)整除的數(shù)有多少個？練習(xí)5：某校對100名學(xué)生進(jìn)行調(diào)查，結(jié)果發(fā)現(xiàn)他們喜歡看球賽、電影和戲劇。其中58人喜歡看球賽，38人喜歡看戲劇，52人喜歡看電影，既喜歡看球賽又喜歡看戲劇的有18人，既喜歡看電影又喜歡看戲劇的有16人，三種都喜歡看的有12人，只喜歡看電影的有22人。問：有多少人既喜歡看球賽又喜歡看電影？五、總結(jié)與思考容斥原理的核心在于“包容”與“排斥”的辯證統(tǒng)一。無論是兩個集合、三個集合，還是更多集合的情況，其基本思想都是先不考慮重疊，將所有對象包容進(jìn)來，然后再將重復(fù)計算的部分排斥出去，如此反復(fù)，直至得到準(zhǔn)確的計數(shù)。解題關(guān)鍵步驟：1.明確集合：清晰定義問題中的各個集合，明確每個集合代表的含義。2.畫韋恩圖：盡可能畫出韋恩圖，將已知數(shù)據(jù)填入圖中相應(yīng)區(qū)域，直觀感受各部分關(guān)系。3.選擇公式：根據(jù)集合數(shù)量（兩個、三個或更多）選擇合適的容斥公式，或考慮逆向思維。4.準(zhǔn)確計算：注意交集、并集的計算，特別是涉及多個集合時，避免重復(fù)或遺漏。容斥原理