高中數(shù)學(xué)奧賽講義：集合.pdf

高中數(shù)學(xué)奧賽 高中數(shù)學(xué)奧賽 集合講義 強(qiáng)化訓(xùn)練和參考答案集合講義 強(qiáng)化訓(xùn)練和參考答案 內(nèi)容綜述內(nèi)容綜述 本講先介紹了以下一些重要的概念 集合 子集 兩集合相等 真子集 并集 交集 相對(duì)補(bǔ)集 然后介紹了著名的容斥原理 接著介紹了以下幾個(gè)定律 零律 分配律 排中 律 吸收律 補(bǔ)交轉(zhuǎn)換律 德 摩根律 然后通過 6 道例題分析了一部分集合題目的解題方法與技巧 同學(xué)們應(yīng)在熟悉以上定 義 定理 定律的基礎(chǔ)上仔細(xì)分析例題材解法 爭(zhēng)取可以獨(dú)立解決訓(xùn)練題 要點(diǎn)講解 要點(diǎn)講解 1 基本理論 1 基本理論 除了課內(nèi)知識(shí)外 我們補(bǔ)充以下知識(shí) 相對(duì)補(bǔ)集 稱屬于 A 而不屬于 B 的全體元素 組成的集合為 B 對(duì) A 的相對(duì)補(bǔ)集或差集 記作 A B 容斥原理 以表示集合 A 中元素的數(shù)目 我們有 其中為 n 個(gè)集合稱為 A 的階 n 階集合的全部子集數(shù)目為 A B C 為三個(gè)集合 就有下面的定律 1 分配律 2 零律 3 排中律 4 吸收律 5 補(bǔ)交轉(zhuǎn)換律 6 德 摩根律的相對(duì)形式 京師博雅園 w w w j s y b y x t c o m 例題分析 例題分析 例 1例 1 對(duì)集合 1 2 n 及其每一個(gè)非空了集 定義一個(gè)唯一確定的 交替和 如 下 按照遞減的次序重新排列該子集 然后交替地減或加后繼的數(shù)所得的結(jié)果 例如 集 合的 交替和 是 9 6 4 2 1 6 的 交替和 是 6 5 1 的交替和是 2 那么 對(duì)于 n 7 求所有子集的 交替和 的總和 分析分析 n 7 時(shí) 集合 7 6 5 4 3 2 1 的非空子集有個(gè) 雖然子集數(shù)目有 限 但是逐一計(jì)算各自的 交替和 再相加 計(jì)算量仍然巨大 但是 根據(jù) 交替和 的 定義 容易看到集合 1 2 3 4 5 6 7 與 1 2 3 4 5 6 的 交替和 是 7 可 以想到把一個(gè)不含 7 的集和 A 與的 交替和 之和應(yīng)為 7 那么 我們也就很容易 解決這個(gè)問題了 解解 集合 1 2 3 4 5 6 7 的子集中 除去 7 外還有個(gè)非空子集合 把 這個(gè)非空子集兩兩結(jié)組后分別計(jì)算每一組中 交替和 之和 結(jié)組原則是設(shè) 這是把結(jié)合為一組 顯然 每組中 交替和 之 和應(yīng)為 7 共有組 所以 所有 交替和 之和應(yīng)該為 說明說明 我們?cè)谶@道題的證明過程中用了這類題目最典型的解法 就是 對(duì)應(yīng) 的方法 對(duì)應(yīng) 的方法在解決相等的問題中應(yīng)用得更多 例 2 例 2 設(shè) A 1 2 2n 證明 A 的任意 n 1 階子集中 存在兩個(gè)數(shù) 一個(gè)可 被另一個(gè)整除 分析分析 對(duì)于 2n 個(gè)數(shù)中取 n 1 個(gè)數(shù) 我們應(yīng)該有一個(gè)直覺就是把這 2n 個(gè)數(shù)分成 n 組 每組都必然滿足題目條件 那么由抽屜原則命題就解決了 證明 證明 前 2n 個(gè)自然數(shù)中 共有 n 個(gè)奇數(shù) 根據(jù)自然數(shù)的一種有用的表達(dá)形式 n 2k 1 2 L 為非負(fù)整數(shù) 考查 A 的下列 n 個(gè)子集 京師博雅園 w w w j s y b y x t c o m 容易看到 考慮 A 中任意 n 1 個(gè)元素 根據(jù)抽屜原則知 至少有兩個(gè)元素是上述 n 個(gè)集合中同一 個(gè)集合中的元素 這兩個(gè)數(shù)中 必有一個(gè)可被另一個(gè)整除 說明說明 把一個(gè)集合分成若干個(gè)兩兩不交的子集的并 也則分拆 這種分拆的方法在解 決集合的問題時(shí)為常用方法之一 例 3 例 3 某班對(duì)數(shù)學(xué) 物理 化學(xué)三科總評(píng)成績(jī)統(tǒng)計(jì)如下 優(yōu)秀的人數(shù) 數(shù)學(xué) 21 個(gè) 物理 19 個(gè) 化學(xué) 20 個(gè) 數(shù)學(xué)物理都優(yōu)秀 9 人 物理化學(xué)都優(yōu)秀 7 人 化學(xué)數(shù)學(xué)都優(yōu)秀 8 人 這個(gè)班有 5 人任何一科都不優(yōu)秀 那么確定這個(gè)班人數(shù)以 及僅有一科優(yōu)秀的三科分別有多少個(gè)人 分析 分析 自然地設(shè) A 數(shù)學(xué)總評(píng)優(yōu)秀的人 B 物理總評(píng)優(yōu)秀的人 C 化學(xué)總評(píng)優(yōu)秀的人 則已知 A 21 B 19 C 20 這表明全班人數(shù)在 41 至 48 人之間 僅數(shù)學(xué)優(yōu)秀的人數(shù)是 可見僅數(shù)學(xué)優(yōu)秀的人數(shù)在 4 至 11 人之間 同理僅物理優(yōu)秀的人數(shù)在 3 至 10 人之間 同理僅化學(xué)優(yōu)秀的人數(shù)在 5 至 12 人之間 解解 略 說明說明 先將具體的實(shí)際生活中的問題數(shù)學(xué)化 然后根據(jù)數(shù)學(xué)理論來解決 這個(gè)問題不僅是競(jìng)賽中常見情況 也是在未來學(xué)習(xí)中數(shù)學(xué)真正有用的地方 例 4 例 4 n 元集合具有多少個(gè)不同的不交子集對(duì) 京師博雅園 w w w j s y b y x t c o m 分析 分析 我們一般想法是對(duì)于一個(gè)子集 求出與它不交的子集個(gè)數(shù) 然后 就可以求出總的子集對(duì)來了 解解 如果子集對(duì)是有序的 即在子集對(duì)中可以區(qū)分第一個(gè)子集與第二個(gè) 子集 則第一個(gè)子集若是 k 個(gè)元素 第二個(gè)子集就由其余 n k 個(gè)元素組成 可能 的情況是種 而這時(shí)第一個(gè)集合的選取的可能情況應(yīng)為種 那么 k 從 o 變到 n 總的情況可能就是 如果子集對(duì)是無序的 即兩個(gè)子集相同但次序不同的子集對(duì)不認(rèn)為不同 則對(duì)有序子集對(duì)中有一對(duì) 是由兩個(gè)空集組成 而對(duì)其它個(gè)有序?qū)?每一對(duì)中交換兩個(gè)子集的次序 得到的是同一個(gè)無序子集對(duì) 因此有個(gè)無序子集對(duì) 其中至少有一個(gè) 子集非空 于是無序子集對(duì)的總數(shù)為 分析二 分析二 我們可以從元素的角度來思考問題 對(duì)一個(gè)元素來說 它有三 種不同的選擇 在第一個(gè)集合中 在第二個(gè)集合中 或者不在兩個(gè)集合中 解法二解法二 在計(jì)算有序?qū)Φ臄?shù)目時(shí) 對(duì)每一個(gè)元素來說有三種可能 它或 在第一個(gè)子集 或在第二個(gè)子集 或不在其中任意一個(gè)子集 因此不同的不交有 序子集對(duì)的總數(shù) 以下同解法一 說明 說明 本題為 1973 年捷克的競(jìng)賽題 對(duì)題目的不同分析使我們得到了 差異很大的兩個(gè)解法 解法一從題目要求想起 很容易想到 但解出最后解卻不 見得那么簡(jiǎn)單 而解法二的想法是類似于集合分析的想法 很難想到 但想出后 比較容易求解 兩個(gè)解法對(duì)比一下正體現(xiàn)了數(shù)學(xué)思維的兩方面 一個(gè)是純代數(shù)想 法 以計(jì)算的方法替代對(duì)題目更深層次的研究 另一個(gè)則是控掘題目本身的內(nèi)在 關(guān)系 找出最合適的解答 我們當(dāng)然推薦第二種做法 例 5 例 5 1992 位科學(xué)家 每人至少與 1329 人合作過 那么 其中一定有 四位數(shù)學(xué)家兩兩合作過 分析 分析 在與一個(gè)人 A 合作的人中我們找到 B 再說明一定有人與 A 和 B 都合作過為 C 最后再說明有人與 A B C 都合作過為 D 那么 A B C D 就是 找的人了 證 明證 明 一 個(gè) 人A 不 妨 設(shè)B與 之 合 作 那 么 即 C 與 京師博雅園 w w w j s y b y x t c o m A 和 B 均合作過 分別表示與 A B 合作過的人的集合 同樣地 所以存在 則 A B C D 就是所求 證畢 說明說明 把一個(gè)普通的敘述性問題轉(zhuǎn)化為集合的語(yǔ)言描述的問題通常為解 題的關(guān)鍵之處 也是同學(xué)們需加強(qiáng)的 例 6 例 6 集合 X 由 n 個(gè)元素構(gòu)成 對(duì)兩個(gè)子集 求得集合 的元素個(gè)數(shù) 證明 所有求得個(gè)數(shù)之和為 分析分析 我們先考慮一個(gè)簡(jiǎn)單情況 n 2 這時(shí)有四個(gè)集合 記為 交集情況就是 那么對(duì)于 n 很大時(shí) 我們有的不只是 4 個(gè)集合卻可以以此形式分組 證明 證明 因?yàn)榧?X 總共有個(gè)不同子集 所以不同的有序子集對(duì)共有 將所有子集對(duì)分為個(gè) 4 元組 其 中表示子集的補(bǔ)集 X A 交換子集對(duì)的 4 元組中子集對(duì)的次序 得到的 是同一個(gè)四元組 事實(shí)上 由子集對(duì)得到的 4 元組與由得到的完 全相同 且 說明 說明 復(fù)雜的問題先考慮簡(jiǎn)單的特殊的情況是一種最常用的方法 從中 找到共性后就很容易得到原題目有答案了 強(qiáng)化練習(xí)強(qiáng)化練習(xí) 1 一個(gè)集合含有 10 個(gè)互不相同的十進(jìn)制兩位數(shù) 證明 這個(gè)集合必有兩個(gè) 無公共元素的子集合 這兩個(gè)子集元素和相等 2 是否存在兩個(gè)以非頁(yè)整數(shù)為元素的集合 A B 使得任一個(gè)非負(fù)整數(shù)都可 以被 A B 之中各取一數(shù)之和唯一表出 京師博雅園 w w w j s y b y x t c o m 3 對(duì)每個(gè)使得在 n 元集合中 可以取出 k 個(gè)子集 其中 任意兩個(gè)的交非合 4 能否把分成兩個(gè)積相等的不交集合 參考答案 參考答案 1 10 個(gè)元素的集合共有個(gè)非空子集 每一個(gè)這個(gè)集合的 非空子集中數(shù)字之和小于 由抽屜原則知 必有兩個(gè)子集 它們 有相同的元素和 設(shè)為滿足題目要求條件 2 十進(jìn)制為第 1 位 為第 i 位 考慮如下的 A B A 為奇位為 o 的那些非負(fù)整數(shù)組成 B 為偶位為 o 的那些非負(fù)整數(shù)組成 不難驗(yàn)證這樣的 A B 是符合題目要求的 3 在集合中取定一個(gè)元素 并只考慮含的子集 這類子集的個(gè)數(shù)為集合的子集的個(gè)數(shù) 即為 因此 另 一方面 設(shè)從集合 X 至少取出個(gè)子集 將集合 X